# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/86.lean).

## 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](https://doi.org/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](https://doi.org/10.1016/j.disc.2008.02.015)
3. R. Baber, Turán densities of hypercubes (2012). [arXiv:1201.3587](https://arxiv.org/abs/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](https://doi.org/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](https://arxiv.org/abs/2603.29127)

## Source

Imported from [Erdős Problems 86](https://www.erdosproblems.com/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.