Problem 86

Erdős Problem #86: declared status 'open'. Formalized: no. Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that every subgraph of $Q_n$ with$$\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}$$many edges contains a $C_4$? Prize: $100. OEIS: A245762. Tags: graph theory.