Alon–Krivelevich–Sudakov (2003) — Turán number of bipartite $H$ with bounded degree on one side, $\\mathrm{ex}(n,H) = O(n^{2-1/r})$

Statement

Question. For a bipartite graph $H=(A\cup B, F)$ with color classes $A,B$, and an integer $n$, the Turán number $\mathrm{ex}(n,H)$ is the maximum number of edges a simple $n$-vertex graph can have while containing no copy of $H$. For general bipartite $H$ the order of magnitude of $\mathrm{ex}(n,H)$ is unknown (this is the notoriously hard case of the Erdős–Turán/Zarankiewicz-type program — see Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ for the still-open $r$-degenerate generalization). **What is $\mathrm{ex}(n,H)$ when $H$ is bipartite and every vertex on *one* of its two sides has degree at most a fixed constant $r$** (no constraint on the degrees on the other side, which can be arbitrarily large, e.g. $K_{r,s}$ for huge $s$)?

Facts

- Source: N. Alon, M. Krivelevich, B. Sudakov, "Turán numbers of bipartite graphs and related Ramsey-type questions," *Combinatorics, Probability and Computing* 12 (2003), 477–494. PDF: web.math.princeton.edu/~nalon/PDFS/akstr6.pdf. - Answer: yes, $\mathrm{ex}(n,H) = O_H(n^{2-1/r})$ — and this is tight for every fixed $r\ge2$. - Theorem 2.2 / Corollary 2.3 (AKS03). Let $H=(A\cup B,F)$ with $|A|=a$, and suppose every vertex of $B$ has degree $\le r$ in $H$. Then there is $c=c(H)>0$ with $\mathrm{ex}(n,H)\le c\,n^{2-1/r}$. - Tightness. For every fixed $r\ge2$ and every $s\ge (r-1)!+1$, $\mathrm{ex}(n,K_{r,s})=\Theta(n^{2-1/r})$: the lower bound is the classical Kővári–Sós–Turán (1954) construction combined with the algebraic norm-graph constructions of Kollár–Rónyai–Szabó (*Combinatorica* 16 (1996), 399–406) and Alon–Rónyai–Szabó (*J. Combin. Theory Ser. B* 76 (1999), 280–290), which the AKS03 paper cites directly for the matching lower bound. So the exponent $2-1/r$ cannot be improved for this class of $H$. - This result was already derivable from an earlier theorem of Füredi (*Combinatorica* 11 (1991), 75–79); AKS03's contribution is a different, self-contained proof via a new probabilistic lemma that also yields several unrelated Ramsey-type corollaries in the same paper (a bipartite case of an Erdős conjecture $r(G)\le 2^{c\sqrt m}$ for graphs with $m$ edges, §5), and in §6 improves Füredi's quantitative bound for the related graph family $\mathbf L_t^{k,s}$ (a generalized theta/norm-graph-adjacent gadget), showing $\mathrm{ex}(2n,\mathbf L_t^{k,s}) \le 2^{1+1/t}(s+1)^{1/t}kn^{2-1/t}$. - **Scope note (what AKS03 does *not* solve). The paper is also motivated by, but does not resolve, a strictly harder conjecture of Erdős: that $\mathrm{ex}(n,H)=O(n^{2-1/r})$ for every** $r$-*degenerate* bipartite $H$ (a much larger class than "bounded degree on one side" — degeneracy only bounds degrees in every subgraph, not the degrees of a whole side). For that harder class AKS03 only proves the weaker $\mathrm{ex}(n,H)\le n^{2-c/r}$ (Theorem 3.6, with a universal constant $c$, sharpened in the paper from an initial exponent-loss of $10r$ down to $4r$ in the denominator). That general conjecture remains open — see Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, which cites this exact one-sided-degree theorem as its solved base case.

Solution

**The transferable technique: a "dependent random choice" lemma — pick a random *small* tuple, take its common neighborhood, and prune away the (provably rare) bad tuples by a first-moment argument — followed by a purely greedy embedding.**

The whole proof is two short, modular pieces.

1. The core probabilistic lemma (Lemma 2.1 in the paper)

*Claim.* Let $G=(V,E)$, $|V|=n$, average degree $d=2|E(G)|/n$. If positive integers $a,b,r$ satisfy $$\frac{d^r}{n^{r-1}} - \binom{n}{r}\Big(\frac{b-1}{n}\Big)^r \;>\; a-1,$$ then $G$ contains a set $A_0$ of at least $a$ vertices such that every $r$-tuple of vertices in $A_0$ has at least $b$ common neighbors in $G$.

*Proof idea (fully worked, this is the reusable engine).* - Pick a uniformly random $r$-tuple $T$ of vertices of $V$ with repetition, and let $A = N^*_G(T)$ be the common neighborhood of $T$, $X=|A|$. - By linearity of expectation and convexity of $x\mapsto x^r$: $\;\mathbb E[X] = \frac1{n^r}\sum_v |N(v)|^r \ge \frac{d^r}{n^{r-1}}$ — a random common neighborhood is, in expectation, at least as large as if every vertex had exactly the average degree. - Let $Y$ count the $r$-tuples $R\subseteq A$ that are "bad": their common neighborhood in the *whole graph* has size $<b$. For a fixed $r$-tuple $R$, $\Pr[R\subseteq A] = (|N^*_G(R)|/n)^r$, so $\mathbb E[Y]\le \binom nr\big(\frac{b-1}n\big)^r$ (union bound over the $\le\binom nr$ bad $r$-subsets). - Combine: $\mathbb E[X-Y] > a-1$, so some specific choice of $T$ achieves $X-Y\ge a$. Delete one vertex from $A$ for each bad $r$-tuple still inside it (killing all of $Y$ at the cost of at most $Y$ vertices); what remains, $A_0$, has $\ge a$ vertices and — crucially — *every* $r$-tuple of $A_0$ now has $\ge b$ common neighbors in $G$, by construction.

This is a first-moment / alteration argument: expectation gives a large candidate set, a union bound over a *polynomial* (in $n$) number of "bad events" (here: $r$-tuples with too few common neighbors) shows the expected damage is small, and a single deterministic deletion pass repairs every violation without shrinking the set below the target size. This exact recipe — random small "test" tuple → common neighborhood is large on average → few tuples inside it are bad → delete-to-fix — is what the literature now generally calls dependent random choice (see 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); AKS03 note this specific formulation refines earlier variants due to Rödl, Gowers, Kostochka–Sudakov, and Sudakov, and it has since become one of the standard tools of extremal/Ramsey graph theory (surveyed by Fox–Sudakov, 2011).

2. Greedy embedding (Theorem 2.2)

Given $H=A\cup B$ with $|A|=a$, $|B|=b$, and every $v\in B$ having degree $\le r$: apply Lemma 2.1 to $G$ with the roles $(a,b)\to(a,\,a+b)$, obtaining $A_0\subseteq V(G)$, $|A_0|=a$, in which every $r$-subset has $\ge a+b$ common neighbors. Map $A\to A_0$ by an arbitrary bijection. Then embed the vertices of $B$ one at a time: each $v_i\in B$ has $\le r$ neighbors in $A$, whose images form an $r$-subset of $A_0$ with $\ge a+b$ common neighbors in $G$ — since fewer than $a+b$ vertices of $G$ have been used so far, an unused common neighbor always exists, and is assigned as the image of $v_i$. This produces a full copy of $H$. Because $a+b$ (i.e., $|H|$) is a constant independent of $n$, choosing $d\sim n^{1-1/r}$ (so $\mathrm{ex}(n,H)\sim cn^{2-1/r}$ edges) is exactly the threshold at which Lemma 2.1's hypothesis is satisfiable — giving the matching upper bound $\mathrm{ex}(n,H)=O(n^{2-1/r})$.

Why this generalizes the classical Kővári–Sós–Turán theorem for $K_{r,t}$ (a special case: $A$ is the size-$r$ side). KST is the $H=K_{r,t}$ instance of exactly this pattern: "a graph with $\gg n^{2-1/r}$ edges must contain $r$-degenerate-on-one-side structure with abundant common neighborhoods." AKS03's contribution is realizing that the *same* dependent-random-choice engine, decoupled from the complete-bipartite special case, works for any bipartite $H$ with bounded degree on one side, and pruning "bad" tuples by a first-moment argument (rather than KST's direct double-counting) is what makes the generalization go through cleanly. This decoupling — engine (Lemma 2.1) separate from application (greedy embedding, Theorem 2.2) — is exactly the reusable shape: the same Lemma 2.1 is reused later in the same paper for the Ramsey-number results (§4–5) with no changes, just different parameter choices.

Where the technique runs out of steam (open frontier). For the strictly harder class of $r$-*degenerate* bipartite $H$ (bounded degree only in every subgraph, not on a whole side — e.g. no bound on how large $|B|$'s degrees can get, so long as deleting high-degree vertices repeatedly reveals a low-degree one), the same style of argument (Lemma 3.2 / Theorem 3.5 in the paper) only delivers $n^{2-c/r}$ for some absolute constant $c$ — not the conjectured $n^{2-1/r}$. AKS03 explicitly flag closing this gap as requiring "some additional ideas." That fully general conjecture is Erdős's, and remains open — see Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, whose own Facts document this exact AKS03 theorem as the solved one-sided-degree special case and track the subsequent 2019–2022 partial progress (Grzesik–Janzer–Nagy on tree blow-ups; Jiang–Longbrake's "nested dependent random choice," a direct technical descendant of the very lemma above).

Related

- Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the still-open general conjecture (Erdős, 1967) that $\mathrm{ex}(n,H)=O(n^{2-1/r})$ for *every* $r$-degenerate bipartite $H$; this page's theorem is the solved special case ("bounded degree on one side" $\subsetneq$ "$r$-degenerate") that the open problem's own Facts cite as its base case and technical starting point. - 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 general name for the Lemma 2.1 engine documented in full above; also the workhorse behind Füredi's earlier (1991) proof of this same bound, and behind Jiang–Longbrake's 2022 "nested" extension used on the still-open Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$. - Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s}) *(forward link — not yet written)* — the classical Kővári–Sós–Turán (1954) bound $\mathrm{ex}(n,K_{r,t})=O(n^{2-1/r})$, the $H=K_{r,t}$ special case this theorem generalizes, and whose matching lower-bound constructions (norm-graphs) also supply this theorem's tightness. - Erdős #760 — large χ(G) forces a subgraph of large cochromatic number ζ(H) ≫ χ(G)/log χ(G) — a different Alon–Krivelevich–Sudakov collaboration (1997, cochromatic number of dense graphs) also solved via a short two-stage probabilistic argument; same three authors, same "short probabilistic lemma → clean corollary" methodology, unrelated problem. - Füredi, Z., "On a Turán type problem of Erdős," *Combinatorica* 11 (1991), 75–79 — the earlier, independent proof of the same $O(n^{2-1/r})$ bound (via a different method), which AKS03's Theorem 2.2 reproves and whose bound is improved in AKS03 §6 for the related graph family $\mathbf L_t^{k,s}$. - Kollár, J.; Rónyai, L.; Szabó, T., "Norm-graphs and bipartite Turán numbers," *Combinatorica* 16 (1996), 399–406, and Alon, N.; Rónyai, L.; Szabó, T., "Norm-graphs: variations and applications," *J. Combin. Theory Ser. B* 76 (1999), 280–290 — the algebraic lower-bound constructions establishing tightness of the $n^{2-1/r}$ exponent for $K_{r,s}$, $s\ge(r-1)!+1$, cited directly in AKS03's tightness remark. - Jiang, T.; Longbrake, S., "Tree-degenerate graphs and nested dependent random choice," arXiv:2201.10699 (2022) — a direct technical descendant that nests the Lemma 2.1-style engine to extend both this theorem and the Grzesik–Janzer–Nagy tree-blow-up result, working toward (but not resolving) the general Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ conjecture.