Logo
All Random Solved Random Open
OPEN - $100
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$?
The best known result is due to Balogh, Hu, Lidicky, and Liu [BHLL14], who proved that $0.6068 n2^{n-1}$ edges suffice. Erdős [Er91] observes that there exist subgraphs with \[\geq \left(\frac{1}{2}+\frac{c}{n}\right)n2^{n-1}\] many edges without a $C_4$ (for some constant $c>0$). He suggests that it is 'perhaps not hopeless' to determine the threshold exactly.

A similar question can be asked for other even cycles.

See also [666] and the entry in the graphs problem collection.

Additional thanks to: Casey Tompkins