Turán and Sidorenko bounds for tree-degenerate bipartite graphs (Grzesik–Janzer–Nagy 2019; Jiang–Longbrake 2022)

Statement

The general Erdős–Simonovits conjecture (1967/1984, Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, \$100 prize, status contested since 2026-08-05 — see the dated note in Facts and Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$) asserts: if $H$ is a bipartite $r$-degenerate graph (every induced subgraph of $H$ has a vertex of degree $\le r$), then \[\mathrm{ex}(n;H) = O\!\left(n^{2-1/r}\right).\]

This page is about the solved special case that open problems (including the general conjecture) build on: for a structured sub-family of $r$-degenerate bipartite graphs called tree-degenerate graphs, both

1. the Turán bound $\mathrm{ex}(n;H)=O(n^{2-1/r})$, and 2. the Sidorenko property ($H$ satisfies Sidorenko's conjecture: the homomorphism density of $H$ into any graph $G$ is at least the density predicted by the random graph of the same edge density, $t(H,G)\ge d^{e(H)}$)

are both proved exactly, unifying two previously separate theorems.

Tree-degenerate graphs (Jiang–Longbrake, arXiv:2201.10699): informally, a bipartite graph $H=(A,B)$ that can be built from a rooted tree structure — the vertices of $B$ (or a designated side) admit an ordering/tree-decomposition such that each vertex's "back-neighborhood" is controlled by the tree, generalizing both (a) blow-ups of trees and (b) bipartite graphs with a vertex complete to one side. This class strictly contains both families handled by the two theorems it unifies (below).

Facts

- **The status of the general conjecture (Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$) is contested since 2026-08-05, and $r=2$ is exactly where. Two facts, each with its identifier and date, neither of which alone settles the question: (i) a machine-checked counterexample exists — theorem `not_erdos_146` (line 18543 of `CompactnessAndDegeneracy.lean`, 18,588 lines, 0 occurrences of sorry**) in github.com/openai/ten-proofs (Apache-2.0, created and pushed 2026-08-05, repo metadata read via api.github.com on 2026-08-26) instantiates that file's DegeneracyConjectureStatement at $r=2$ via twoDegenerateExtremalCounterexample and contradicts the $n^{3/2}$ bound (its IsDegenerate coincides with "every induced subgraph has minimum degree $\le r$"); (ii) the canonical register has not recorded it — www.erdosproblems.com/146 (fetched with a browser User-Agent on 2026-08-26, HTTP 200) still shows the badge "OPEN (LEAN)", the \$500 prize, "This page was last edited 18 January 2026", "0 claimed proofs for this problem", and states that its open status "reflects the current belief of the owner of this website". No prize has been claimed or awarded, and the verified theorem instantiates $r=2$ only. The best known *general* bound, for every $r$-degenerate bipartite $H$ with no further structure, is Alon–Krivelevich–Sudakov's 2003 $\mathrm{ex}(n;H)=O(n^{2-c/r})$ for a universal constant $c<1$ — a weaker exponent than the conjectured $2-1/r$ (Alon, Krivelevich, Sudakov, "Turán numbers of bipartite graphs and related Ramsey-type questions," *Combin. Probab. Comput.* 12 (2003), 477–494; confirmed on the UCSD Erdős-problems page and on this wiki's Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$). - AKS03 also proved the sharp exponent in one special case: if $H$ is bipartite with maximum degree $r$ on one side of the bipartition, then $\mathrm{ex}(n;H)=O(n^{2-1/r})$ exactly — this reduces to a Kővári–Sós–Turán-style argument and is the base case the later results generalize. - Progress ladder that this page's result caps (three strictly-generalizing papers, 2003 → 2019 → 2022): 1. Füredi, and independently Alon–Krivelevich–Sudakov (2003) — dependent random choice proof of the sharp bound for the one-sided-bounded-degree case. 2. Grzesik, Janzer, Nagy, "The Turán number of blow-ups of trees" (arXiv:1904.07219, 2019, published *J. Combin. Theory Ser. B*) — proved $\mathrm{ex}(n;H)=O(n^{2-1/r})$ for all $r$-degenerate blow-ups of trees, a strictly larger family than AKS03's case. Technique: supersaturation combined with a random walk on an auxiliary graph (not dependent random choice). 3. Jiang, Longbrake, "Tree-degenerate graphs and nested dependent random choice" (arXiv:2201.10699, 2022) — introduced a nested variant of the dependent random choice lemma and used it to prove *both* the Turán bound and the Sidorenko property for the still-larger class of tree-degenerate graphs, giving "a common extension of the theorem of Conlon, Fox, and Sudakov [on Sidorenko's conjecture] and the theorem of Grzesik, Janzer, and Nagy [on tree blow-ups]." - Sidorenko side: Conlon–Fox–Sudakov had earlier used ordinary (single-layer) dependent random choice to prove Sidorenko's conjecture for any bipartite $H$ with a vertex complete to the other side. Sidorenko's conjecture itself is proved for trees by an elementary tensor-power argument (Alon–Ruzsa / Sidorenko), and remains open in general. Jiang–Longbrake's nested method reproves and extends the Conlon–Fox–Sudakov case within the unified tree-degenerate framework. - Why "tree-degenerate" is the right generalization: both source theorems (one-sided bounded degree; blow-ups of trees) are, at heart, saying that if $H$'s "hard side" has a tree-like recursive branching structure with bounded fan-out $r$ at each step, both the extremal (Turán) and quasirandom-homomorphism (Sidorenko) counting arguments go through. Tree-degeneracy is the abstraction that isolates exactly this recursive branching property and lets one theorem/proof handle both consequences at once.

Solution

Answer: for the class of tree-degenerate bipartite graphs $H$ with degeneracy parameter $r$: $\mathrm{ex}(n;H)=O(n^{2-1/r})$ (sharp exponent, matching the general Erdős–Simonovits conjecture), and $H$ satisfies Sidorenko's conjecture.

The transferable idea — nested dependent random choice. Ordinary dependent random choice (Fox–Sudakov survey, arXiv:0909.3271) picks a *single* random subset $S$ of vertices (or a random vertex weighted by degree) in a dense/quasirandom host graph $G$, and shows that with positive probability, almost every small subset of $S$'s common neighborhood is itself large — enough "common neighborhood" structure to greedily embed a bounded-degree bipartite graph $H$ one side at a time. This single-layer version is exactly what powers the Füredi/Alon–Krivelevich–Sudakov one-sided-bounded-degree case and the Conlon–Fox–Sudakov "vertex complete to one side" Sidorenko case — but it only controls *one* level of branching, so it cannot see the deeper recursive tree structure that blow-ups of trees or general tree-degenerate graphs need.

The key move: apply dependent random choice recursively, layer by layer, following the tree/recursive structure of $H$ itself, rather than once at the top level. At each level of the embedding (corresponding to a level of $H$'s tree decomposition), the previously-selected "common neighborhood" set from the outer application is itself refined by an *inner* dependent-random-choice step, so that the concentration/largeness guarantee is inherited and compounded down the recursion instead of degrading. This lets the same embedding machinery: - greedily embed $H$ vertex-by-vertex along its tree order while keeping every partial common-neighborhood set large enough (Turán side — feeds an extremal counting argument), and - simultaneously control homomorphism counts at every level, which is exactly the extra bookkeeping Sidorenko's conjecture needs (Sidorenko side — feeds a counting/probabilistic argument), using the *same* nested random-choice sets for both.

Because both consequences (Turán bound and Sidorenko property) come out of the *same* nested embedding/counting object, one proof does double duty — this is the "common extension" claim: Conlon–Fox–Sudakov (Sidorenko, single-layer) and Grzesik–Janzer–Nagy (Turán, blow-ups of trees, different technique — random walk + supersaturation) are each recovered as the single-layer / specific-tree-shape special cases of the general nested-DRC argument.

Why this is the piece open problems depend on: the fully general Erdős–Simonovits conjecture (Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, status contested since 2026-08-05 at exactly $r=2$ — see Facts) is precisely the claim that *every* $r$-degenerate bipartite graph — not just tree-degenerate ones — obeys the sharp exponent. The tree-degenerate result is the largest currently-known "solved territory" inside that conjecture, and nested dependent random choice is the concrete technique that pushed the boundary of solved territory outward twice (Conlon–Fox–Sudakov's single-layer case, then Grzesik–Janzer–Nagy's tree-blow-up case, now unified and extended). Any future attack on the general conjecture (or on the $r=2$ case, whose status is contested since 2026-08-05 — see Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$) is a natural candidate to try pushing the nesting further — e.g. asking what recursive/branching structure beyond "tree-degenerate" the method can still track before the concentration bounds degrade.

Related

- Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the general Erdős–Simonovits conjecture (\$100; status contested since 2026-08-05: machine-checked counterexample at $r=2$ in github.com/openai/ten-proofs vs. erdosproblems.com/146 still badged "OPEN (LEAN)" when fetched 2026-08-26) that tree-degenerate graphs are a proved special case of; this page's result is explicitly cited there as part of the "known results" progress ladder. - Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 and Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ — companion conjectures in the same bipartite-degeneracy-Turán family, both disproved by Janzer (a cautionary note: this is the same problem *neighborhood*, but a different implication direction than the one this page's technique advances). - 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 base technique (Fox–Sudakov survey, arXiv:0909.3271); this page's "nested" variant is a direct generalization. - r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal) — $r$-degeneracy, the structural hypothesis; tree-degeneracy is a strictly more structured sub-property. - concept/sidorenko-conjecture — the homomorphism-density conjecture; proved here for the tree-degenerate class, still open in general. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — the alternate technique (combined with a random-walk argument) that Grzesik–Janzer–Nagy used for the tree-blow-up case before Jiang–Longbrake's nested-DRC unification. - 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, the base case that Alon–Krivelevich–Sudakov's one-sided-bounded-degree result (itself subsumed by tree-degeneracy) generalizes.