Four-cycle-free subgraphs of the hypercube

The $n$-dimensional hypercube $Q_n$ is full of 4-cycles: every pair of coordinate directions spans many squares. How many of its edges can one keep while destroying all of them? Taking about half of the edges is easy; Erdős conjectured that one cannot do substantially better, and offered $100 for a proof.

Problem

Let $Q_n$ be the hypercube graph on $\{0,1\}^n$, in which two vertices are adjacent when they differ in exactly one coordinate; it has $2^n$ vertices and $n2^{n-1}$ edges. Let $f(n)$ be the largest number of edges of a subgraph of $Q_n$ that contains no cycle of length 4. Is it true that

$$f(n)\le\left(\frac12+o(1)\right)n\,2^{n-1}\,?$$

Background

Erdős raised the question around 1990 and wrote that determining $f(n)$ exactly is "perhaps not hopeless". It is a Turán-type problem inside a fixed host graph, and the same question can be asked for longer even cycles. The best upper bounds come from Razborov's flag-algebra method adapted to the hypercube, while the lower bounds come from explicit constructions, so both directions are open to computer-assisted work.

What is known

• Lower bounds. Erdős showed $f(n)\ge\left(\frac12+\frac cn\right)n2^{n-1}$ for a constant $c>0$, and Brass, Harborth and Nienborg (1995) improved this to $f(n)\ge\left(\frac12+\frac{c}{\sqrt n}\right)n2^{n-1}$.
• Upper bounds. Thomason and Wagner (2009) proved $f(n)\le(0.6226+o(1))\,n2^{n-1}$, slightly improving an earlier bound of Chung. Razborov's flag-algebra method, adapted to the hypercube, then gave $f(n)\le 0.6068\,n2^{n-1}$ (Balogh, Hu, Lidický and Liu; preprint 2011, published 2014) and $f(n)\le 0.60318\,n2^{n-1}$ (Baber, 2012), still the best bound.
• Small cubes. Since every edge of $Q_n$ lies in exactly $n-1$ of its $2n$ subcubes of dimension $n-1$, averaging gives $f(n)\le\frac{2n}{n-1}f(n-1)$, so $f(n)/(n2^{n-1})$ is non-increasing and exact values in small dimensions bound the limit. Harborth and Nienborg found $f(6)=132$; Minamoto (2026) constructed $C_4$-free subgraphs with $304$ edges in $Q_7$ and $682$ edges in $Q_8$, so $304\le f(7)\le 308$. Explicit edge lists for dimensions $9$ to $15$ have been posted on the problem's forum.

What would count as progress

• A proof that $f(n)\le(c+o(1))n2^{n-1}$ for some $c<0.60318$, for example a flag-algebra certificate with exact rational entries that can be checked independently.
• A construction showing $f(n)\ge(\frac12+\varepsilon)n2^{n-1}$ for a fixed $\varepsilon>0$ and all large $n$, which would disprove the conjecture.
• The exact value of $f(7)$, now pinned to $304\le f(7)\le 308$, or of $f(8)$, with certificates of optimality.
• A formal proof against the Lean statement in formal-conjectures.

References

1. P. Brass, H. Harborth and H. Nienborg, On the maximum number of edges in a $C_4$-free subgraph of $Q_n$, J. Graph Theory 19 (1995), 17–23. doi:10.1002/jgt.3190190104
2. A. Thomason and P. Wagner, Bounding the size of square-free subgraphs of the hypercube, Discrete Math. 309 (2009), 1730–1735. doi:10.1016/j.disc.2008.02.015
3. R. Baber, Turán densities of hypercubes (2012). arXiv:1201.3587
4. J. Balogh, P. Hu, B. Lidický and H. Liu, Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube, European J. Combin. 35 (2014), 75–85. doi:10.1016/j.ejc.2013.06.003
5. M. Minamoto, $C_4$-free subgraphs of the hypercubes $Q_6$, $Q_7$ and $Q_8$ (2026). arXiv:2603.29127

Source

Imported from Erdős Problems 86, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.