Grzesik–Janzer–Nagy (2019/2022) — the Turán number of blow-ups of trees: $\\mathrm{ex}(n,T[r])=O(n^{2-1/r})$, the $r$-degenerate blow-up-of-a-tree case of Erdős's 1967 degenerate-Turán conjecture

Statement

**Erdős's 1967 conjecture (Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, still open in full generality). Let $F$ be a bipartite graph that is $r$-degenerate** (every subgraph of $F$ has a vertex of degree $\le r$). Then $$\mathrm{ex}(n,F) = O_F(n^{2-1/r}),$$ i.e. any $n$-vertex $F$-free graph has at most $Cn^{2-1/r}$ edges for a constant $C=C(F)$.

The solved special case this page documents. For a tree $T$, define its ($r$-fold) blow-up $T[r]$: replace every vertex of $T$ by an independent set of $r$ vertices, and join two blown-up vertices by a complete bipartite graph exactly when the corresponding original vertices of $T$ are adjacent (more generally, parts can have unequal sizes, as long as the result stays $r$-degenerate). Grzesik, Janzer, and Nagy proved: $$\mathrm{ex}(n,T[r]) = O(n^{2-1/r})$$ for every tree $T$ and every $r$-degenerate blow-up of $T$ — settling Erdős's 1967 conjecture for this entire infinite family of graphs, in fact for the strictly larger family of $(r,t)$-blownup trees (Definition 1.8 below).

Facts

- Authors / source: Andrzej Grzesik, Oliver Janzer, Zoltán Lóránt Nagy, "The Turán number of blow-ups of trees," arXiv:1904.07219 (submitted April 2019); published *Journal of Combinatorial Theory, Series B* 156 (2022), 299–309. - The Kővári–Sós–Turán theorem ($F=K_{r,t}$, $r\le t$: $\mathrm{ex}(n,F)=O(n^{2-1/r})$) is the $r=1$-degenerate-witness prototype Erdős's conjecture generalizes. - Prior partial results, all reproved/generalized by this paper: - Füredi (1991, implicit) / reproved by Alon–Krivelevich–Sudakov (2003) via dependent random choice: if $F$ is bipartite with max degree $\le r$ on one side, then $\mathrm{ex}(n,F)=O(n^{2-1/r})$ — the full sharp exponent, but only for this restrictive sub-case of $r$-degeneracy. - Alon–Krivelevich–Sudakov (2003): for any $r$-degenerate bipartite $F$, the weaker bound $\mathrm{ex}(n,F)=O(n^{2-1/(4r)})$ — general but with a lossy exponent. - Füredi–West (2001): $\mathrm{ex}(n,K_{s,s}\setminus K_{s-r,s-r})=O(n^{2-1/r})$ — this is exactly the blow-up-of-the-path-$P_4$ case, later subsumed as a corollary of Theorem 1.7 below. - Key structural notion: "complexity" of an $r$-degenerate bipartite graph. Every $r$-degenerate bipartite graph embeds into a "complete $r$-degenerate bipartite graph of complexity $s$," built inductively: complexity 0 is $K_{r,r}$ (any multiplicity); complexity $s$ is obtained from a complexity-$(s-1)$ graph by attaching new vertices, each joined completely to some $r$-subset of an existing part. The complexity of $F$ is the smallest $s$ such that $F$ embeds in some complexity-$s$ complete graph. Füredi–West is exactly the complexity-1 case; Füredi/AKS03's one-sided theorem covers only some complexity-$\le2$ graphs. - Theorem 1.5 (this paper): Erdős's conjecture holds for all $r$-degenerate bipartite graphs of complexity $\le 2$ — already strictly more than was known. - Theorem 1.6 / 1.7 (the named result): for a tree $T$, $\mathrm{ex}(n,T[r])=O(n^{2-1/r})$, and more generally for any graph $F$ that is $r$-degenerate and is a blow-up of a tree (independent-set vertex blow-up + complete-bipartite edge blow-up, arbitrary part sizes). - Theorem 1.9 (most general form proved): defines an $(r,t)$-blownup tree of size $k$ — start with disjoint sets $X_1=Y_0$ ($|X_1|=r$) and $Y_1,\dots,Y_k$ ($|Y_i|=t$); for each $i\ge2$ pick $X_i\subseteq Y_j$ for some earlier $j<i$ with $|X_i|=r$; join every $X_i$ completely to $Y_i$. Any such graph is automatically $r$-degenerate, and $\mathrm{ex}(n,L)=O(n^{2-1/r})$ for every $(r,t)$-blownup tree $L$ of arbitrary size. This single theorem contains Theorem 1.2/Füredi's one-sided-degree case as a special instance (any bipartite $F$ with max degree $\le r$ on one side embeds in a suitable $(r,t)$-blownup tree). - Follow-up generalization: Jiang–Longbrake, "Tree-degenerate graphs and nested dependent random choice," arXiv:2201.10699 (2022), introduce a *nested* dependent-random-choice lemma giving a common extension of Füredi/AKS03's one-sided-degree theorem and this paper's tree-blow-up theorem for a class they call "tree-degenerate" graphs, and connect the same machinery to a Sidorenko-type theorem of Conlon–Fox–Sudakov. - Related follow-up strand (edge blow-ups): a separate line of work ("The Turán number for the edge blow-up of trees," arXiv:2008.09998, and "the missing case," arXiv:2206.05162) treats the *edge*-blow-up (replacing each edge, not vertex, by a clique/complete bipartite gadget) — a related but distinct construction from the vertex-blow-up $T[r]$ studied here; not independently verified in this session beyond the search snippet. - The general conjecture is still open, and the graphs of high complexity that are *not* blow-ups of trees (and not one-sided-bounded-degree) remain the frontier; see Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ for the full open-problem tracking page and its "adjacent conjectures disproved" caveats (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}$ — different, reverse-direction statements in the same Erdős–Simonovits research program, both *disproved* by Janzer, and *not* counterexamples to this conjecture).

Solution

Answer: YES for all (r-degenerate) blow-ups of trees — $\mathrm{ex}(n,T[r])=O(n^{2-1/r})$, matching Erdős's conjectured exponent exactly (tight, by the Alon–Rónyai–Szabó / Kollár–Rónyai–Szabó norm-graph constructions for $K_{r,s}$ with $s>(r-1)!$).

The transferable technique — turn "embed a bounded-degeneracy graph" into "run a random walk on an auxiliary graph of $r$-sets, built dense by supersaturation."

1. Reduce edge-counting to embedding. As always in Turán theory, it suffices to show: any graph $G$ on $n$ vertices with $\gg n^{2-1/r}$ edges contains a copy of the target $(r,t)$-blownup tree $L$. Ordinary supersaturation (Erdős–Simonovits) already gives that $G$, having edge density above the $K_{r,t}$-threshold, contains many copies of $K_{r,t}$ — but naively stitching these copies together into a tree-shaped structure risks reusing vertices and getting stuck. 2. Build a dense auxiliary graph whose vertices are $r$-sets of $G$. Define an auxiliary graph $\mathcal A$ on the $r$-element subsets of $V(G)$, joining an $r$-set $X$ to a $t$-set-completing structure when $X$ together with a suitable $Y\supseteq$ neighbourhood witnesses a copy of $K_{r,t}$ in $G$ rooted at $X$. Because $G$ has superthreshold edge density, supersaturation forces $\mathcal A$ itself to be dense — this is the step that converts a raw edge-count hypothesis into a workable combinatorial density on the *auxiliary* object. 3. Do NOT embed greedily/deterministically — use the stationary distribution of a random walk on $\mathcal A$. The naive greedy embedding of a tree's vertices one at a time can get stuck (later vertices may have no valid image once earlier images are fixed, because degeneracy alone doesn't guarantee enough "room" is left). Instead, the images of the first few vertices of $L$ are chosen according to the stationary distribution of a random walk on $\mathcal A$, not chosen greedily or uniformly — this biases the embedding toward $r$-sets with large residual neighbourhoods. 4. Propagate the embedding along the walk. The images of the remaining vertices of $L$ are chosen by continuing the same random walk on $\mathcal A$: because $L$ is a blow-up of a *tree* (hence has a natural "parent" structure — each new $X_i$ sits inside an earlier $Y_j$), each new vertex's image only needs to extend a walk step from an already-placed $r$-set, so the process never needs to look far ahead. 5. Union bound / concentration closes the argument. Standard random-walk mixing/concentration shows that, with positive probability, *every* $r$-set visited along the whole walk retains a large enough neighbourhood in $G$ to continue the embedding — i.e. with positive probability the random process never gets stuck, so a valid embedding of $L$ exists. Positive probability of success is enough to conclude existence.

Why this beats plain dependent random choice. The one-sided-bounded-degree case (Füredi / AKS03) is solvable by dependent random choice alone because a *single* dense "reservoir" of common neighbours suffices — every degree-$\le r$ vertex on the small side only ever needs one shared neighbourhood. A general $r$-degenerate blow-up of a tree instead has a branching, multi-level dependency structure (each new part's attachment set can sit inside *any* earlier part, not just the root), so a single dependent-random-choice reservoir is not enough; the fix is to replace "one dense reservoir" with "a whole auxiliary graph of reservoirs, navigated by a random walk whose stationary distribution is biased toward good starting points." This same architecture — supersaturate to get a dense auxiliary structure, then run a random walk (rather than a greedy or single dependent-random-choice step) to perform the actual embedding — is exactly the generalization Jiang–Longbrake's "nested dependent random choice" (arXiv:2201.10699) later reformulates and extends to the broader "tree-degenerate" graph class.

Portable lesson for downstream (open) degeneracy-Turán problems. Whenever an $r$-degenerate bipartite target graph $F$ has a tree-like (acyclic) dependency structure among its high-degree witnesses — i.e. its complexity-defining sequence of $r$-set attachments forms a tree/forest rather than something with cross-dependencies — the embedding can be found by (i) supersaturating the host graph to make an auxiliary "$r$-set graph" dense, then (ii) embedding via a random walk on that auxiliary graph rather than a single dependent-random-choice step or greedy search. The obstruction to extending this to all $r$-degenerate bipartite graphs (the fully general Erdős conjecture, Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, still open) is precisely graphs whose complexity structure is *not* tree-shaped — where the auxiliary-graph/random-walk machinery does not obviously apply, and where the authors themselves (§3) only dare conjecture, not prove, the natural generalization (Conjecture 3.1: $\mathrm{ex}(n,F)=O(n^{2-\alpha})\Rightarrow\mathrm{ex}(n,F[r])=O(n^{2-\alpha/r})$ for arbitrary $F$, verified here only for $F$ a tree or $F=K_{s,t}$, explicitly flagged as open even for $F=$ even cycle).

Related

- Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the fully general, still-open Erdős 1967 conjecture ($r$-degenerate bipartite $F\Rightarrow\mathrm{ex}(n,F)=O(n^{2-1/r})$) that this page proves a large special case of; best fully-general bound remains Alon–Krivelevich–Sudakov's weaker $O(n^{2-1/4r})$ (2003), unimproved in general since. - Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 — a *different*, reverse-direction biconditional conjecture from the same Erdős–Simonovits research program (2-degenerate $\iff\mathrm{ex}(n,G)\ll n^{3/2}$); disproved by Janzer (arXiv:2109.06110) — not a counterexample to this page's result or to 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}$ — the companion min-degree lower-bound conjecture in the same program; disproved by Janzer for $r\ge3$. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) *(forward link — not yet written)* — the Erdős–Simonovits principle (superthreshold edge density forces abundantly many copies of a fixed subgraph) used here to densify the auxiliary $r$-set graph before the random walk runs; the same principle underlies the "nested/nested-cycle" iterated-supersaturation technique used one level up in Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021's disproof. - 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 *(forward link — not yet written)* — the classical Füredi/Alon–Krivelevich–Sudakov single-reservoir technique this paper's random-walk-on-an-auxiliary-graph generalizes to handle tree-shaped (multi-level) dependency structures; formalized as "nested dependent random choice" by Jiang–Longbrake, arXiv:2201.10699. - r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal) *(forward link — not yet written)* — $r$-degeneracy, the structural hypothesis common to this whole problem family. - concept/random-walk-embedding *(forward link — not yet written)* — the specific transferable idea of this page: embed a target graph into a dense host by running a random walk (using the walk's stationary distribution to choose early vertex images) on an auxiliary graph of $r$-sets/reservoirs built dense via supersaturation, rather than embedding greedily or via a single dependent-random-choice step. - Jiang, Z., Longbrake, L., "Tree-degenerate graphs and nested dependent random choice," arXiv:2201.10699 (2022) — direct follow-up generalizing this paper's technique and result to a broader "tree-degenerate" graph class, and connecting it to Sidorenko-type results of Conlon–Fox–Sudakov. - Füredi, Z., West, D. B., "Ramsey theory and bandwidth of graphs," *Graphs and Combinatorics* 17 (2001), 463–471 — proves the $\mathrm{ex}(n,K_{s,s}\setminus K_{s-r,s-r})=O(n^{2-1/r})$ special case (the blow-up of $P_4$), subsumed as a corollary of Theorem 1.7 here.