Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$

Statement

If $H$ is bipartite and is $r$-degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$, then \[\mathrm{ex}(n;H) \ll n^{2-1/r}.\]

Contested status — machine-checked counterexample vs. canonical registry (flagged 2026-08-26)

Two authoritative sources contradict each other at the same date. Both are recorded here, neither is picked: on its own, neither licenses the word *solved* or the word *disproved*.

Source 1 — machine-checked counterexample, at $r=2$. Repository github.com/openai/ten-proofs (created 2026-08-05T21:07Z, pushed 2026-08-05T21:09Z, Apache-2.0, 141 stars; metadata read from api.github.com on 2026-08-26). File CompactnessAndDegeneracy.lean, 18,588 lines, 0 occurrences of `sorry` (in Lean a sorry is an admitted hole in a proof, so zero means no hole declared anywhere in the file). Theorems not_erdos_146 (line 18543) and not_erdos_180 (line 8967). The formal statement it refutes, DegeneracyConjectureStatement, quantifies over every $r>0$ and every bipartite $H$ with IsDegenerate r H — defined as: every nonempty vertex set contains a vertex of degree $\leq r$ within that set, which is the "every induced subgraph of $H$ has minimum degree $\leq r$" of the Statement above — and asserts $\mathrm{ex}(n;H) = O(n^{2-1/r})$. not_erdos_146 instantiates that statement at $r=2$ via twoDegenerateExtremalCounterexample and contradicts the resulting $n^{3/2}$ bound — i.e. it lands on exactly the case erdosproblems.com singles out as the hard one ("Open even for $r=2$"). The verified theorem is about $r=2$; nothing here extends it to general $r$.

Source 2 — the canonical registry has not taken it up. www.erdosproblems.com/146, direct fetch with a browser User-Agent on 2026-08-26, HTTP 200: badge "OPEN (LEAN)", prize \$500, "This page was last edited 18 January 2026", "0 claimed proofs for this problem", "There are no solutions, partial or complete, claimed in the comments." So the \$500 is neither claimed nor awarded. The site states of itself: "The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of."

What this leaves. status: contested — a formal artefact that has not been reconciled with the registry that keeps score. A reader can check both in under a minute: open the .lean file and search not_erdos_146; open /146 and read the badge and the last-edited date. This resolves when one side moves: the registry changes its badge, or the certificate is withdrawn or found defective.

Facts

- Prize \$500; status OPEN (erdosproblems.com/146, direct fetch 2026-07-02) — "cannot be resolved with a finite computation" (site-owner tag). Cross-checked against teorth/erdosproblems/data/problems.yaml entry number: 146 — status.state: open, last_update: 2025-08-31, formalized.state: no, oeis: N/A. - Falsifiable: no in the finite sense — this is a $\forall H,\,\forall r$ asymptotic-growth claim; a counterexample would be a specific $r$-degenerate bipartite $H$ for which one *proves* $\mathrm{ex}(n;H) = \omega(n^{2-1/r})$, which itself requires a proof (typically an explicit/algebraic lower-bound construction), not a finite search. - Origin: Erdős's original 1967 conjecture (per the UCSD problem-collection page, mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/TuranDegenerate.html, read directly), formalized in print by Erdős and Simonovits, "Cube-supersaturated graphs and related problems" [ErSi84] (1984), and restated by Erdős in [Er91], [Er93], [Er97c] (all bib entries read directly at erdosproblems.com/bibs/*). Tagged "#43 in Extremal Graph Theory" in the UCSD Erdős problem collection. - Explicitly noted OPEN EVEN FOR $r=2$ on erdosproblems.com/146 (i.e. the case "2-degenerate bipartite $H$ $\Rightarrow$ $\mathrm{ex}(n;H)=O(n^{3/2})$" is itself unresolved in full generality). - Known results / best bounds: - Alon, Krivelevich, Sudakov [AKS03], "Turán numbers of bipartite graphs and related Ramsey-type questions," *Combin. Probab. Comput.* 12 (2003), 477–494 — proved the general weakened bound $\mathrm{ex}(n;H) \ll n^{2-1/(4r)}$ for every $r$-degenerate bipartite $H$ (universal constant in the exponent loss), and proved the full conjectured bound $\mathrm{ex}(n;H) \ll n^{2-1/r}$ in the special case that $H$ is bipartite with maximum degree $r$ in one side of the bipartition (both facts stated on erdosproblems.com/146 and confirmed on the UCSD page). The one-sided-degree case reduces to (a generalization of) the Kővári–Sós–Turán bound for $K_{r,t}$. - Grzesik, Janzer, Nagy, "The Turán number of blow-ups of trees," arXiv:1904.07219 (2019) — prove the full $O(n^{2-1/r})$ bound for a large family of $r$-degenerate bipartite $H$, including all $r$-degenerate blow-ups of trees, generalizing Füredi's and AKS03's cases. Technique: supersaturation + a random walk on an auxiliary graph. - Jiang, Longbrake, "Tree-degenerate graphs and nested dependent random choice," arXiv:2201.10699 (2022) — introduce a *nested* dependent-random-choice lemma and use it to give a common extension of the Füredi/AKS03 one-sided-degree theorem and the Grzesik–Janzer–Nagy tree-blow-up theorem, for the class of "tree-degenerate" graphs; also connects to Sidorenko-type results (Conlon–Fox–Sudakov). - No paper found that resolves the conjecture for general $r$-degenerate $H$, nor even for general $r=2$ (literature sweep of 2026-07-02). This still holds for *papers*; it no longer holds for *artefacts*: on 2026-08-26 a machine-checked Lean file was found asserting a counterexample at $r=2$, unrecognised by the canonical registry — see Contested status above. - Adjacent conjectures that HAVE been disproved (important non-hit for #146 itself): - Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 — the biconditional "$\mathrm{ex}(n;G)\ll n^{3/2} \iff G$ is 2-degenerate" — disproved by Oliver Janzer, arXiv:2109.06110 [Ja23b] (2021/2023, *IMRN*), who constructed, for every $\varepsilon>0$, a 3-regular (hence not 2-degenerate) bipartite $H$ with $\mathrm{ex}(n;H)\ll n^{4/3+\varepsilon}$ — disproving the "$\Leftarrow$"-direction-adjacent claim that small Turán exponent forces 2-degeneracy. A shorter, independent disproof was later given by Dong, Gao, Liu, "Bipartite Turán problems via graph gluing," arXiv:2501.12953 (Jan 2025), via a graph-gluing equivalence to a Zarankiewicz-type question of Erdős–Simonovits. This does not touch #146's own direction ($r$-degenerate $\Rightarrow O(n^{2-1/r})$), which Janzer's counterexample graph is consistent with (it is not 2-degenerate, so is not a counterexample to #146 at $r=2$). - Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ — the companion lower-bound conjecture (min-degree-$r$ bipartite $H$ $\Rightarrow$ $\mathrm{ex}(n;H) \gg n^{2-1/(r-1)+\varepsilon}$) — disproved by Janzer for even $r\geq4$ [Ja23], and for $r=3$ by [Ja23b] (same construction as the #113 disproof). - Related problems: Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021, Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ (both erdosproblems.com "See also" cross-links, verified) — same Erdős–Simonovits 1981/1984 paper, same bipartite-degeneracy Turán program, but the two adjacent directions have both fallen to Janzer's explicit constructions while #146's own direction withstood them in the literature — it is now contested since 2026-08-05 by an unreconciled machine-checked counterexample at $r=2$ (see Contested status above), not by a construction of that kind.

Literature state

Fully open as of 2026-07-02, confirmed at that date by three independent sources (superseded in part: see Contested status above — on 2026-08-26 a machine-checked Lean counterexample at $r=2$ stands unreconciled against a canonical registry that still reads OPEN): (1) erdosproblems.com/146's own OPEN badge and disclaimer, (2) the teorth/erdosproblems community-maintained YAML database (status.state: open, last touched 2025-08-31, not in Lean), (3) no hit for problem #146 in the "AI contributions to Erdős problems" wiki. The strongest general upper bound remains AKS03's 2003 result $\mathrm{ex}(n;H)=O(n^{2-1/(4r)})$ — a constant-factor loss in the exponent that has stood for over 20 years for the fully general case. What *has* moved since 2003 is the set of special families for which the sharp $O(n^{2-1/r})$ bound is now proven: one-sided bounded degree (AKS03 itself), $r$-degenerate blow-ups of trees (Grzesik–Janzer–Nagy 2019, arXiv:1904.07219), and the broader "tree-degenerate" class via nested dependent random choice (Jiang–Longbrake 2022, arXiv:2201.10699). This is a live, incrementally-advancing research program (three papers across 2003/2019/2022 each strictly generalizing the last), but no paper claims or approaches the fully general conjecture. Crucially, the *closely adjacent* conjectures on the same problem page's neighborhood — erdos/113 (the $r=2$ biconditional) and erdos/147 (the companion lower-bound conjecture) — were both disproved by Oliver Janzer in 2021–2023 via explicit/algebraic constructions (arXiv:2109.06110, plus the rainbow-Turán paper for the even-$r\geq4$ case of #147), with a second independent disproof of #113 via graph-gluing by Dong–Gao–Liu in Jan 2025 (arXiv:2501.12953). None of these disproofs is a counterexample to #146 itself — Janzer's graphs are witnesses that *low Turán exponent does not imply low degeneracy* (the reverse direction), not that *low degeneracy fails to imply low Turán exponent* (#146's actual direction) — but they establish that Janzer-style explicit/algebraic constructions are the sharp tool in this exact neighborhood of the Turán-degeneracy landscape, and that the "easy-looking" implication direction (#146) had specifically resisted that technique up to the 2026-07-02 literature sweep. What contests it now is not a paper of that lineage but a Lean artefact (2026-08-05), which is why the two are recorded separately above. Separately, a distinct but related "rational exponents" conjecture of Erdős–Simonovits (does every rational $r\in(1,2)$ occur as a Turán exponent?) has seen substantial 2018–2026 progress (Bukh–Conlon random-algebraic construction; Conlon–Janzer "Rational exponents near two," *Adv. Comb.* 2022; Dong–Gao–Li–Liu and Jiang–Longbrake's 2025/2026 induced-setting extensions, arXiv:2506.09020, arXiv:2604.05288) — this is a sibling research vein using the same toolkit (random algebraic / norm-graph constructions for lower bounds, dependent random choice / supersaturation for upper bounds) but is a formally different conjecture from #146.

Attack surface

- Mode: literature-resolution (read Grzesik–Janzer–Nagy 2019 and Jiang–Longbrake 2022 in full to map exactly which degeneracy/tree structures are covered, and whether their "nested dependent random choice" machinery has a natural next generalization) + derivation (the real prize-worthy move is closing the AKS03 exponent gap $n^{2-1/(4r)}\to n^{2-1/r}$ in general, or finding the general-$r$ analogue of the Grzesik–Janzer–Nagy random-walk argument that removes the tree-blow-up restriction). - Concrete first experiment: not a finite-computation problem (falsifiability: not-finite). The closest thing to a "runnable" experiment is on the *disproof* side by analogy with Janzer's method: take the general $r$-degenerate bipartite $H$ closest in spirit to Janzer's 3-regular counterexample (from arXiv:2109.06110) but chosen to actually be a candidate falsifier of #146 (i.e. keep it genuinely $r$-degenerate and try to push its Turán number growth rate above $n^{2-1/r}$ via the same "generalized theta-graph"/algebraic-construction toolkit) — and separately, computationally estimate $\mathrm{ex}(n;H)$ for small concrete $r$-degenerate $H$ (e.g. via SAT/ILP extremal-graph search for small $n$) purely as intuition-building, understanding this cannot itself prove the asymptotic claim. - Oracle: none mechanical for the general conjecture (asymptotic upper/lower bound proof required, not a finite check); for the special-case literature (blow-ups of trees, tree-degenerate graphs) correctness would need to be checked against the Grzesik–Janzer–Nagy / Jiang–Longbrake papers directly, or eventually against a Lean formalization (none per teorth/erdosproblems.yaml formalized.state: no, checked 2026-07-02; but on 2026-08-26 a third-party Lean file — openai/ten-proofs, CompactnessAndDegeneracy.lean, theorem not_erdos_146, 0 sorry — was found to contain both the formal statement and a refutation of it at $r=2$, see Contested status). - Feasibility: honest read: famous-and-hard, but with real derivation fuel nearby. This stood open from 1967 for nearly 60 years and is contested since 2026-08-05 by an unreconciled machine-checked counterexample at $r=2$ (see Contested status above), the general bound hasn't moved past AKS03 (2003) despite three follow-up papers narrowing special cases, and it sits in the same research neighborhood as two sibling conjectures that *were* recently resolved (by disproof) using explicit/algebraic constructions — meaning the toolkit (dependent random choice + supersaturation for upper bounds; Bukh–Conlon-style random algebraic constructions for lower bounds/counterexamples) is actively being sharpened on this exact family of problems as of 2022–2026. Not a quick win, but a legitimate target for "apply Janzer/Bukh–Conlon machinery to the direction no published construction has toppled" derivation, analogous to the SekaiCTF apbq/Herrmann–May-style wall-cracking pattern (recombining recent, adjacent, technique-rich literature rather than starting from scratch).

Related

- Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 — the $r=2$ biconditional companion conjecture from the same [ErSi84] paper; disproved by Janzer (arXiv:2109.06110) and independently by Dong–Gao–Liu (arXiv:2501.12953); shares the exact bipartite-degeneracy-vs-Turán-exponent setting but is the reverse implication. It fell to a published construction; #146 is instead contested since 2026-08-05 by an unreconciled machine-checked counterexample at $r=2$, which is a different kind of evidence and is recorded as such. - Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ — the companion lower-bound conjecture (min-degree $r$ forces a Turán-number lower bound); disproved for $r\geq3$ by Janzer (arXiv:2109.06110, arXiv:2006.01062 [Ja23]). - Turán number ex(n,H): extremal edge-count for forbidden subgraphs — $\mathrm{ex}(n;H)$, the core extremal quantity of the whole problem family. - r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal) — $r$-degeneracy (every induced subgraph has a vertex of degree $\leq r$), the structural hypothesis on $H$. - Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts — the workhorse upper-bound technique behind Füredi's and AKS03's results and the Jiang–Longbrake "nested" generalization (arXiv:2201.10699). - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — combined with a random-walk argument in Grzesik–Janzer–Nagy's proof for tree blow-ups (arXiv:1904.07219). - Random algebraic construction (Bukh; Bukh–Conlon) — random low-degree polynomials over $\\mathbb F_q$ for Turán lower bounds — the Bukh–Conlon-style algebraic/explicit-construction toolkit used to produce sharp lower-bound (Turán-exponent-realizing) graphs, and the same family of techniques Janzer used to disprove erdos/113 and erdos/147. - Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s}) — Kővári–Sós–Turán bound for $K_{r,t}$-free graphs, the base case AKS03's one-sided-degree result generalizes. - Erdős–Simonovits rational exponents conjecture — every rational in [1,2] is a Turán exponent — the sibling Erdős–Simonovits conjecture (every rational $r\in(1,2)$ realized as a Turán exponent), sharing the same technique toolkit and under active 2018–2026 progress (arXiv:1806.02838, Conlon–Janzer *Adv. Comb.* 2022, arXiv:2506.09020, arXiv:2604.05288). - Machine formalization of infinitary combinatorics proofs (Isabelle/HOL, Lean) — the canonical databases carry no Lean formalization for #146 (teorth/erdosproblems/data/problems.yaml, formalized.state: no, checked directly 2026-07-02, and erdosproblems.com/146 still badged OPEN (LEAN) on 2026-08-26); a third-party one exists and is unrecognised by them (openai/ten-proofs, CompactnessAndDegeneracy.lean, not_erdos_146, 0 sorry) — see Contested status.