Erdős #86 — C4-free subgraphs of the hypercube density

Statement

Let $Q_n$ be the $n$-dimensional hypercube graph ($2^n$ vertices, $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$? Equivalently, letting $f(n) = \mathrm{ex}(Q_n, C_4)$ be the max edges in a $C_4$-free subgraph of $Q_n$, the conjecture is $f(n) \leq (\tfrac12+o(1))n2^{n-1}$, i.e. the Turán density $\sigma_4 := \lim_n f(n)/e(Q_n) = 1/2$ exactly.

Facts

- Prize $100; status open (erdosproblems.com/86, reflects site-owner T.F. Bloom's belief; site flags it explicitly as *not* resolvable by finite computation since it's an asymptotic-in-$n$ statement). - Falsifiable: no in the finite-computation sense — a single finite $n$ cannot refute an "$o(1)$" claim; a disproof needs either a genuine $\liminf$ lower-bound construction beating $1/2$, or a matching-limsup proof to confirm it. (Small-$n$ exact values, e.g. Minamoto arXiv:2603.29127, only bound $f(n)$ pointwise, not $\sigma_4$.) - Origin: [Er90] (*Some of my favourite unsolved problems*, 1990), restated in [Er91],[Er92b],[Er93,p.343],[Er94b],[Er95],[Er97f] through the 1990s (per erdosproblems.com/bibs/*, all fetched directly). Also catalogued as problem #1 ("$100) in the "Extremal Graph Theory" section of the old Erdős problem-collection site, mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/TuranInCube.html (fetched directly, -k for stale CA cert). - Known bounds on $\sigma_4$ (chain of results, all independently verified): - Lower: $f(n) \geq (\tfrac12+\tfrac{c}{n})n2^{n-1}$, Erdős [Er91] itself (an explicit small perturbation). - Lower: $f(n) \geq (\tfrac12+\tfrac{c}{\sqrt n})n2^{n-1}$ for a constant $c>0$, Brass–Harborth–Nienborg [BHN95] (*J. Graph Theory* 1995) — this is presented on the site as *disproving* an earlier Erdős belief that $\sigma_4$ might equal $1/2$ with no polynomial correction term; still the best known asymptotic lower bound. - A finite-$n$ generalization of the BHN construction giving improved concrete constructions for small $n$ (not asymptotic): Brendon Stanton, "A Generalization of the Methods of Brass, Harboth, and Nieborg," arXiv:1405.5957 (2014) — generalizes to $Q_3$-free (not just $C_4$-free) subgraphs. - Older upper bound (pre-flag-algebra): Chung [Ch92] (*Subgraphs of a hypercube containing no small even cycles*, J. Graph Theory 1992) $f(n) \leq (\alpha+o(1))n2^{n-1}$, $\alpha\approx 0.623$ (root of $9\alpha^3+5\alpha^2-5\alpha-1=0$); Chung's paper is also the source establishing that the limit $\sigma_4=\lim f(n)/e(Q_n)$ exists at all (per the old mathweb TuranInCube.html page). - Upper: $f(n)\leq 0.6068\, n2^{n-1}$, Balogh–Hu–Lidický–Liu [BHLL14], *European J. Combin.* (2014), arXiv:1201.0209 — "we modify slightly Razborov's flag algebra machinery to be suitable for the hypercube" (abstract, verified). Same paper improves the $C_6$-free bound from $\sqrt2-1$ to $0.3755$. - Current best upper bound: $f(n) \leq 0.60318\, n2^{n-1}$, Rahil Baber [Ba12b], arXiv:1201.3587 ("Turán densities of hypercubes", 2012) — extends the flag-algebra/SDP method further; same paper gets $\pi(K_4^{3}) \leq 0.5615$ for 3-uniform hypergraphs as a spinoff. This is the record as of this search (no arXiv/OpenAlex/Semantic-Scholar hit found improving it since 2012). - Small-$n$ exact/near-exact values (finite, not asymptotic): $f(1){=}1,f(2){=}3,f(3){=}9,f(4){=}24,f(5){=}56$ (Emany-K–Guan–Rivera-Vega 1992, per mathweb TuranInCube.html); $f(6)=132$ exactly (ILP-proved), $f(7)\geq304$, $f(8)\geq680$ (conjectured tight) — Minamo Minamoto, arXiv:2603.29127 (submitted 31 Mar 2026), simulated-annealing + exhaustive $C_4$-enumeration certificates, code at github.com/minamominamoto/c4free-hypercube. - Gap remaining: $1/2$ (conjectured) vs. $0.60318$ (proved upper bound) — over 10 percentage points open; no polynomial-in-$n$ improvement to the lower bound beyond $c/\sqrt n$ (1995) has been found. - A similar question is open for other even cycles $C_{2k}$; see erdos/666 for the resolved $k=3$ "for every $\epsilon$" variant. - Related problems: erdos/666 (same host $Q_n$, cycle $C_6$, DISPROVED).

Literature state

Not resolved. Direct fetch of erdosproblems.com/86 confirms OPEN, "no solutions, partial or complete, claimed in the comments," last edited 27 Dec 2025.

The problem sits inside an active, ongoing research program on "Turán-type problems for the hypercube as host graph" (as opposed to the classical host $K_n$). Confirmed via arXiv + Semantic-Scholar citation-graph of Baber's paper (arXiv:1201.3587, 35 citing works checked): - The flag-algebra / semidefinite-programming machinery (Razborov's method, adapted to $Q_n$ by Balogh–Hu–Lidický–Liu 2011/2014 and extended by Baber 2012) is the tool that produced every upper-bound improvement since Chung 1992, and is the same general machine that later fully resolved other extremal problems exactly (e.g. the Erdős pentagon-count conjecture, Grzesik 2012 / Hatami–Hladký–Král'–Norine–Razborov 2013 — see Related). No one has yet pushed the SDP hierarchy for $Q_n$/$C_4$ far enough to either match $1/2$ or find the true extremal density; Baber's 2012 bound (0.60318) appears to be the record 14 years on, per this search. - A parallel, distinct research line by Maria Axenovich and collaborators (2022–2023, arXiv:2201.04598, 2211.12842, 2308.11366, 2303.15529) develops general "$\mathrm{ex}(Q_n,H)$" theory (generalized Turán numbers, "cubical"/"layered" graphs, Conlon's partite-representation zero-density criterion) but targets *other* forbidden subgraphs (longer even cycles $C_{4k+2}$, general cubical $H$) — $C_4$ itself is explicitly noted (arXiv:2303.15529 abstract) as the base case that already has *positive* Turán density (unlike e.g. $C_{12}$), so this line does not attack the exact constant $\sigma_4$ that #86 asks for. - No AI-assisted resolution found: github.com/teorth/erdosproblems wiki "AI contributions to Erdős problems" page (fetched directly, current as of 30 Jun 2026) has no entry for problem #86. The data/problems.yaml ground-truth file (teorth/erdosproblems, fetched directly) lists number: "86", status.state: open, formalized.state: no, last_update: 2025-08-31. The DeepMind formal-conjectures repo returns 404 for FormalConjectures/ErdosProblems/86.lean — not even formalized as a Lean statement, let alone proved. - A directly adjacent Erdős problem, erdos/666 (same $Q_n$, but "for every $\epsilon>0$, large $n$ $\Rightarrow$ every $\geq\epsilon n2^{n-1}$-edge subgraph contains $C_6$"), is resolved (DISPROVED, Lean-verified): Chung [Ch92] and Brouwer–Dejter–Thomassen [BDT93] give an explicit 4-part edge-partition of $Q_n$ with each part $C_6$-free, killing the "for every $\epsilon$" version for $k=3$. This is a genuine nearby win but for a *qualitatively different* question (existence of *any* positive-density $C_6$-free part vs. the *exact* extremal constant for $C_4$) — it does not transfer directly to #86, though the explicit-automorphism-based construction technique is the same family of tool used for the #86 lower bounds.

Attack surface

- Mode: literature-resolution (primary — the SDP/flag-algebra gap-closing is an active, well-defined computational-mathematics program, not blank-slate research) + derivation (extending an established recursive/SDP method) - Concrete first experiment: reproduce Baber's flag-algebra LP for $Q_n$, $C_4$-free (arXiv:1201.3587 §on hypercubes) at a higher SDP level using a modern solver (e.g. flagmatic/CSDP/SDPA, or Razborov-style Lagrangian-density LPs specialized to the $Q_n$ recursive layer structure) to see whether the 2012-era bound of 0.60318 can be pushed down with 14 years of solver/hardware improvement — this is a concrete, mechanically checkable numeric-optimization run, not a proof search. - Oracle: a tightened upper bound is a certified LP/SDP dual solution (machine-verifiable, as flag-algebra proofs are); a tightened lower bound is an explicit construction (verifiable by brute-force $C_4$-scan, as Minamoto arXiv:2603.29127 does for small $n$) that must additionally be shown to extend recursively/asymptotically (not just for one $n$) to move the $o(1)$ term. - Feasibility: closing the full gap ($1/2$ vs $0.60318$) is a genuine open extremal-graph-theory problem worked by specialists (Baber, Balogh, Lidický et al.) with no movement on the upper bound since 2012 in this search — realistically out of reach for a first pass. A tractable sub-goal: (a) rerun/extend Baber's SDP at higher level as a citable numeric artifact (does not need a new idea, just compute), or (b) attempt to shave the lower-bound correction term below $O(1/\sqrt n)$, unimproved since Brass–Harborth–Nienborg 1995 — 30 years stale, a natural place for a targeted construction search guided by Minamoto's 2026 small-$n$ computational structural data (degree sequence $\{4^{32},5^{96}\}$, rigid structural core for the $Q_7$ optimum) as a seed for a recursive/product construction.

Related

- erdos/666 — same host $Q_n$, the $C_6$ analogue of the "every subgraph with $\geq\epsilon\cdot$edges contains a short even cycle" family; DISPROVED and Lean-verified via Chung [Ch92] + Brouwer–Dejter–Thomassen [BDT93]'s explicit 4-coloring/edge-partition of $Q_n$ avoiding $C_6$ in each part. Explicitly cross-linked ("See also [86]") on erdosproblems.com/666. - Flag algebras — Razborov's SDP-based calculus for extremal graph/hypergraph densities — Razborov's semidefinite-programming method for extremal density problems; adapted to the hypercube host by Balogh–Hu–Lidický–Liu (arXiv:1201.0209) and extended by Baber (arXiv:1201.3587); the exact machine behind every upper-bound record on this problem since 2012, and the same machine that fully closed other Erdős extremal-density conjectures elsewhere (e.g. the pentagon-count problem, Grzesik 2012). - concept/turan-density-in-hypercube-host — the general "$\mathrm{ex}(Q_n,H)$" program (Axenovich et al. 2022–2023: arXiv:2201.04598, 2211.12842, 2308.11366, 2303.15529) studying which cubical subgraphs $H$ have zero vs. positive Turán density in $Q_n$; establishes $C_4$ has positive density (the easy direction of #86) via Conlon's "partite representation" criterion, but does not address the exact constant. - concept/kovari-sos-turan-theorem — the classical $C_4$-free Turán/Zarankiewicz bound for host $K_n$ (extremal examples = polarity graphs of projective planes); the natural "solved" analogue in the dense-host regime, useful as a contrast: $Q_n$'s bounded degree ($n \ll 2^n$) puts #86 in a structurally different (constant-fraction-density, not $o(1)$-density) extremal regime. - concept/explicit-automorphism-constructions — recursive/product and automorphism-group-based explicit constructions (Guan's lower bound, Brass–Harborth–Nienborg 1995, Stanton's 2014 generalization, Chung/Brouwer–Dejter–Thomassen's edge-partitions for erdos/666) — the family of tools used for every lower-bound record on this problem. - Simulated-annealing extremal search — Metropolis local search for rare, structured witness/counterexample objects — the computational-search technique (two-phase simulated annealing with $\mathrm{Aut}(Q_n)$-based diversification, plus ILP certification) used by Minamoto (arXiv:2603.29127, 2026) to get exact/near-exact $f(n)$ for $n\leq 8$; a possible seed generator for new recursive lower-bound constructions on the asymptotic problem.