Degenerate Turán conjecture: does $r$-degenerate bipartite $H$ force $\mathrm{ex}(n;H)\ll n^{2-1/r}$? (Erdős #146)
Statement
For a graph $H$, let $\mathrm{ex}(n;H)$ be the Turán number: the maximum number of edges in an $n$-vertex graph containing no copy of $H$ as a subgraph. Call $H$ $r$-degenerate if every subgraph of $H$ has a vertex of degree at most $r$ (equivalently, every induced subgraph of $H$ has minimum degree $\leq r$). Conjecture (Erdős–Simonovits): if $H$ is bipartite and $r$-degenerate, then $$\mathrm{ex}(n;H)\ll n^{2-1/r},$$ i.e. there is a constant $C=C(H)$ with $\mathrm{ex}(n;H)\leq C\,n^{2-1/r}$ for all $n$.
Acceptance. FULLY RESOLVES: a complete proof that $\mathrm{ex}(n;H)\ll n^{2-1/r}$ for every $r$-degenerate bipartite $H$ (machine-checkable Lean/Coq preferred, else a full written proof with all steps); OR a disproof — a specific $r$-degenerate bipartite $H$ together with a proof (a construction of $H$-free graphs) that $\mathrm{ex}(n;H)\gg n^{2-1/r+\delta}$ for some fixed $\delta>0$. ADVANCES, each with proof: prove the conjecture in the first open case $r=2$; improve the general exponent strictly beyond the best bound stated in the background, the Alon–Krivelevich–Sudakov bound $n^{2-1/(4r)}$, for all $r$; or establish the full exponent $2-1/r$ for a new natural class of degenerate bipartite $H$ (beyond bounded one-sided maximum degree). Deliver the proof, or the improved-exponent theorem with its complete proof.
Background
Conjectured by Erdős and Simonovits [ErSi84]; Erdős offered \$500 for a solution. The conjecture is a sweeping unification of bipartite Turán bounds (it would subsume the Kővári–Sós–Turán bound for complete bipartite $H$ and much more) and is open even in the first nontrivial case $r=2$. The best general result is due to Alon, Krivelevich, and Sudakov [AKS03], who proved the weaker bound $\mathrm{ex}(n;H)\ll n^{2-1/(4r)}$ for every $r$-degenerate bipartite $H$; they also proved the FULL conjectured exponent $2-1/r$ under the stronger hypothesis that $H$ is bipartite with maximum degree $r$ on one side of its bipartition. Matching lower-bound constructions show the exponent $2-1/r$ cannot in general be lowered, so the conjecture is about the exact exponent. Related: Erdős #113 and #147 (erdosproblems.com/113, erdosproblems.com/147); this is #43 in the Extremal Graph Theory problem collection. Listed as open on erdosproblems.com/146 (fetched 2026-07-13, status 'open'), tagged graph theory | turan number. Attacker's tool: extremal graph theory — dependent random choice (the Alon–Krivelevich–Sudakov method), norm and counting inequalities, and explicit algebraic or random constructions for matching lower bounds; the frontier is closing the exponent gap from $2-1/(4r)$ toward $2-1/r$. This is a proof problem, though the bound can be probed computationally for specific small degenerate $H$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #146 (T. F. Bloom) | website |
| REF-02 | Extremal Graph Theory collection #43 — degenerate Turán conjecture | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.