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

Statement

Basic Lemma (Fox–Sudakov, arXiv:0909.3271, Lemma 2.1; earlier versions due to Rödl, Gowers, Kostochka, Sudakov — see Kostochka–Rödl 2001, Sudakov 2003, Gowers 2001). Let $a,d,m,n,r$ be positive integers. Let $G=(V,E)$ be a graph with $|V|=n$ vertices and average degree $d = 2|E(G)|/n$. If there is a positive integer $t$ such that $$\frac{d^t}{n^{t-1}} - \binom nr\Big(\frac mn\Big)^t \ \ge\ a,$$ then $G$ contains a subset $U$ of at least $a$ vertices such that every $r$-element subset of $U$ has at least $m$ common neighbors.

Proof (transcribed in full). Pick a list $T$ of $t$ vertices of $V$ uniformly at random *with repetition*. Set $A=N(T)$ (the common neighborhood of $T$), $X=|A|$. By linearity of expectation and convexity of $f(z)=z^t$, $$\mathbb E[X]=\sum_{v\in V}\Big(\frac{|N(v)|}{n}\Big)^t = n^{-t}\sum_{v\in V}|N(v)|^t \ \ge\ n^{1-t}\Big(\frac{\sum_v |N(v)|}{n}\Big)^t = \frac{d^t}{n^{t-1}}.$$ Call an $r$-subset $S$ bad if $|N(S)|<m$. The probability $S\subset A$ is $(|N(S)|/n)^t$, so for bad $S$ this is $<(m/n)^t$; since there are at most $\binom nr$ subsets $S$ of size $r$, letting $Y$ count bad $r$-subsets contained in $A$, $$\mathbb E[Y] < \binom nr\Big(\frac mn\Big)^t.$$ By linearity, $\mathbb E[X-Y]\ge d^t/n^{t-1} - \binom nr(m/n)^t \ge a$, so some draw of $T$ achieves $X-Y\ge a$. Delete one vertex from each bad $r$-subset of $A$; the remaining set $U$ has $|U|\ge X-Y\ge a$ vertices and, by construction, every $r$-subset of $U$ has $\ge m$ common neighbors. $\blacksquare$

The companion embedding lemma (Lemma 3.2 in the survey). If $H=(A\cup B,F)$ is bipartite with $|A|=a$, $|B|=b$, and every vertex of $B$ has degree $\le r$ in $H$, and $G$ has a vertex subset $U$ with $|U|=a$ such that every $r$-subset of $U$ has $\ge a+b$ common neighbors, then $H\subseteq G$. Proof idea: embed $A\to U$ arbitrarily, then embed $B$'s vertices one at a time; each $v\in B$ has $\le r$ neighbors already placed in $U$, so by hypothesis there are $\ge a+b$ candidate images, of which fewer than $a+b$ are already used — greedily place $v$ in an unused one.

Composing these two lemmas is the entire mechanism: Lemma 2.1 manufactures the "rich" set $U$; Lemma 3.2 (or a variant) greedily embeds the target graph $H$ into $U$'s common neighborhoods one vertex at a time. Essentially every application in the survey is an instance of choosing $(a,d,m,n,r,t)$ so that Lemma 2.1's inequality holds and then invoking an embedding lemma of this shape.

Key variants proved in the same survey (needed for different regimes)

- Almost-all-pairs variant (Lemma 5.1), for bipartite $G$ with parts $A,B$, $e(G)=c|A||B|$: for any $0<\epsilon<1$ there is $U\subset A$, $|U|\ge c|A|/2$, such that at most an $\epsilon$-fraction of ordered pairs in $U$ are "bad" (fewer than $\epsilon c^2|B|/2$ common neighbors). Proved by picking a single random $v\in B$ and setting $U=N(v)$, using Cauchy–Schwarz on $\mathbb E[X^2]$ rather than the multi-vertex $T$ of Lemma 2.1. This is needed because Kostochka–Sudakov proved (survey §4, Proposition 4.1, via a Hamming-cube construction) that one cannot in general get a *linear*-size $U$ in which *every* pair (not just almost every pair) has linearly many common neighbors — a genuine limitation of the basic lemma. - $d$-set / almost-all variant (Lemma 6.3): for $\epsilon>0$, $d\le n$, $G$ with $N>4d\epsilon^{-d}n$ vertices and $\ge \epsilon N^2/2$ edges, there is $U$, $|U|>2n$, such that the fraction of *bad* $d$-subsets of $U$ (common neighborhood $<n$) is $<(2d)^{-d}$ — used with a matching embedding lemma (Lemma 6.4) to embed any bounded-degree bipartite graph, giving linear Ramsey-number bounds for bounded-degree graphs (Theorem 6.1, Corollary 6.2: $r(H)\le \Delta\,2^{\Delta+3}n$ for $H$ bipartite, $n$ vertices, max degree $\Delta$). - Nested / iterated variant (Jiang–Longbrake, arXiv:2201.10699, "Tree-degenerate graphs and nested dependent random choice"): apply the basic lemma recursively, layer by layer, following a tree/recursive decomposition of the target graph $H$, so the "rich common-neighborhood" guarantee is inherited and compounded down the recursion instead of being applied only once at the top level — needed when $H$ has unbounded degree overall but bounded degree only in a nested/recursive sense (tree-degenerate graphs), a strictly larger class than bounded-degree or one-sided-bounded-degree graphs.

Facts

- Origin and naming. Early versions were proved and applied independently by Rödl, Gowers, Kostochka, and Sudakov (Fox–Sudakov survey, §1, citing [60] Kostochka–Rödl 2001, [49] Gowers 2001, [81] Sudakov 2003); the unifying name "dependent random choice" and the systematic treatment (basic Lemma 2.1, and the variants above) are due to J. Fox and B. Sudakov, "Dependent Random Choice," arXiv:0909.3271 (2009), published *Random Structures & Algorithms* 38 (2011), 68–99 — the standard reference for the whole technique family. - Why "dependent." The random object chosen (the common neighborhood $A=N(T)$ of a random tuple $T$) is not itself a uniformly random subset of vertices — its membership probabilities for different vertices are *dependent* on one another through the shared random tuple $T$ — yet this dependence is exactly what makes bad (sparse-neighborhood) subsets unlikely to survive into $A$: a subset $S$ with small $|N(S)|$ has small probability of being $\subseteq N(T)$ precisely because all $t$ elements of $T$ would independently need to land in the small set $N(S)$. - Four quick applications given in the survey (§3), each a direct one-shot use of Lemma 2.1 + an embedding lemma: 1. *Turán numbers of bipartite graphs with one side bounded degree* (Alon–Krivelevich–Sudakov 2003; survey Theorem 3.1): if $H=(A\cup B,F)$ bipartite with every vertex of $B$ having degree $\le r$, then $\mathrm{ex}(n,H)\le cn^{2-1/r}$, $c=c(H)$ — best possible for every fixed $r$. 2. *1-subdivisions of complete graphs* (Alon–Krivelevich–Sudakov; survey Theorem 3.3): a graph with $n$ vertices and $\epsilon n^2$ edges contains a 1-subdivision of $K_a$ for $a=\epsilon^{3/2}n^{1/2}$ — resolving a question of Erdős on strengthening the Mader/Erdős–Hajnal topological-minor theorem. 3. *Ramsey number of the hypercube* (survey Theorem 3.4): $r(Q_r)\le 2^{3r}$, an easy polynomial bound from the basic lemma alone (the survey later sharpens the exponent to $2^{2r+o(r)}$ using the refined bounded-degree machinery of §6), resolving decades-open sub-questions of the Burr–Erdős conjecture that $r(Q_r)$ is linear in $|V(Q_r)|=2^r$. 4. *Ramsey–Turán for $K_4$-free graphs* (Sudakov; survey Theorem 3.5): $RT(n,K_4,f(n))=o(n^2)$ for $f(n)=2^{-\omega(n)\sqrt{\log n}}n$ with $\omega(n)\to\infty$ arbitrarily slowly — strengthens the classical Bollobás–Erdős/Szemerédi $RT(n,K_4,o(n))=(1+o(1))n^2/8$ theorem to a much smaller allowed independence number, via a proof-by-contradiction: the rich set $U$ from Lemma 2.1 must (since $\alpha(G)<a$) contain an edge $\{u,v\}$ whose $\ge a$ common neighbors are then forced to be independent (else a $K_4$ appears), contradicting $\alpha(G)<a$. - A genuine limitation of the basic lemma, proved via a Hamming-cube (Kostochka–Sudakov) construction in survey §4: there exist dense graphs (density $\ge 1/4$) on $n$ vertices such that every linear-size vertex subset contains some pair with only $o(n)$ common neighbors — so one cannot in general strengthen Lemma 2.1 to get *both* $|U|=\Theta(n)$ *and* every-pair-common-neighborhood $=\Theta(n)$ simultaneously. This is exactly why the "almost-all-pairs" variant (Lemma 5.1, relaxing "every pair" to "$(1-\epsilon)$-fraction of pairs") had to be developed separately, and it is this weaker variant — not the basic lemma — that powers the Balog–Szemerédi–Gowers theorem. - Balog–Szemerédi–Gowers theorem via dependent random choice (survey §5, following Gowers' 2001 proof of Szemerédi's theorem on arithmetic progressions): if $A,B$ are size-$n$ integer sets, $G$ a bipartite graph between them with $\ge cn^2$ edges and $|A+_G B|\le Cn$ (the *partial* sumset restricted to edges of $G$), then there exist $A'\subset A,B'\subset B$ with $|A'|,|B'|\ge cn/8$ and $|A'+B'|\le 2^{12}C^3c^{-5}n$. Gowers' innovation over the original Balog–Szemerédi regularity-lemma proof was replacing its *tower-type* dependence between parameters with a *polynomial* one — dependent random choice (via the paths-of-length-3 Lemma 5.2, itself built from the almost-all-pairs Lemma 5.1) is the mechanism that achieves this polynomial bound. - Ramsey numbers of bounded-degree and degenerate graphs. The Burr–Erdős conjecture (1975) that $r(H)\le c(\Delta)\cdot n$ for every $n$-vertex, max-degree-$\Delta$ graph $H$ was first proved via Szemerédi's regularity lemma (Chvátal–Rödl–Szemerédi–Trotter), giving a *tower-type* $c(\Delta)$; dependent random choice (survey §6, via Lemma 6.3/6.4 and Theorem 6.1) gives the far better bound $c(\Delta)<2^{c\Delta\log\Delta}$ for bipartite $H$ (Corollary 6.2: $r(H)\le \Delta 2^{\Delta+3}n$), avoiding the regularity lemma's tower-type loss entirely — and the same machinery extends to bounded-degree $k$-uniform hypergraphs (survey Theorem 6.5, giving $c(\Delta,k)\le t_k(c\Delta)$, dramatically better than the Ackermann-type bound that regularity methods give). - Extremal-graph-theory reach (this wiki's own cross-links). Dependent random choice is the standard upper-bound engine for $r$-degenerate bipartite Turán numbers: Füredi (1991) and independently Alon–Krivelevich–Sudakov 2003 use it for the one-sided-bounded-degree case $\mathrm{ex}(n,H)=O(n^{2-1/r})$ (solved special case of Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, documented in wiki/problems/kst-one-sided-degree-turan.md, slug solved/kst-one-sided-degree-turan); Jiang–Longbrake's *nested* dependent random choice (arXiv:2201.10699) extends this to the larger "tree-degenerate" class, unifying it with Grzesik–Janzer–Nagy's tree-blow-up theorem and Conlon–Fox–Sudakov's Sidorenko-conjecture result (documented in wiki/problems/tree-degenerate-graphs-turan.md, slug solved/tree-degenerate-graphs-turan); the fully general $r$-degenerate conjecture remains open (Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$), as does the companion lower-bound conjecture (Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$) and the general bipartite Turán-number problem (Erdős #713 — does every bipartite graph have a Turán exponent?). - Hypergraph-Ramsey / Erdős–Hajnal-type reach. Conlon–Fox–Sudakov use dependent random choice (combined with a counting-to-blow-up theorem of Nikiforov) to prove almost-monochromatic-subset results in hypergraphs (arXiv:0901.3912, arXiv:1104.5544, arXiv:0808.3760), resolving the $t=3$ case of an Erdős–Hajnal discrepancy question from 1989 — documented in wiki/problems/161.md (Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?), where the $t\ge4$ case remains open and is flagged as a candidate target for the same machinery.

Technique

WHEN it applies. Reach for dependent random choice when: 1. You have a dense host graph $G$ (edge density bounded below, e.g. $\ge\epsilon\binom n2$ or average degree $\ge d$) and want to embed a specific target graph/subgraph $H$ into it — especially when $H$ is bipartite, sparse, or has one side of bounded degree. 2. A direct greedy embedding of $H$ into $G$ fails because $G$'s common neighborhoods aren't a priori large enough for *every* small subset simultaneously (a naive union bound over all subsets can fail — recall the Kostochka–Sudakov limitation above), but you only need this for a carefully chosen rich subset $U\subset V(G)$, not all of $V(G)$. 3. The target parameter has the shape "Turán number of a bipartite/degenerate graph," "Ramsey number of a sparse/bounded-degree graph," "find a specific bipartite substructure (subdivision, blow-up) in a graph with $\ge \epsilon n^2$ edges," or an additive-combinatorics statement reducible to a sumset/common-neighborhood question (Balog–Szemerédi–Gowers).

WHY it works (the mechanism). A single random *tuple* $T$ of $t$ vertices (chosen with repetition, so effectively a random point of $V^t$) has common neighborhood $A=N(T)$ whose expected size is large by convexity of $z\mapsto z^t$ applied to the degree sequence — this pulls in the "denser-than-average" part of the neighborhood structure. Simultaneously, any fixed small subset $S$ with a small common neighborhood is very unlikely to end up entirely inside $A$, because *all* $t$ (independently drawn) elements of $T$ would have to fall inside $S$'s (small) neighborhood — the probability decays like $(|N(S)|/n)^t$, exponentially in $t$. A union bound over the polynomially-many candidate bad subsets $S$ (there are $\binom nr$ of them) is therefore beaten by choosing $t$ large enough, exactly as in the alteration method's Markov/union-bound recipe (see The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs) — but here the "random object" is a *common neighborhood of a random tuple*, not a random subgraph, which is the twist that makes the surviving set $U$ automatically well-connected into the rest of $G$ (every small subset of $U$ retains a big common neighborhood), a property a plain random vertex subset would not have with useful parameters.

The reusable recipe

1. Choose $t$ (the tuple size) to balance two competing forces exactly as in the basic Lemma 2.1 proof: larger $t$ makes $\mathbb E[X]=d^t/n^{t-1}$ shrink relative to $n$ unless $d$ is close to $n$ (favors small $t$), while larger $t$ makes the bad-event probability $(m/n)^t$ decay faster (favors large $t$). The correct $t$ is almost always dictated by the target embedding's parameters (e.g. $t=r$, the max one-sided degree of $H$, for the basic KST-type application; $t\propto \log n/\log(1/\epsilon)$ for the 1-subdivision application). 2. Set $(a,d,m,n,r)$ from the target embedding's shape: $r$ = the "test tuple size" needed by the embedding lemma (often the max degree of one side of $H$), $m$ = the number of common neighbors the embedding lemma needs per $r$-tuple (often $|V(H)|$), $a$ = the size of the rich set needed (often $|A(H)|$, one side of $H$). 3. Check Lemma 2.1's inequality $d^t/n^{t-1} - \binom nr (m/n)^t \ge a$ holds for your choice — this is almost always a short calculus/algebra check, not a deep step. 4. Invoke an embedding lemma (greedy, vertex-by-vertex, exploiting that every relevant $r$-tuple already placed has $\ge m$ available common neighbors to place the next vertex in) to conclude $H\subseteq G$. 5. If a single (non-nested) application only gives a weak exponent or fails to reach the target class of graphs (e.g. degenerate but not one-sided-bounded-degree $H$), escalate to a nested/recursive application (Jiang–Longbrake), applying the lemma again *inside* the common-neighborhood set returned by the outer application, following $H$'s own recursive/tree decomposition. 6. **If you need "almost every small subset is rich" rather than "every small subset is rich" with a *linear*-size $U$** (recall: getting both simultaneously is impossible in general, per the Kostochka–Sudakov obstruction), use the Cauchy–Schwarz-based single-random-vertex variant (Lemma 5.1) instead of the multi-vertex tuple $T$ — this is the version needed for additive-combinatorics applications (Balog–Szemerédi–Gowers) and for $C_{2k}$-connectivity-type results.

HOW to use this to prove new things (recombination guidance for a solver). - If a problem reduces to "show a dense graph contains [some specific bipartite/sparse substructure]," first ask whether a greedy vertex-by-vertex embedding would work *if only* every small subset of some target set had a large common neighborhood — if yes, dependent random choice is very likely to supply exactly that set, and the rest of the proof is often "choose parameters, check one inequality, invoke a generic embedding lemma." - The degree-side asymmetry matters: dependent random choice is naturally suited to graphs $H$ where degree is bounded on (at least) one side, because the test-tuple size $t\approx r$ scales with that bound; for graphs with unbounded degree on both sides, or "degenerate but not bounded-degree" graphs, plain dependent random choice typically falls short (as in the still-open general case of Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, where AKS03's bound is $n^{2-1/(4r)}$, not the conjectured sharp $n^{2-1/r}$) — the standard escalation is the nested/iterated variant (Jiang–Longbrake) or switching to an entirely different technique (algebraic/random-algebraic constructions, e.g. Bukh–Conlon, for matching lower bounds). - Dependent random choice is fundamentally an existence/upper-bound technique for embeddings (equivalently, upper bounds on Turán and Ramsey numbers) — it does not by itself supply matching lower-bound constructions; pair it with explicit algebraic constructions (finite-field/norm-graph constructions, Finite-field / projective-plane constructions for extremal additive sets) or probabilistic alteration-type lower-bound arguments (The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs) when the target problem asks for a tight two-sided bound. - When the union-bound step in the basic lemma's proof feels too lossy (e.g. bad-event probability doesn't decay fast enough in $t$ for your parameter regime), consider whether the almost-all-pairs Cauchy–Schwarz variant (Lemma 5.1) gets you further, since it trades "every subset is rich" for "an explicit $(1-\epsilon)$-fraction is rich," which is often all a subsequent embedding argument (or an additive-combinatorics sumset argument) actually needs. - This technique composes cleanly with greedy/inductive embedding as its natural partner (Lemma 3.2, Lemma 6.4) — the two-step "manufacture rich set, then greedily embed" shape recurs across nearly every cited application, so when adapting to a new target graph $H$, the main creative freedom is in designing the embedding-lemma's induction (the order in which $H$'s vertices are placed) to match whatever "richness" guarantee the dependent-random-choice step delivers.

Related

- The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs — the more general "random object + first-moment/union-bound repair" template that dependent random choice specializes: here the "random object" is a common neighborhood of a random tuple (not a random subgraph/subset directly), and the "repair" deletes bad $r$-tuples rather than bad local patterns, but the union-bound-beats-bad-event-count mechanism is identical. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — an alternative escalation from first-moment arguments (variance/Cauchy–Schwarz) that Lemma 5.1's proof itself uses in place of the plain multi-vertex expectation trick, when only a linear (not full) rich subset is achievable. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings and Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent — sibling probabilistic-existence techniques for dense/sparse-structure problems; unlike dependent random choice, neither is specifically tailored to the "common neighborhood of a random tuple" embedding template, and both are typically reached for when the target structure is a global coloring/packing rather than a subgraph embedding. - Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — OPEN: general $r$-degenerate bipartite Turán conjecture ($\mathrm{ex}(n,H)=O(n^{2-1/r})$); dependent random choice (AKS03, one-sided case) and its nested extension (Jiang–Longbrake, tree-degenerate case) are the state-of-the-art upper-bound tools, but the fully general case is unresolved. - Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ — OPEN: companion lower-bound conjecture in the same Turán-degeneracy family; the "toolkit still-live" note in this wiki explicitly flags dependent random choice/supersaturation as the relevant technique family. - Erdős #713 — does every bipartite graph have a Turán exponent? — the general bipartite Turán-number \$500 conjecture; dependent random choice is cited as the standard upper-bound technique for special cases, contrasted with algebraic/finite-geometric lower-bound constructions capped by the Feit–Higman theorem. - Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? — OPEN for $t\ge4$: hypergraph discrepancy/almost-monochromatic-subset problem; Conlon–Fox–Sudakov's $t=3$ resolution uses dependent random choice combined with Nikiforov's counting-to-blow-up theorem. - solved/kst-one-sided-degree-turan — Alon–Krivelevich–Sudakov 2003's full proof (Lemma 2.1/Theorem 2.2/Corollary 2.3) documented in detail in this wiki, the cleanest worked example of the basic lemma + greedy embedding recipe. - solved/tree-degenerate-graphs-turan — Jiang–Longbrake's nested dependent random choice, the concrete "escalate by nesting" example documented in this wiki.