Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$

Statement

If $H$ is bipartite with minimum degree $r$, then there exists $\epsilon=\epsilon(H)>0$ such that $$\mathrm{ex}(n;H) \gg n^{2-\frac{1}{r-1}+\epsilon}.$$

Conjectured by Erdős and Simonovits [ErSi84] (1984), restated in [Er93], [Er97c]. It was meant as a converse to Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ (the still-open claim that $r$-degenerate bipartite $H$ forces the *upper* bound $\mathrm{ex}(n;H)\ll n^{2-1/r}$): the hope was that a high-min-degree bipartite graph should be forced to be "Turán-expensive" — i.e. that avoiding $H$ costs you close to $n^2$ edges — with the exponent $2-1/(r-1)$ chosen to sit strictly above the trivial general bound. (erdosproblems.com/147)

Facts

- Status: DISPROVED (erdosproblems.com/147; cross-checked against teorth/erdosproblems/data/problems.yaml entry number: "147" → status.state: disproved, last_update: 2025-08-31, formalized.state: no). Prize tag on the site: \$500. Not formalized in Lean. - The general (weak, always-true) lower bound: a simple application of the probabilistic deletion method shows that for every bipartite $H$ with minimum degree $r\ge2$ there is some $\varepsilon=\varepsilon(H)>0$ with $\mathrm{ex}(n;H)=\Omega(n^{2-2/r+\varepsilon})$ (stated on erdosproblems.com/147 and proved in [Ja23], §1.3). Since $2/r>1/(r-1)$ for every $r\ge3$, this weaker bound is numerically *below* what Erdős–Simonovits conjectured — the whole content of the conjecture was that the trivial deletion bound could be improved to $2-1/(r-1)$. - Disproved for every even $r\ge4$ by Oliver Janzer, "Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles," arXiv:2006.01062, *Israel J. Math.* 253 (2023), 813–840 [Ja23]. This paper's Theorem 1.15 (on $\mathrm{ex}(n,C_{2k}[m])$ for blow-ups of even cycles) is the engine; Conjecture 1.16 in the paper is exactly Erdős–Simonovits' conjecture, in the paper's own $s$-for-min-degree notation. - Disproved for $r=3$ by Oliver Janzer, "Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3," arXiv:2109.06110, *Int. Math. Res. Not.* (2023), 8478–8494 [Ja23b]. This is a *different* explicit graph family (not a blow-up of a cycle), needed because the even-$r$ blow-up construction is inherently even-regular. - Genuinely open remainder: odd $r\ge5$. Janzer's own Conjecture 6.3 in [Ja23] proposes that for every odd $s\ge3$ and $\delta>0$ there is an $s$-regular $H$ with $\mathrm{ex}(n,H)=O(n^{2-2/s+\delta})$ — i.e. that the trivial deletion lower bound is *tight*, hence #147 is false for all $r\ge3$ — but [Ja23] proves this only for even $s$ ($s=2m$, via the blow-up), and [Ja23b] separately settles only $s=3$. $r=5,7,9,\dots$ remain unconfirmed as of the last database update (2025-08-31); no paper found closing this gap. - Companion/adjacent problems, same [ErSi84] paper, all cross-linked on erdosproblems.com/147 as "See also": Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 (also disproved, by literally the *same* $r=3$ graph from [Ja23b] — see Solution below), Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ (the reverse-direction upper-bound conjecture, still open), and erdos/714 (Zarankiewicz-type conjecture $\mathrm{ex}(n;K_{r,r})\gg n^{2-1/r}$, still open for $r\ge4$ — the special case of a min-degree-$r$ lower-bound question for the single graph $H=K_{r,r}$, distinct from and not settled by #147's disproof).

Solution

Answer: false. For every $r\ge3$ except (as far as is known) odd $r\ge5$, there exist explicit bipartite $H$ of minimum degree $r$ with $\mathrm{ex}(n;H)=O(n^{2-2/r+\delta})$ for every $\delta>0$ — strictly below the conjectured threshold $n^{2-1/(r-1)+\varepsilon}$, since $2-2/r<2-1/(r-1)$ for all $r\ge3$ (e.g. at $r=4$: achieved $O(n^{3/2+\delta})$ beats the would-be-required $\Omega(n^{5/3+\varepsilon})$). Two constructions, two papers, one shared underlying machine.

1. Even $r=2m\ge4$: blow-ups of long even cycles [Ja23]. For a graph $F$, the $m$-fold blow-up $F[m]$ replaces every vertex of $F$ by an independent set of size $m$ and every edge by a complete bipartite $K_{m,m}$. Take $H=C_{2k}[m]$, the $m$-blow-up of a long even cycle $C_{2k}$: this graph is exactly $2m$-regular, so it has minimum degree $r=2m$. Janzer's Theorem 1.15 bounds $\mathrm{ex}(n,C_{2k}[m])=O\!\big(n^{2-\frac1{m+1}+\frac{4k}{m(k+m-1)}}(\log n)^{\cdot}\big)$; crucially, for *fixed* $m$ and $k\to\infty$ the extra term can be driven below any $\delta>0$, giving $\mathrm{ex}(n,C_{2k}[m])=O(n^{2-1/m+\delta})$ for $k$ large enough — i.e. $O(n^{2-2/r+\delta})$ in terms of the min degree $r=2m$. Plugging in: a $2m$-regular graph with a Turán number this small directly falsifies Conjecture 1.16 (= #147) for every even $r\ge4$.

2. Odd $r=3$: an explicit twisted-ladder graph [Ja23b]. The blow-up trick can't reach odd min degree ($C_{2k}[m]$ is always even-regular), so Janzer built a genuinely different, hand-designed 3-regular family $H_{k,\ell}$: take vertices $x_{i,j}$ for $1\le i\le4k,\ 1\le j\le2\ell$ (indices mod $2\ell$ in $j$), with edges forming (a) $2k$ disjoint "rungs" $x_{2i-1,j}x_{2i,j}$ at each $j$, (b) two boundary cycles closing up $x_{1,j}x_{1,j+1}$ and $x_{4k,j}x_{4k,j+1}$, and (c) "diagonal" cross-edges $x_{2i,j}x_{2i+1,j+1}$ and $x_{2i+1,j}x_{2i,j+1}$ — a twisted cyclic ladder / generalized prism on $4k$ "rows" and $2\ell$ "columns," 3-regular by construction. Theorem 1.6: for $k\ge1/\varepsilon$, $\ell\ge16k/\varepsilon$, $\mathrm{ex}(n,H_{k,\ell})=O(n^{4/3+\varepsilon})$ — and the probabilistic deletion method shows this is *exponent-optimal* (no 3-regular $H$ can do better than $\Omega(n^{4/3+\delta})$), so $H_{k,\ell}$ is a best-possible counterexample, not just any counterexample. Since $r=3$ gives conjectured-required exponent $2-1/(3-1)=3/2$, and $4/3<3/2$, this falsifies #147 at $r=3$.

3. The transferable technique — supersaturation + homomorphism-vs-embedding conflict counting. Both papers, despite using different graph families, share one proof engine (Janzer's own "Overview of the proof," §1.1 of [Ja23b]), and it is *this* — not either specific graph — that later problems should borrow: - Step 1 (cheap): get abundance via supersaturation, not embedding. If a graph $G$ has $n^{2-1/r+\varepsilon}$ edges — far more than the Turán number of a long cycle $C_{2\ell}$ — classical supersaturation (Erdős–Simonovits [Er83], used as Lemma 5.5 in [Ja23]) forces $G$ to contain *many* homomorphic (not necessarily injective) copies of a long cycle. Counting homomorphisms is easy; this step is "free." - Step 2 (the hard part, made tractable): build an auxiliary graph on tuples/matchings. Define an auxiliary graph $\mathcal G$ whose vertices are $2k$-matchings (or $r$-subsets, in the blow-up case) of $G$, joined when their union traces out an $8k$-cycle (resp. the right pattern) in $G$. The number of vertices of $\mathcal G$ is governed by $e(G)^{2k}$; the number of *edges* of $\mathcal G$ is governed by the homomorphic-cycle count from Step 1 — and because $G$'s edge count vastly exceeds the Turán number of an even cycle at the $\mathcal G$-level too, $\mathcal G$ itself must contain a long cycle. - Step 3 (the technical crux): most homomorphisms are "conflict-free" almost for free. A long cycle in $\mathcal G$ only gives an actual copy of $H$ in $G$ if its constituent matchings/tuples are pairwise vertex-disjoint (no "coordinate collisions"). The papers' key lemmas (adapted from Jiang–Newman's "small dense subgraphs" cycle-counting toolkit, [16] in both papers) bound the number of "conflicting" homomorphic cycles — those sharing a vertex or edge across supposedly-disjoint copies — and show this count is a *vanishing fraction* of the total homomorphism count established in Step 1. Whatever homomorphic abundance survives after discarding conflicts must therefore contain a genuine, coordinate-disjoint embedding. - Why this generalizes: the recipe turns "does an anomalous $H$ exist with min degree $r$ but small Turán number" into "can I design a *periodic/cyclic gadget* (blow-up of a cycle, or a twisted-ladder cyclic gadget) whose Turán number is controlled by counting homomorphisms of a long cycle in an auxiliary tuple-graph, then killing off degenerate homomorphisms by a counting lemma." This is a purely mechanical last step (Step 3) once the right cyclic gadget (Step 0 — the genuinely creative choice, different in each paper) has been picked. It is exactly the toolkit flagged as still-live in erdos/146.md's Related section (dependent random choice / supersaturation family), and it is the open piece for odd $r\ge5$: Janzer's own Conjecture 6.3 predicts a suitable odd-regular cyclic gadget exists but nobody has yet found — or ruled out — one for $r=5,7,9,\dots$, making this the natural next target for the same machine. - A pointed structural remark for anyone reusing this: the *same* graph $H_{k,\ell}$ that disproves #147 at $r=3$ also, verbatim, disproves the sibling conjecture Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 (the "$\mathrm{ex}(n;G)\ll n^{3/2}\iff G$ is 2-degenerate" biconditional) — one explicit 3-regular counterexample kills two conjectures at once, because $3$-regular $\Rightarrow$ not 2-degenerate $\Rightarrow$ automatically a candidate for both the "min-degree-3" and the "not-2-degenerate" failure modes.

Related

- Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the reverse-direction companion conjecture ($r$-degenerate $\Rightarrow \mathrm{ex}(n;H)=O(n^{2-1/r})$), from the same [ErSi84] paper; still open, and explicitly *not* touched by Janzer's #147 disproof (Janzer's counterexample graphs are high-min-degree, not low-degeneracy, so they say nothing about the #146 direction). - Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 — the $r=2$ biconditional sibling conjecture; disproved by the same $H_{k,\ell}$ graph from [Ja23b] that disproves #147 at $r=3$ — a single construction resolving two problems. - erdos/714 — Zarankiewicz-type conjecture $\mathrm{ex}(n;K_{r,r})\gg n^{2-1/r}$; still open for $r\ge4$ (proved for $r\le3$ by Kővári–Sós–Turán upper bound + Brown/Erdős–Rényi–Sós lower bound). Important contrast: $K_{r,r}$ itself has minimum degree $r$, so it would have been a special case of #147 had #147 been true; #147's disproof shows min-degree alone cannot force the desired lower bound for *general* $H$, but says nothing about the specific graph $K_{r,r}$ — leaving #714 as a genuinely distinct, harder, still-open question that the #147 machinery does not resolve. - 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. - concept/cycle-blow-up — the $F[m]$ blow-up construction (independent sets of size $m$ for vertices, $K_{m,m}$ for edges), the Grzesik–Janzer–Nagy research program (arXiv:1904.07219) it comes from, and its use here to hit every even minimum degree. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — Erdős–Simonovits supersaturation (forcing many homomorphic copies of a structure once the edge count exceeds its Turán number), Step 1 of the shared proof engine above. - concept/homomorphism-counting-embedding — the "count homomorphisms cheaply, then bound conflicting/degenerate ones" technique (adapted from Jiang–Newman's small-dense-subgraphs machinery) that converts homomorphic abundance into an actual embedding; the transferable core of both [Ja23] and [Ja23b]. - concept/probabilistic-deletion-method — the standard random-graph-plus-edge-deletion argument giving the *universal* lower bound $\mathrm{ex}(n;H)=\Omega(n^{2-2/r+\varepsilon})$ for every min-degree-$r$ bipartite $H$; shown by both papers to be essentially tight, which is exactly why it disproves the stronger $2-1/(r-1)$ conjecture. - Random algebraic construction (Bukh; Bukh–Conlon) — random low-degree polynomials over $\\mathbb F_q$ for Turán lower bounds — the broader Bukh–Conlon-style explicit/algebraic lower-bound-construction toolkit in the same research neighborhood (referenced in erdos/146.md); the blow-up and twisted-ladder constructions here are combinatorial rather than algebraic, a useful methodological contrast within the same problem cluster.