Logo
All Problems Random Solved Random Open
$100
Is it true that every subgraph of the $n$-dimensional cube 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.
Additional thanks to: Casey Tompkins