# The Erdős–Simonovits degeneracy conjecture is false for all R ≥ 2 > Source: > Published: 2026-08-15 00:11:14+00:00 Fable 5 Opus 5 Christian Lewis Evolving Programs High Signal Short version from README on GitHub. See theorems.pdf and Lean verification for more info. The figure in the header shows what is known about α for our specific choice of bipartite r-degenerate graph, the layered subset graph described below. Fable and Opus developed this proof on August 1, the same day OpenAI released their ten proofs. All text beyond this point is machine written and human edited. Introduction The extremal number ex(n, H) is the largest number of edges in an n-vertex graph that contains no copy of H. Degeneracy is one measure of how dense a graph is. A graph is r-degenerate if its vertices can be deleted one at a time, in some order, such that each deletion removes at most r edges. A graph is bipartite if its vertices can be divided into two parts U and V, and every edge connects a vertex of U to a vertex of V. A triangle is not bipartite because one of its edges must connect U to U or V to V. Graphs are bipartite if they do not contain an odd cycle. When H is non-bipartite, ex(n, H) = Θ(n²), that is, its extremal number is of order n² up to a constant factor. For bipartite H, ex(n, H) = O(n^(2−α)) for some α > 0, that is, its extremal number is at most of order n^(2−α). Erdős and Simonovits proposed that α = 1/r. Because ex(n, H) is a maximum over H-free graphs, proving a lower bound in excess of the conjectured 2 − 1/r requires demonstrating a single graph that has more than n^(2 − 1/r) edges without containing a copy of H. These two criteria are in tension because having many edges is what forces copies of a fixed subgraph to appear. Result: For all r ≥ 2, the tower Hᵣ built below has ex(n, Hᵣ) = Ω(n^(2 − 1/r + ε)) with ε ≥ 1/(28r²); that is, its extremal number is at least of order n^(2 − 1/r + 1/(28r²)), in excess of the conjectured ceiling n^(2 − 1/r). The components below originate in OpenAI's result for r = 2, Chapter 10 of Ten advances in mathematics and theoretical computer science (2026), cited below as [OAI26]. Abstract A graph is r-degenerate if every induced subgraph of it has minimum degree at most r. Erdős and Simonovits conjectured that the extremal number (or Turán number) of every bipartite r-degenerate graph H satisfies \mathrm{ex}(n,H)\ =\ O\big(n^{2-\frac{1}{r}}\big). The case r = 2 was refuted by OpenAI on the morning of August 1, 2026, via a layered Hamming-ball construction. We generalize this method and prove that the conjecture fails for all r ≥ 2. For all r ≥ 2, there exists a connected bipartite graph Hᵣ of degeneracy exactly r, for which \mathrm{ex}(n,H_r)\ =\ \Omega\big(n^{\,2-\frac{1}{r}+\varepsilon}\big),\qquad \varepsilon\ \ge\ \frac{1}{28r^2}. Verification: proofs/Theorem12.lean; at r = 3, proofs/Theorem12r3.lean. We also determine that this window obeys an asymptotic law with a sharp phase transition at Gibbs weight e, and the supremal constant of its exponent gain is 1/(8r²), approached but not attained. For every δ ∈ (0,1) and every sufficiently large r there is a connected bipartite graph H₍ᵣ,δ₎ of degeneracy exactly r, for which \mathrm{ex}(n,H_{r,\delta})\ =\ \Omega\big(n^{\,2-\frac{1}{r}+\varepsilon}\big),\qquad \varepsilon\ \ge\ \frac{1-\delta}{8r^2}. Verification: proofs/Corollary14.lean. The forbidden graph The degeneracy conjecture is a claim about every bipartite r-degenerate graph, so we are free to choose any qualifying H. The graph we forbid is the layered subset tower Hᵣ. Above a root layer V₀, each layer Vᵢ₊₁ = C(Vᵢ, r) consists of all r-element subsets of the previous layer, and each subset (a child) is joined to its r elements (its parents). At r = 2 this is exactly the layered graph of [OAI26]. At r = 2, over the roots a, b, c: \begin{array}{l} V_1=\big\{\{a,b\},\{a,c\},\{b,c\}\big\},\\ V_2=\Big\{\big\{\{a,b\},\{a,c\}\big\},\ \big\{\{a,b\},\{b,c\}\big\},\ \big\{\{a,c\},\{b,c\}\big\}\Big\}. \end{array} Keeping only {a,b} and {b,c} in V₁ would also leave a 2-degenerate graph, but it would omit {a,c} and every combination containing it in later layers. Peeling the layers from the top, each vertex at its removal has no remaining neighbors other than its r parents, so the degeneracy of Hᵣ is at most r. The subgraph induced on the bottom two layers has minimum degree r, as each child keeps its r parents and each root is a parent of at least r children, so the degeneracy is at least r. The degeneracy of Hᵣ is therefore exactly r. Our tower has depth Θ(r²), while the tower of [OAI26] has constant depth. Each layer of our tower moves the entropy potential by a fixed fraction of the width of the dense exclusion window below, and at general r that window is only of order 1/r² wide, so Θ(r²) layers are needed to reach a contradiction. The sparsified Hamming host Take two copies of the cube {0,1}ᵐ, join x to y across the copies whenever their Hamming distance is at most τm, and retain each vertex independently with probability 2^(−βm). We call this exponent β the sparsity of the host. This construction is the same as that of [OAI26]. The density threshold A Hamming ball of radius τm in {0,1}ᵐ holds 2^(h(τ)m + o(m)) points, where h is the binary entropy function, h(τ) = −τ log₂ τ − (1 − τ) log₂(1 − τ). A second-moment argument shows that with high probability the retained graph has n ≈ 2^((1−β)m) vertices and n^γ edges, where γ = (1 + h(τ) − 2β)/(1 − β). Because β < 1, the requirement γ > 2 − 1/r can be rearranged as \beta\ <\ C_r(\tau)\ :=\ r\,h(\tau)-(r-1). Verification: Cᵣ, proofs/lib/LawDefs.lean; density threshold, proofs/lib/SamplingR.lean. We call this bound Cᵣ(τ) the host's density threshold, as once β exceeds it, the retained host no longer carries more than n^(2 − 1/r) edges (Lemma 2.2). At r = 2, this is the threshold 2h(τ) − 1 of [OAI26]. The entropy ceiling Suppose a copy of Hᵣ survives, and let Xᵥ denote the string at vertex v. Adjacency in this host implies Hamming distance at most τm, and so an embedded copy of Hᵣ constrains each child's string to lie near the strings of all r of its parents. The per-bit conditional entropy of a uniformly random child w of one layer, given its parents u₁, …, uᵣ in the layer below, is \eta\ =\ \tfrac{1}{m}\sum_{j=1}^{m}\mathrm{H}\big(X_w^{(j)} \mid X_{u_1}^{(j)},\dots,X_{u_r}^{(j)}\big). There is one term for each of the m coordinates, measuring what the parents' bits at that coordinate leave undetermined about the child's. A smaller τ confines the child to fewer strings once its parents are fixed, so the ceiling on η falls; a larger τ leaves more strings available, and so it rises. For the lower bound, the retained strings have density 2^(−βm). A child restricted to fewer than 2^(βm) of them would expect to find none retained, and therefore no vertex of the host to occupy. A first-moment count rules out every such embedding, so in any surviving copy of Hᵣ this conditional entropy satisfies η > β (Lemma 3.1). For the upper bound, a child lies within τm of each of its parents, so its string is confined to the intersection of r Hamming balls of radius τm. Entropy is at most the log-volume of the set over which the variable ranges. A Gibbs soft-max estimate, applied one coordinate at a time, bounds that volume, penalizing each disagreeing coordinate by the Gibbs weight 2^λ, whose exponent λ > 0 is ours to choose. This caps the entropy at the entropy ceiling Aᵣ(λ), up to a term that telescopes across layers, so a copy can survive only if \beta\ <\ A_r(\lambda)\ :=\ \lambda\tau+\sup\{\,G_r(q,v)\ :\ 0\le q,v\le 1\,\}, Verification: Aᵣ is DegeneracyLaw.Aside and Gᵣ is DegeneracyLaw.Gfun (proofs/lib/LawDefs.lean). where Gᵣ is the Gibbs objective at a single coordinate (Lemma 3.2). Above Aᵣ, the two bounds cannot both hold at a layer unless the potential increases by a fixed fraction of the window width. The tower's Θ(r²) layers therefore push it past the one bit it can hold, and no copy of Hᵣ survives (Proposition 3.3). This technique is that of [OAI26], with two changes: (1) the entropy inequality is generalized from two parents to r, and (2) the Gibbs weight, which [OAI26] fixes at 3, is kept as a free parameter 2^λ. The dense exclusion window The two thresholds divide the sparsity axis into three regimes: Below Aᵣ, the entropy argument no longer excludes Hᵣ. Above Cᵣ, the retained host is no denser than the conjecture permits. Any β in between, Aᵣ(λ) < β < Cᵣ(τ), therefore yields a host which excludes our particular Hᵣ, of degeneracy exactly r, while carrying more edges than the conjecture permits for any graph of that degeneracy. This refutes the conjecture at level r with exponent gain arbitrarily close to εᵣ^max(β) = (Cᵣ − β)/(r(1 − β)). Whether the window is nonempty is the point at which this work departs from [OAI26]. At r = 2, [OAI26] evaluates both thresholds at the single radius τ = 1/(1 + √3) and exhibits a window of positive constant width in closed form. At general r, no fixed radius succeeds: both thresholds lie at 1 − Θ(1/r), so the radius must approach τ = 1/2. The comparison therefore moves to the lower-order terms, where each threshold has an explicit expansion. At τ = 1/2 − c/r, expanding h about 1/2 puts the density threshold below 1 by an amount quadratic in the radius offset c: C_r(\tau)\ =\ r\,h(\tau)-(r-1)\ =\ 1-\frac{2c^2}{\ln2}\cdot\frac1r-O\Bigl(\frac1{r^3}\Bigr). Verification: proofs/lib/WindowLowerBound.lean, bracketing 1 − h(1/2 − x) between 2x²/ln2 and 2x²/ln2 + 3x⁴/ln2 for |x| ≤ 1/4. For the entropy ceiling, a concavity argument (Lemmas 4.1 and 4.2), valid whenever the Gibbs weight is subcritical, places the maximizer of the optimization defining Aᵣ at the center, where the Gibbs soft-max over the r parent bits collapses to a binomial log cosh average over Sᵣ = 2 Bin(r, 1/2) − r, the popcount fluctuation of r fair parent bits: A_r \;=\; \lambda\tau + 1 - \frac{\lambda}{2} \;+\; \mathbb{E}\Bigl[\log\cosh\Bigl(\frac{\lambda \ln 2}{2r}\,S_r\Bigr)\Bigr]. Verification: the center value, proofs/lib/WindowUpperBound.lean; the supremum, proofs/Lemma42.lean. Aᵣ itself, proofs/lib/LawDefs.lean. Expanding the log cosh term the same way, at second moment E[Sᵣ²] = r, the 1/r terms of the two thresholds combine into −(4c − λ ln 2)²/(8 ln 2), at most zero and zero only at c = (λ ln 2)/4. That forces the tuned radius τᵣ = 1/2 − (λ ln 2)/(4r), where the quadratic parts cancel exactly. Now ln cosh t lies below its parabola t²/2 by the quartic defect t⁴/12, and E[Sᵣ⁴] = 3r² − 2r, so the ceiling Aᵣ falls strictly below its quadratic approximation: w_r\ :=\ C_r-A_r\ =\ \frac{\lambda^4\ln^32}{64\,r^2}\Bigl(1+O(\tfrac1r)\Bigr)\ >\ 0. Verification: positivity for every r ≥ 2 at λ = 27/20, proofs/lib/AssemblyR.lean, proofs/Lemma44.lean; the asymptotic form, proofs/Theorem13a.lean. That defect, of order 1/r², is the exponent gain. Take β just inside the exclusion edge Aᵣ, which is the optimal end of the window by Theorem 1.3(b). Together with the bound wᵣ ≥ 0.00603/r² of Lemma 4.4, certified in exact rational arithmetic at λ = 27/20 for every r ≥ 2, this yields the 1/(28r²) of Theorem 1.2; the specialization w₃ ≥ 0.0098/9 gives the gain 1/160 at r = 3. Letting λ vary instead determines the limits of the method. Below the critical weight 2^λ = e the rescaled width converges, r²wᵣ → λ⁴ ln³2/64, while above it r²wᵣ → −∞ as given by Theorem 1.3(a). Theorem 1.3(b) determines the certified gain across the window; it is largest at the exclusion edge, where it approaches the supremum 1/(8r²). The schedule λᵣ = (1 − (ln r)/r)/ln 2 is subcritical for every r and critical in the limit, and for any fixed δ it recovers the ceiling up to a factor 1 − δ (Corollary 1.4). The window is nonempty for every r ≥ 2, so some β leaves the host denser than the conjecture allows while still excluding Hᵣ. The constant is set by r = 2 and no higher r does worse, so the exponent is at least 2 − 1/r + 1/(28r²), and by this method never more than 2 − 1/r + 1/(8r²). Acknowledgments We thank OpenAI for publishing their work and providing the framework used here. We also thank Sai Gajjala @publishiperishi of New York University for contributing to the Lean formalization, and Elliot Glazer @ElliotGlazer of Principia Labs for notes on the Lean development and Comparator setup.