Frieze's trick — boosting a positive-probability (second-moment) existence bound to whp via the vertex-exposure martingale

Statement

Let $G_{n,p}$ be the Erdős–Rényi random graph with $p=d/n$, $d$ a large constant (the sparse regime, as opposed to the classical dense case $0<p<1$ fixed). Let $\alpha(G)$ denote the independence number (size of the largest independent set).

Question (implicit in Erdős–Rényi-era random graph theory, resolved by Frieze 1990): what is $\alpha(G_{n,p})$ asymptotically, and — crucially — does it concentrate tightly around a single deterministic value, or only around its mean up to lower-order fluctuations that are hard to pin down without knowing the mean exactly?

The first-moment method alone gives an upper bound: $\mathbb P(\alpha(G_{n,p})\ge k)\to 0$ for $k$ somewhat above $(2n/d)\log d$ (Markov's inequality on the count of independent $k$-sets). It gives no matching lower bound — a positive expected count of large independent sets is consistent with $\alpha$ usually being small and occasionally huge. Getting a whp (with-high-probability, i.e. probability $\to 1$) two-sided bound on $\alpha(G_{n,p})$ additionally requires (a) an existence argument that only needs to succeed with some non-negligible (not necessarily $\to 1$) probability, and (b) a way to promote that into a full whp statement.

Facts

- Origin: A. M. Frieze, "On the independence number of random graphs," *Discrete Mathematics* 81(2):171–175 (1990) (book bibliography entry lists pp. 171–176 — page-range discrepancy across secondary sources, not resolved here). - The dense case is easier and predates this: for $0<p<1$ fixed, D. Matula (1976) showed $\alpha(G_{n,p})\approx 2\log_b n$ ($b=1/(1-p)$) via first moment (upper bound, Markov) plus Janson's inequality (lower bound, an *exponential*-tail second-moment-type tool) directly giving $\mathbb P(X_k=0)\le \exp(-\Omega(n^2/(\log n)^5))$ — i.e. in the dense regime the existence bound is *already* whp, no boosting trick needed (Frieze–Karoński book, Thm 7.3, its proof read in full). - Why the sparse case is different: in the sparse regime $p=d/n$, the analogous second-moment computation for $X_{k_0}$ (count of independent sets of the conjectured near-optimal size $k_0=(2-\varepsilon/8)\frac{\log d}{d}n$) only yields $\mathbb P(X_{k_0}>0)\ge\exp\!\big(-O((\log d)^{3/2}d^{-2}n)\big)$ (book's inequality (7.11)) — a probability that is *not* $\to 1$ (indeed $\to 0$, just much more slowly than the competing exponential-tail terms). A naive second-moment argument here proves only "large independent sets exist with some non-vanishing-relative-to-the-exponent probability," not "whp." Frieze's contribution is the extra step that converts this into the full two-sided whp statement. - Theorem 7.4 (Frieze 1990, as restated in Frieze–Karoński, "Introduction to Random Graphs," §7.2): for fixed $\varepsilon>0$ and $d\ge d(\varepsilon)$, whp $$\Big|\alpha(G_{n,p}) - \tfrac{2n}{d}\big(\log d - \log\log d - \log 2 + 1\big)\Big| \le \tfrac{\varepsilon n}{d}, \qquad p=d/n.$$ - Dani & Moore later gave a sharper refinement of this result (cited in the Frieze–Karoński book, bibliography ref. [327], not independently verified here). - The same book chapter immediately reuses $\alpha(G_{n,p})$'s dense-case whp concentration (Theorem 7.3, via Janson's inequality) as a black-box input to the classical chromatic number bound $\chi(G_{n,p})\approx n/(2\log_b n)$ (Bollobás 1988) — evidence this whole cluster of results (independent sets → chromatic number) is a load-bearing dependency chain in random graph theory.

Solution

Answer: $\alpha(G_{n,p}) = \frac{2n}{d}\big(\log d - \log\log d - \log 2 + 1 + o(1)\big)$ whp, for $p=d/n$ and $d\to\infty$ (any rate, including $d$ a large constant) — Theorem 7.4 above.

**The transferable technique ("Frieze's trick"): decouple *where* the value concentrates from *how tightly* it concentrates, using two independent tools, then recombine.**

The proof of Theorem 7.4 (Frieze–Karoński book, pp.128–131, read in full) runs three separate probabilistic estimates and then a purely algebraic combination step:

1. Concentration (tightness), independent of the unknown mean — vertex-exposure martingale + Azuma–Hoeffding. Write $Z=\alpha(G_{n,p})=Z(Y_2,\dots,Y_n)$ where $Y_i$ is the set of edges between vertex $i$ and vertices $[i-1]$ (revealing the graph vertex by vertex — the *vertex-exposure* martingale, as opposed to edge-exposure). The $Y_i$ are independent, and — crucially — changing a single $Y_i$ (i.e. rewiring one vertex's connections to its predecessors) can change $\alpha(G)$ by at most 1 (adding/removing a vertex's edges can add or remove that vertex from an optimal independent set, nothing more). This "bounded-difference" / vertex-Lipschitz property is exactly the hypothesis of Azuma–Hoeffding for the induced Doob martingale $\mathbb E[Z\mid Y_2,\dots,Y_i]$, giving directly, for any $t>0$: $$\mathbb P(|Z-\mathbb E Z|\ge t)\le \exp\!\Big(-\frac{t^2}{2n}\Big).$$ With $t=\varepsilon(\log d/8d)\,n$ this is inequality (7.9) in the book: $\mathbb P(|\alpha-\mathbb E\alpha|\ge \varepsilon n\log d/(8d))\le\exp(-\Omega((\log d)^2 n/d^2))$. Note this bound says nothing about what $\mathbb E\alpha$ actually is — it only pins down that $\alpha$, whatever its mean, is confined to a window of width $O(\varepsilon n\log d/d)$ around that mean, whp. This is the general-purpose "cheap" half of the argument: it needs no fine control of the combinatorics of independent sets beyond the one-vertex-Lipschitz property. 2. Pin the mean from above — first moment / Markov, cheap and standard. For $k_1=(2+\varepsilon/8)(\log d/d)n$ (slightly above the conjectured value), $\mathbb E X_{k_1}=\binom nk_1(1-p)^{\binom{k_1}2}$ is computed directly and shown $\le\exp(-\Omega((\log d)^2 n/d))$, giving $\mathbb P(\alpha\ge k_1)\to 0$ superexponentially fast (inequality (7.10)) — a routine one-sided first-moment bound. 3. **Pin the mean from below — second moment on a *positive-probability* (not whp) event. For $k_0=(2-\varepsilon/8)(\log d/d)n$ (slightly below the conjectured value), Markov's inequality on $\mathbb E[X_{k_0}^2]/(\mathbb E X_{k_0})^2$ (a Paley–Zygmund-style computation, summing over the overlap sizes $j$ of pairs of $k_0$-subsets) shows $\mathbb P(X_{k_0}>0)\ge\exp(-O((\log d)^{3/2}n/d^2))$ (inequality (7.11)) — a bound that is not** whp (its RHS $\to 0$, just at a controllably slow rate relative to steps 1–2's much faster exponentials) but is enough to say the event "$\alpha\ge k_0$" is *not negligible on the scale that matters*. 4. The recombination — pure algebra, no further probability. This is the crux of the trick. From step 1, $\alpha$ is confined whp to an interval $I$ of width $\varepsilon n\log d/(4d)$ around $\mathbb E\alpha$. If $\mathbb E\alpha$ were much less than $k_0$, then combining with step 3 — a nonzero-probability event that $\alpha \ge k_0$ lies *outside* the high-probability window $I$ around a much smaller mean — would make the two probability bounds from steps 1 and 3 contradict each other (the tail bound in step 1 decays *faster*, as a function of $n$, than the "failure margin" needed, since $(\log d)^2 n/d^2 \gg (\log d)^{3/2}n/d^2$ in the exponent for large $d$). Algebraically this forces $\mathbb E\alpha \ge k_0 - \varepsilon n\log d/(8d)$ (the book's (7.12)). Symmetrically, steps 1+2 force $\mathbb E\alpha \le k_1+\varepsilon n\log d/(8d)$ (7.13). Together: $\mathbb E\alpha$ itself is now pinned to within $O(\varepsilon n\log d/d)$ of $k_0\approx k_1$. Finally, reapplying step 1's concentration bound (now that the mean is known) converts "$\alpha$ is close to *some* mean" into "$\alpha$ is close to *the specific asymptotic value* $\frac{2n}{d}(\log d-\log\log d-\log2+1)$" — the full whp statement (7.8), Theorem 7.4.

Why this is the reusable move, not just this one proof. The two ingredients are deliberately *decoupled and interchangeable*: - Concentration engine: any bounded-difference / Lipschitz martingale argument (vertex-exposure here; edge-exposure, or McDiarmid's inequality more generally, in other problems) that shows the target statistic sits in a *narrow window around its mean*, without needing to know or compute that mean. - Existence engine: any argument — first/second moment, Janson, Lovász Local Lemma, entropy, or an explicit construction — that only needs to show a target value is achieved with probability *not absurdly smaller* than the concentration window's failure probability (it does not need to itself be whp, or even bounded away from $0$; it only needs a lower bound that beats the concentration tail in the exponent). - The algebra in step 4 is generic: *if* $Z$ is whp within $w$ of $\mathbb E Z$, *and* $\mathbb P(Z\ge k)\ge q \gg \exp(-\text{(concentration's own tail rate)})$, *then* $\mathbb E Z \ge k - w$. This lets a "merely positive-probability" (or even just "not implausibly small probability") existence bound get promoted to a statement about the *mean*, and the concentration bound is then reapplied to promote *that* into a sharp whp statement about the random variable itself. - Portable takeaway for open problems: whenever a target extremal parameter of a random structure (i) is provably Lipschitz/bounded-difference under one-object exposure (vertex, edge, cell, coordinate, ...) — the concentration half is then a one-line Azuma–Hoeffding application — and (ii) has *any* existence argument (however weak, even non-whp) pinning down its rough scale via first/second moment, the two can always be algebraically recombined exactly as in step 4 to upgrade the weak existence bound into a sharp two-sided whp concentration result. This is the general schema Frieze's 1990 paper introduced for sparse-graph independence numbers, and it is the template this wiki flags for any open problem asking to convert an "exists with positive/non-negligible probability" bound into a "whp" bound for a random combinatorial structure.

Related

- Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — supplies steps 2–3 of the proof (the first/second-moment existence bounds on $X_{k_0}, X_{k_1}$); this page's technique is precisely about what to do *after* a second-moment argument gives only a positive-probability (not whp) bound. - Vertex-exposure martingale + Azuma–Hoeffding concentration for graph parameters — the general concentration engine (step 1: Shamir–Spencer 1987 / Bollobás 1988 machinery) this page instantiates for $\alpha(G_{n,p})$ specifically; already referenced by this wiki's Independence/clique number of G(n,1/2) is two-point concentrated at ⌊α₀+o(1)⌋ and Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021) pages for the analogous dense-regime $\chi(G_{n,1/2})$ concentration, but not yet written as its own concept page — flagged as the natural next page given how load-bearing it is across this whole cluster. - Independence/clique number of G(n,1/2) is two-point concentrated at ⌊α₀+o(1)⌋ — the dense-regime ($p=1/2$ fixed) sibling result (Bollobás–Erdős 1976 / Matula 1970–72): there $\alpha(G_{n,p})$ is in fact *two-point* concentrated, because Janson's inequality supplies a directly whp existence bound and no positive-probability-to-whp boosting step is needed. Frieze's 1990 sparse-regime theorem is the harder case where that shortcut fails and the martingale-boosting trick on this page becomes necessary. - Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021) — a cautionary contrast in the *same* technique family: Heckel's coupling proof shows the chromatic number of $G_{n,1/2}$ is emphatically not tightly concentrated, by exploiting fluctuation of the same independent-set-count random variable $X_k$ that this page's step 3 controls — evidence that the boosting trick's power (turning weak existence into sharp concentration) does not transfer to every random-graph parameter. - Ramsey-type concentration of the independence/clique number of G(n,1/2) — the concept-level pointer to the classical dense-regime independence/clique-number concentration result line that this page's sparse-regime theorem extends.