Problem Statement
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$?
Categories:
Graph Theory
Progress
Let $f(n)$ be the maximum number of edges in a subgraph of $Q_n$ without a $C_4$, so that this conjecture is that $f(n)\leq (\frac{1}{2}+o(1))n2^{n-1}$.Erdős [Er91] showed that\[f(n) \geq \left(\frac{1}{2}+\frac{c}{n}\right)n2^{n-1}\]for some constant $c>0$, and wrote it is 'perhaps not hopeless' to determine $f(n)$ exactly. Brass, Harborth, and Nienborg [BHN95] improved this to\[f(n) \geq \left(\frac{1}{2}+\frac{c}{\sqrt{n}}\right)n2^{n-1}\]for some constant $c>0$.
Balogh, Hu, Lidicky, and Liu [BHLL14] proved that $f(n)\leq 0.6068 n2^{n-1}$. This was improved to $\leq 0.60318 n2^{n-1}$ by Baber [Ba12b].
A similar question can be asked for other even cycles.
See also [666] and the entry in the graphs problem collection.
Source: erdosproblems.com/86 | Last verified: January 13, 2026