Lewis 🇺🇸 on X: "https://t.co/HnGLdOCgBu" / X<br>Post

Log inSign up

Post

Lewis 🇺🇸

@ctjlewis

The Erdős–Simonovits degeneracy conjecture is false for all r ≥ 2<br>Fable 5 Opus 5 Christian Lewis<br>Evolving Programs High Signal<br>Short version from README on GitHub. See theorems.pdf and Lean verification for more info.<br>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.<br>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.<br>Introduction<br>The extremal number ex(n, H) is the largest number of edges in an n-vertex graph that contains no copy of H.<br>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.<br>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.<br>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.<br>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.<br>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).<br>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].<br>Abstract<br>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<br>\mathrm{ex}(n,H)\ =\ O\big(n^{2-\frac{1}{r}}\big).<br>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.<br>For all r ≥ 2, there exists a connected bipartite graph Hᵣ of degeneracy exactly r, for which<br>\mathrm{ex}(n,H_r)\ =\ \Omega\big(n^{\,2-\frac{1}{r}+\varepsilon}\big),\qquad \varepsilon\ \ge\ \frac{1}{28r^2}.<br>Verification: proofs/Theorem12.lean; at r = 3, proofs/Theorem12r3.lean.<br>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<br>\mathrm{ex}(n,H_{r,\delta})\ =\ \Omega\big(n^{\,2-\frac{1}{r}+\varepsilon}\big),\qquad \varepsilon\ \ge\ \frac{1-\delta}{8r^2}.<br>Verification: proofs/Corollary14.lean.<br>The forbidden graph<br>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].<br>At r = 2, over the roots a, b, c:<br>\begin{array}{l}<br>V_1=\big\{\{a,b\},\{a,c\},\{b,c\}\big\},\\<br>V_2=\Big\{\big\{\{a,b\},\{a,c\}\big\},\ \big\{\{a,b\},\{b,c\}\big\},\ \big\{\{a,c\},\{b,c\}\big\}\Big\}.<br>\end{array}<br>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.<br>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.<br>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.<br>The sparsified Hamming host<br>Take two copies of the cube {0,1}ᵐ, join x to y across the copies...