AI-Assisted Proof Disproves Erdős's Degeneracy Conjecture in Graph Theory
ctjlewis · x · 2026-08-02
A major breakthrough in AI-assisted mathematical proof has successfully disproved the famous Erdős's degeneracy conjecture.
The conjecture posited that for an $r$-degenerate bipartite graph $H$, its extremal function satisfies $ex(n;H) \ll n^{2-1/r}$. However, the new proof demonstrates that this fails for every $r \ge 2$: for each $r$, there exists an $r$-degenerate bipartite graph $Hr$ such that $ex(n;Hr) \ge n^{2-1/r+\epsilonr}$ (where $\epsilonr \sim 1/(16r^2)$). This result is derived via an exact $1/r$ cancellation between binomial variance and entropy curvature at a specific Gibbs weight and Hamming radius. For instance, at $r=3$, $ex(n;H) \ge n^{5/3+1/200}$.
Related event: AI-Assisted Proof Refutes Classic Erdős Degeneracy Conjecture(2 posts)→
More from Research
- Semantic map indexes 66,000 podcasts and 700,000 ideas — g_pal · 2026-08-04
- Mila highlights African-language LLM work at Deep Learning Indaba in Lagos — Mila_Quebec · 2026-08-04
- Paper says selective parameter freezing may cut lifelong pretraining costs — ttkciar · 2026-08-04
- Epoch AI’s MirrorCode benchmark sees Claude Fable solve C preprocessor and Pkl tasks — Jsevillamol · 2026-08-04
- A NeurIPS joke says authors waiting for rebuttals are basically Waiting for Godot — MelMitchell1 · 2026-08-04
- Researcher says RLVR gains on noisy labels are spurious, not real model improvement — StellaLisy · 2026-08-04