Turán density of $C_4$ in the hypercube: does $(1/2+o(1))n2^{n-1}$ edges force a $C_4$? (Erdős #86)
Statement
Let $Q_n$ be the $n$-dimensional hypercube graph, with $2^n$ vertices (the binary strings of length $n$) and $n2^{n-1}$ edges (pairs of strings differing in one coordinate). Is it true that every subgraph of $Q_n$ with at least $$\left(\tfrac12+o(1)\right)n2^{n-1}$$ edges contains a $4$-cycle $C_4$? Equivalently, writing $f(n)$ for the maximum number of edges in a $C_4$-free subgraph of $Q_n$, is $f(n)\leq\left(\tfrac12+o(1)\right)n2^{n-1}$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else full written) that $f(n)=(\tfrac12+o(1))n2^{n-1}$ — the $C_4$-free edge-density coefficient tends to $1/2$ — OR a disproof: a construction plus proof that $\limsup_n f(n)/(n2^{n-1})>1/2$. ADVANCES: lower the upper-bound coefficient strictly below the best stated in the background ($0.60318\,n2^{n-1}$, Baber) with a verifiable flag-algebra / SDP certificate; OR improve the lower-order term of the lower bound beyond Brass–Harborth–Nienborg's $(\tfrac12+c/\sqrt{n})$ via an explicit construction and proof; OR extend the exact sequence $f(n)$ (maximum edges in a $C_4$-free subgraph of $Q_n$) to a new record $n$ by ILP/exhaustive search with a reproducible program and exhaustiveness certificate. Deliver the proof file, the SDP certificate, the explicit construction plus proof, or the search code plus certified values.
Background
Erdős's Turán-type problem for $C_4$ in the cube [Er90; Er91; Er92b; Er93, p.343; Er94b; Er95; Er97f]; he offered a prize of $100 for its solution. Lower bounds: Erdős [Er91] showed $f(n)\geq(\tfrac12+c/n)n2^{n-1}$ for some $c>0$ and remarked it is 'perhaps not hopeless' to determine $f(n)$ exactly; Brass, Harborth, and Nienborg [BHN95] improved this to $f(n)\geq(\tfrac12+c/\sqrt{n})n2^{n-1}$. Upper bounds via flag algebras: Balogh, Hu, Lidický, and Liu [BHLL14] proved $f(n)\leq 0.6068\,n2^{n-1}$, improved by Baber [Ba12b] to $f(n)\leq 0.60318\,n2^{n-1}$. The conjecture asserts the leading coefficient tends to $1/2$; the current gap is between $1/2$ from below (matched up to lower-order terms) and $0.60318$ from above. Analogous questions can be posed for other even cycles. Listed as open on erdosproblems.com/86 (fetched 2026-07-13, status 'open', tagged 'graph theory'); related to erdosproblems.com/666. The attacker's tool: flag-algebra / semidefinite-programming certificates to lower the upper-bound coefficient below 0.60318, explicit or computer-searched constructions to raise the lower-order term, and ILP/exhaustive search to extend the exact values $f(n)$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #86 (T. F. Bloom) | website |
| REF-02 | OEIS A245762 — maximum number of edges in a $C_4$-free subgraph of the hypercube graph $Q_n$ | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.