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}.\]

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$. - 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 has not.

Literature state

Fully open, confirmed by three independent sources as of 2026-07-02: (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) has specifically resisted the technique that felled its neighbors. 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 currently exists per teorth/erdosproblems.yaml formalized.state: no). - Feasibility: honest read: famous-and-hard, but with real derivation fuel nearby. This has been open since 1967 (nearly 60 years), 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 one remaining un-toppled direction" 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, and it fell while #146 has not. - 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) — no Lean formalization exists yet for #146 (teorth/erdosproblems/data/problems.yaml, formalized.state: no, checked directly).