Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021

Statement

Let $H$ be a bipartite graph and $\mathrm{ex}(n;H)$ its Turán (extremal) number — the max edges in an $n$-vertex $H$-free graph. Erdős and Simonovits conjectured (1984, [ErSi84], restated in [Er90],[Er91],[Er93]):

$$\mathrm{ex}(n;H) \ll n^{3/2} \iff H \text{ is } 2\text{-degenerate},$$

where $H$ is $2$-degenerate if every subgraph of $H$ has a vertex of degree $\le 2$ (equivalently, $H$ has no induced subgraph of minimum degree $\ge 3$). Erdős offered \$250 for a proof, and — after raising the counterexample bounty from \$100 — \$500 for a disproof (erdosproblems.com/113).

Facts

- Status: DISPROVED ("solved in the negative," \$500 prize paid out in spirit) — erdosproblems.com/113, last edited 19 Oct 2025. - Falsifiable in principle by an explicit finite-graph-family construction; this is exactly how it was settled. - Origin: P. Erdős, "Some recent results on extremal problems in graph theory" (1967) and P. Erdős & M. Simonovits, "Cube-supersaturated graphs and related problems" (1984, [ErSi84]); restated in Erdős's survey papers [Er90],[Er91],[Er93]. - Disproved by Oliver Janzer (ETH Zürich), arXiv:2109.06110 (posted Sept 2021), published as "Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3," *Int. Math. Res. Not. IMRN* (2023), 8478–8494 [Ja23b]. - The known/easy direction is only half-conjectural: the "if" direction ($2$-degenerate $\Rightarrow O(n^{3/2})$) is the $r=2$ case of a *still-open* general statement (Erdős's Conjecture 1.2 in Janzer's paper = **Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$): $H$ $r$-degenerate bipartite $\Rightarrow \mathrm{ex}(n;H)=O(n^{2-1/r})$. Best known general bound: Alon–Krivelevich–Sudakov (2003) proved $O(n^{2-1/(4r)})$ for any $r$-degenerate bipartite $H$; Füredi (1991, independently reproved by ACS) proved the easier one-sided case (all vertices in one part have degree $\le r$) gives the full $O(n^{2-1/r})$ (Theorem 1.1 in Janzer's paper). So even the $r=2$/$3/2$-exponent upper-bound direction of #113 is not fully proved in general — it is known only when the target 2-degeneracy comes from a one-sided-degree-bound witness. - What was actually refuted is the "only if" (necessity) direction: Janzer's Theorem 1.4 constructs, for every $\varepsilon>0$, a 3-regular** bipartite graph $H$ (hence *not* 2-degenerate — a 3-regular graph is its own induced subgraph with min degree 3) such that $\mathrm{ex}(n;H)=O(n^{4/3+\varepsilon})$, which is $o(n^{3/2})$. So $2$-degeneracy is not necessary for the $n^{3/2}$ (indeed even $n^{4/3+\varepsilon}$) bound — the conjecture's iff is false. - The bound is essentially tight for 3-regular graphs: for *any* 3-regular $H$, the standard probabilistic-deletion method gives $\mathrm{ex}(n;H)=\Omega(n^{4/3+\delta})$ for some $\delta>0$ — so $4/3$, not $3/2$, is the correct threshold exponent once you leave 2-degeneracy at the minimal (3-regular) level. - Companion converse conjecture (erdosproblems.com/147: minimum degree $\ge r+1$ $\Rightarrow \exists\varepsilon>0,\ \mathrm{ex}(n;H)=\Omega(n^{2-1/(r-1)+\varepsilon})$) was already disproved by Janzer for all $r\ge 3$ in an earlier paper ("Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles," *Israel J. Math.*, to appear at time of writing — ref [16] in the 2109.06110 paper); #113/Conjecture 1.3 is precisely the boundary $r=2$ case of that same family of statements, and the 2021 paper closes it by reusing and extending that earlier toolkit. - Related problems: Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$.

Solution

The conjecture is FALSE. Erdős's iff fails in the necessity ("only if") direction: there exist bipartite graphs that are emphatically *not* 2-degenerate (3-regular, so minimum degree 3 everywhere) yet still have Turán number strictly below $n^{3/2}$ — in fact as low as $n^{4/3+\varepsilon}$, matching (up to the $\varepsilon$) the probabilistic lower bound that holds for *every* 3-regular graph. So minimum-degree-3 alone does not force $\mathrm{ex}(n;H)\gg n^{3/2}$; degeneracy-3 graphs can be just as sparse-Turán as some 2-degenerate ones.

The counterexample construction (Definition 1.5 in arXiv:2109.06110). For integers $k\ge1,\ \ell\ge2$, build $H_{k,\ell}$ on a $4k\times 2\ell$ grid of vertices $x_{i,j}$ ($1\le i\le 4k$, $1\le j\le 2\ell$, columns indexed cyclically mod $2\ell$): - rung edges in every column: $x_{2i-1,j}x_{2i,j}$ for $1\le i\le 2k$ (a perfect matching down each column); - top/bottom wrap edges linking consecutive columns at the two boundary rows: $x_{1,j}x_{1,j+1}$ and $x_{4k,j}x_{4k,j+1}$; - zigzag diagonal edges linking consecutive columns at interior rows: $x_{2i,j}x_{2i+1,j+1}$ and $x_{2i+1,j}x_{2i,j+1}$ for $1\le i\le 2k-1$.

This graph is 3-regular for every $k,\ell$ (verified in the paper), and Theorem 1.6 shows: for $0<\varepsilon<1/6$, if $k\ge 1/\varepsilon$ and $\ell\ge 16k/\varepsilon$, then $\mathrm{ex}(n;H_{k,\ell})=O(n^{4/3+\varepsilon})$.

The transferable proof technique — nested ("cycle-of-cycles") supersaturation via an auxiliary graph of matchings. This is the reusable idea, summarized from Janzer's own "Overview of the proof" (§1.1): 1. Let $G$ be an $n$-vertex, near-regular graph with $\approx n^{4/3+\varepsilon}$ edges (WLOG almost-regular by standard regularization). Goal: force a copy of $H_{k,\ell}$ inside $G$. 2. First supersaturation pass. Build an auxiliary graph $\mathcal G$ whose *vertices* are ordered $2k$-matchings of $G$ (i.e. $4k$-tuples of distinct vertices $(x_1,\dots,x_{4k})$ with $x_{2i-1}x_{2i}\in E(G)$). Join two matchings $(x_1,\dots,x_{4k})$ and $(y_1,\dots,y_{4k})$ by an edge of $\mathcal G$ exactly when interleaving their coordinates in a prescribed order produces a genuine $8k$-cycle in $G$. Since $G$ has $\approx n^{4/3+\varepsilon}$ edges — far above $\mathrm{ex}(n;C_{8k})$ — classical supersaturation forces $G$ to contain very many $8k$-cycles, which translates into $|E(\mathcal G)| \gtrsim |V(\mathcal G)|^{1+\varepsilon}$. 3. Second supersaturation pass, one level up. $\mathcal G$ itself now has superlinear-over-threshold edge density relative to $\mathrm{ex}(\cdot\,;C_{2\ell})$ once $\ell \gg 1/\varepsilon$, so supersaturation applies *again*, this time inside $\mathcal G$: it must contain a $2\ell$-cycle. If the $4k$-tuples strung along that $2\ell$-cycle in $\mathcal G$ happened to use all-distinct vertices of $G$ (no coordinate reused across "columns"), unpacking them directly reassembles a copy of $H_{k,\ell}$ in $G$. 4. The hard remaining step — killing coordinate collisions. Guaranteeing "no reused vertex" needs controlling how many $8k$-cycles in $G$ share a vertex or edge with each other — done with codegree/"conflict" counting lemmas (bounding, via max-degree and a codegree parameter $s$, how many homomorphic $2k$-cycles reuse a conflicting edge or vertex) imported from Janzer's earlier toolkit built to disprove the $r\ge3$ case of the companion conjecture (Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$, Israel J. Math. paper on rainbow Turán numbers of even cycles / blow-ups of cycles). Rather than using *all* $8k$-cycles to build $\mathcal G$'s edges, the proof restricts to a large sub-collection $\mathcal C$ of $8k$-cycles, engineered so that no vertex of $G$ is overused across $\mathcal C$, and reruns the two-level supersaturation argument on $\mathcal C$ alone. 5. Tightness check. For any 3-regular graph the standard probabilistic-deletion lower bound (start from a random graph and delete an edge from each copy of $H$) gives $\Omega(n^{4/3+\delta})$, so the exponent $4/3$ produced by steps 1–4 is the correct threshold, not an artifact — the construction and the proof meet.

Bottom line for downstream use: "iterated / nested supersaturation via an auxiliary graph of matchings" is the reusable move: (i) supersaturate the host graph for a fixed small cycle to get abundantly many copies of a rigid gadget (here, a $2k$-matching-plus-cycle motif), (ii) treat gadget-copies as vertices of a *new* auxiliary graph and supersaturate *again* to find a long cyclic arrangement of gadgets, (iii) use codegree/conflict lemmas to prune so the final arrangement, unpacked, uses all-distinct host vertices. This let Janzer push a Turán exponent strictly below the naively-conjectured value ($3/2$) down to the probabilistically-tight one ($4/3$), and is the exact toolkit (Israel J. Math., "Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles") that earlier cracked the $r\ge3$ case of the sibling conjecture #147. It is the template for any Erdős-style "bounded-degeneracy $\Rightarrow$ small Turán number" question suspected of not being tight via the naive Füredi / Alon–Krivelevich–Sudakov degree-counting bound (Theorem 1.1) alone — e.g. it directly bears on the still-open general Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ (Conjecture 1.2: $r$-degenerate $\Rightarrow O(n^{2-1/r})$), which is exactly the "if"-direction generalization that #113's disproof shows cannot be pushed further via plain degeneracy witnesses without this kind of nested-cycle argument.

Related

- Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the still-OPEN general "forward"/sufficiency direction (Erdős's Conjecture 1.2: $H$ $r$-degenerate bipartite $\Rightarrow \mathrm{ex}(n;H)=O(n^{2-1/r})$); #113's un-refuted "if" direction is exactly its $r=2$ case, and best known general bound (Alon–Krivelevich–Sudakov, $O(n^{2-1/(4r)})$) is still far from it. - Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ — the general converse conjecture on minimum-degree lower bounds ($\ge r+1$ $\Rightarrow \Omega(n^{2-1/(r-1)+\varepsilon})$), disproved by Janzer for all $r\ge3$ in the earlier companion paper; #113 is precisely the boundary $r=2$ instance of this same family, closed by the present paper's extension of that toolkit. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — the base counting principle (edge count over the Turán threshold forces abundantly many copies of a fixed small subgraph); applied *twice*, at two different "scales" (raw graph, then auxiliary graph of matchings), which is the structural core of the proof. - concept/degenerate-bipartite-turan-bounds — Füredi (1991) / Alon–Krivelevich–Sudakov (2003) degree-counting machinery (Theorem 1.1: one-sided-degree-$\le r$ bipartite $H$ $\Rightarrow O(n^{2-1/r})$); the naive bound that #113's disproof shows is not the whole story once degeneracy witnesses are two-sided. - concept/iterated-supersaturation-auxiliary-matching-graph — the transferable "cycle-of-cycles" technique: build an auxiliary graph whose vertices are matchings/gadget-copies of the host graph, supersaturate at that second level, prune with codegree/conflict lemmas to avoid coordinate collisions.