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, still OPEN) 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 general conjecture (Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$) remains open even for $r=2$.** 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}$, still open even at $r=2$) 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 still-open $r=2$ case) 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, OPEN even for $r=2$) 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.