Vertex-exposure martingale + Azuma–Hoeffding concentration for graph parameters

Statement

Azuma–Hoeffding inequality. Let $(Z_i)_{i=0}^n$ be a martingale (with respect to some filtration / some sequence $(X_i)$) such that the increments are bounded: $|Z_i - Z_{i-1}| \le c_i$ almost surely for every $i$. Then for every $\lambda \ge 0$, $$\Pr[|Z_n - Z_0| \ge \lambda] \;\le\; 2\exp\!\left(-\frac{\lambda^2}{2\sum_{i=1}^n c_i^2}\right).$$ (Hoeffding 1963 proved the i.i.d.-sum case and remarked that his argument extends to martingale differences; Azuma, "Weighted sums of certain dependent random variables," *Tôhoku Math. J.* 19 (1967), gave the martingale formalization; a related bound was already implicit in Bernstein 1937. en.wikipedia.org/wiki/Azuma's_inequality.) If only an upper (or lower) tail is wanted, the constant $2$ drops to $1$.

The Doob martingale. Given a function $f(X_1,\dots,X_n)$ of a sequence of random variables and any *exposure ordering* of the $X_i$, define $$Z_i := \mathbb E[f(X_1,\dots,X_n) \mid X_1,\dots,X_i], \qquad i=0,1,\dots,n,$$ so $Z_0 = \mathbb E[f]$ (nothing revealed) and $Z_n = f$ (everything revealed). $(Z_i)$ is automatically a martingale with respect to $(X_i)$ (tower property of conditional expectation) — this holds for any choice of ordering/grouping of the underlying randomness, which is exactly the freedom the technique exploits. (A. Gupta, CMU 15-859M Lec. 19, Lemma 2.)

Lipschitz $\Rightarrow$ bounded differences (McDiarmid's inequality). If the $X_i$ are independent and $f$ is $(c_i)$-Lipschitz — i.e. changing only the $i$-th coordinate changes $f$ by at most $c_i$ — then the associated Doob martingale automatically has $|Z_i - Z_{i-1}| \le c_i$ (Gupta, Lemma 4), so Azuma–Hoeffding gives $$\Pr[|f - \mathbb E f| \ge \lambda] \;\le\; 2\exp\!\left(-\frac{\lambda^2}{2\sum_i c_i^2}\right).$$ This packaged corollary is what is usually called McDiarmid's (bounded-differences) inequality (McDiarmid, "On the method of bounded differences," *Surveys in Combinatorics 1989*, LMS Lecture Note Series 141, 148–188).

The vertex-exposure martingale for graph parameters. For a graph parameter $f$ on the random graph $G_{n,p}$ on labelled vertex set $[n]$, order the underlying randomness by vertex rather than by edge: let $X_i$ be the (random) set of edges from vertex $i$ to vertices $1,\dots,i-1$. Revealing $X_1,\dots,X_n$ in order reveals the whole graph, in $n$ steps rather than $\binom n2$. If $f$ is $1$-Lipschitz under "add/change one vertex's incident-edge pattern" (formally: changing the edges at a single vertex changes $f$ by at most $1$), the vertex-exposure Doob martingale $Z_i=\mathbb E[f\mid X_1,\dots,X_i]$ has $|Z_i-Z_{i-1}|\le 1$ for all $i=1,\dots,n$, and Azuma–Hoeffding gives $$\Pr[|f - \mathbb E f| \ge \lambda] \;\le\; 2\exp\!\left(-\frac{\lambda^2}{2n}\right),$$ i.e. $f$ is concentrated in a window of width $O(\sqrt n)$ around its mean, with high probability. This is the archetypal instance; the same recipe transports to any $[n]$-indexed family of graph/hypergraph parameters with an analogous one-vertex-change Lipschitz bound.

Facts

- The chromatic number, the founding example. Shamir & Spencer, "Sharp concentration of the chromatic number on random graphs $G_{n,p}$," *Combinatorica* 7 (1987), 121–129: a direct application of Azuma–Hoeffding to the vertex-exposure martingale shows $\chi(G_{n,p})$ lies whp in an interval of width $O(\omega(n)\sqrt n)$ for any $\omega(n)\to\infty$, for every edge probability $p=p(n)$ — this was the first use of martingale concentration in random graph theory (Kang–McDiarmid survey, p.9). Note the proof gives concentration with no information about where the interval is located — a recurring limitation of the method. - Why edge-exposure fails here but vertex-exposure works — the canonical illustration of the "choose the right exposure ordering" idea. With the *edge*-exposure martingale ($n_i:=$ the $i$-th of the $\binom n2$ edges, $\chi$ is $1$-Lipschitz in each edge), Azuma–Hoeffding only gives $\Pr[|\chi-\mathbb E\chi|\ge\lambda]\le 2\exp(-\lambda^2/2\binom n2)$, vacuous unless $\lambda\approx n$ — useless since $\chi\in[1,n]$ (Gupta Lec. 19, §2.1, worked explicitly). With the *vertex*-exposure martingale (only $n$ steps, same $1$-Lipschitz bound per step because changing one vertex's edges changes $\chi$ by at most $1$: recolour that one vertex), the sum of squared step-bounds drops from $\binom n2$ to $n$, giving the meaningful $O(\sqrt n)$ bound above. The number of exposure steps, not just the per-step Lipschitz constant, controls the final concentration width — this is the single most important tuning knob of the technique. - Sharpening the leading-order value. Bollobás, "The chromatic number of random graphs," *Combinatorica* 8 (1988), 49–55: combines a martingale argument (a two-random-variable comparison, one with an easy expectation lower bound, one a martingale amenable to Azuma–Hoeffding) with a strong upper tail bound on the independence number to pin down $\chi(G_{n,1/2}) \sim n/(2\log_2 n)$ whp — the vertex-exposure/Azuma machinery supplies the *concentration*, a separate first/second-moment argument supplies the *location*. - Sparse regime, two-point concentration. Shamir–Spencer also showed that for $p=n^{-\alpha}$, $\alpha>\tfrac12$, $\chi(G_{n,p})$ is confined whp to an interval of *constant* width (dependent on $\alpha$) via the same martingale method. Łuczak (1991) sharpened this to genuine two-point concentration (only 2 possible values whp) for $\alpha>\tfrac56$; Alon & Krivelevich later extended two-point concentration to all $\alpha>\tfrac12$, but via a *different* technique (recolouring through the Lovász Local Lemma, not martingales) — evidence that the martingale method alone caps out and needs to be combined with or replaced by other tools to reach the sharpest results (Kang–McDiarmid survey, §3). - Independence/stability number. The same vertex-exposure + Azuma–Hoeffding combination underlies martingale-based upper-tail control on the stability number $\alpha(G_{n,p})$ (used, e.g., by Bollobás's proof above, and by Frieze (1990) for sparse $G_{n,p}$, per Kang–McDiarmid §3) — complementing the (typically second-moment-based) lower-tail / existence side. - Beyond graphs: any bounded-difference statistic of independent inputs. The abstracted corollary (McDiarmid's inequality) needs no graph structure at all — only (a) independence of the underlying inputs and (b) a Lipschitz bound on how much a single input can move the output. Classic non-graph example: the Euclidean TSP tour length $\tau$ on $n$ i.i.d. uniform points in $[0,1]^2$ is $2\sqrt2$-Lipschitz in each point, giving $\Pr[|\tau-\mathbb E\tau|\ge\lambda]\le 2\exp(-\lambda^2/16n)$ by the naive Lipschitz bound (Gupta Lec. 19, §3) — but a refined, non-uniform bound $|Z_i-Z_{i-1}|=O(1/\sqrt{n-i})$ (obtained by directly estimating the effect of resampling the $i$-th point via its expected distance to the remaining $n-i$ points, rather than using the worst-case Lipschitz constant) gives $\sum c_i^2=O(\log n)$ instead of $O(n)$, sharpening the concentration window from $O(\sqrt{n\log n})$ down to $O(\sqrt{\log n})$. This "bound the martingale differences directly, don't just invoke a global Lipschitz constant" refinement is the standard second-level move once the basic vertex/coordinate-exposure setup is in place. - Limitation exploited by later work. The $O(\sqrt n)$ (or $O(\omega\sqrt n)$) width from vertex-exposure/Azuma–Hoeffding is an *upper bound* on the concentration window, proved by a worst-case per-step bound; it says nothing about whether the true window is actually that wide. Heckel's non-concentration result for $\chi(G_{n,1/2})$ (arXiv:1906.11808, JAMS 2021) and its sharpening by Heckel & Riordan (arXiv:2103.14014, JLMS 2023, unconditionally reaching $n^{1/2-o(1)}$ for some $n$) show this $O(\sqrt n)$ bound is close to tight — i.e. the vertex-exposure martingale bound, unimprovable in general, is in fact essentially the truth for $\chi(G_{n,1/2})$ along a subsequence of $n$. See Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? and Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021).

Technique

When it applies: a function $f$ of $n$ (or $\binom n2$, or however many) pieces of independent randomness, where you can choose an *exposure ordering* of that randomness such that (a) revealing one more "unit" (a vertex's incident edges, a point, a coordinate) changes $f$ by at most a controllable amount $c_i$, and (b) the number of exposure steps is small enough that $\sum c_i^2$ is much smaller than $(\mathbb E f)^2$. It is the workhorse for proving that a combinatorial/geometric statistic of a random structure is sharply concentrated around its mean, *without* needing to know the mean's exact value, and without needing independence of the summands that make up $f$ (unlike Chernoff bounds for sums of independent variables) — only a Lipschitz/bounded-difference property of $f$ itself as a function of the exposure sequence.

Why it works (the mechanism): the Doob martingale $Z_i=\mathbb E[f\mid \text{first } i \text{ exposures}]$ interpolates deterministically from $Z_0=\mathbb E f$ to $Z_n=f$; Azuma–Hoeffding says a martingale that never jumps more than $c_i$ at step $i$ cannot random-walk far from its start with high probability — the same "sum of bounded, mean-zero, but *not necessarily independent* increments" intuition as Hoeffding's inequality for independent sums, except the martingale property (rather than independence) is what makes the exponential moment bound go through. The exposure ordering is a free design choice — choosing it so that (i) $f$ changes little per step and (ii) there are few steps is precisely how one converts a hard concentration question into an easy calculus bound on $\sum c_i^2$.

The reusable recipe

1. Identify the underlying source(s) of randomness for the object (e.g. the $\binom n2$ edge-indicators of $G_{n,p}$). 2. Choose an exposure ordering/grouping, not necessarily "one edge at a time." For graph parameters, grouping edges *by vertex* (vertex-exposure: reveal all of vertex $i$'s edges to earlier vertices at step $i$, for $i=1,\dots,n$) is the standard trick because it cuts the number of steps from $\binom n2$ down to $n$ while often preserving the same per-step Lipschitz bound — an immediate quadratic-to-linear improvement in $\sum c_i^2$, hence a $\sqrt n$-to-$1$ improvement inside the square root of the final bound's argument. 3. Prove the Lipschitz/bounded-difference bound: show that changing the outcome of one exposure step (e.g. recolouring/rewiring one vertex's incident edges) changes $f$ by at most $c_i$ — for $\chi$, this is immediate: delete the vertex, colour the rest, add the vertex back with one new colour if needed, so $c_i=1$ for all $i$. This step is usually a short, purely combinatorial argument ("surgery" on the structure), independent of any probability computation. 4. Sum $\sum_i c_i^2$ and plug into Azuma–Hoeffding to get $\Pr[|f-\mathbb E f|\ge\lambda]\le 2\exp(-\lambda^2/2\sum c_i^2)$; solving for the $\lambda$ that makes the RHS $\to 0$ (e.g. $\lambda=\omega(n)\sqrt{\sum c_i^2}$ for any $\omega\to\infty$) gives the concentration window. 5. If the crude Lipschitz bound is too weak (as in naive TSP or dense subgraph-count applications), bound $|Z_i - Z_{i-1}|$ *directly* rather than via a global worst-case Lipschitz constant — condition on the first $i-1$ exposures and estimate the actual expected effect of resampling the $i$-th piece, which is often much smaller than the crude worst case (e.g. $O(1/\sqrt{n-i})$ vs. a global $O(1)$ for TSP). This typically sharpens $O(\sqrt n)$-type bounds to $O(\sqrt{\log n})$-type bounds. 6. What this method does NOT give: (a) the *location* of the concentration interval (a separate first/second-moment or explicit-formula computation is needed for that — Shamir–Spencer's $O(\sqrt n)$-window result said nothing about where the window was; Bollobás's $n/(2\log_2 n)$ location required extra work); (b) *two-point* concentration (needs recolouring/local-lemma arguments à la Alon–Krivelevich, or problem-specific structure); (c) any guarantee that the bound is tight — the window it proves is only an *upper* bound on the true fluctuation, and can in fact be tight (as later confirmed for $\chi(G_{n,1/2})$ by Heckel's non-concentration result) or loose, depending on the parameter.

Related

- Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the complementary tool typically needed alongside vertex-exposure/Azuma to nail down *where* the concentration interval sits (e.g. Bollobás's $\chi(G_{n,1/2})\sim n/(2\log_2 n)$ combines both). - Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021) — Heckel's (2021) and Heckel–Riordan's (2023) proof that the $O(\sqrt n)$ upper bound this technique gives for $\chi(G_{n,1/2})$ is close to tight (unconditionally $n^{1/2-o(1)}$ for some $n$), the first genuine test of whether the classical vertex-exposure bound could be beaten. - Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — open Erdős–Gimbel cochromatic-number question whose best partial results build on both this concentration machinery and the non-concentration result above. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — an alternative route to concentration/threshold-type results in some of the same problem families, structurally distinct from martingale methods.