vertex- and edge-exposure martingales

Vertex- and edge-exposure martingales are the standard device for proving concentration of graph parameters around their means in random graphs, by realising a graph parameter as a martingale and applying the Azuma-Hoeffding inequality. The challenge is that interesting quantities — the chromatic number, the size of the largest clique, the length of the longest path — are complicated global functions of all the random edges, with no simple variance formula and no independence to exploit directly. The exposure martingale finesses this: it reveals the randomness one piece at a time and tracks the conditional expectation of the parameter, which by construction is a martingale, regardless of how complicated the parameter is.

Concretely, let f(G) be any graph parameter and let G be a random graph G(n,p). Order the randomness and define the martingale by exposing it gradually. In the edge-exposure martingale, list the C(n,2) potential edges e_1, ..., e_m in a fixed order and set X_i = E[f(G) given the status (present/absent) of e_1, ..., e_i]; then X_0 = E[f(G)], X_m = f(G), and (X_i) is a Doob martingale. In the vertex-exposure martingale, reveal the edges vertex by vertex: X_i = E[f(G) given all edges among the first i vertices]. The crucial point is the bounded-difference property: if changing the status of a single edge (or all edges at a single vertex) can change f by at most c, then the martingale has increments bounded by c, and Azuma-Hoeffding gives P(|f(G) - E[f(G)]| >= t) <= 2 exp(-t^2 / (2 m c^2)). For Lipschitz graph parameters this yields concentration with no variance computation at all.

Why this matters: it provides concentration for parameters where the second moment method is intractable, because Azuma needs only a worst-case bounded-difference (Lipschitz) constant, not detailed correlation structure. Vertex exposure is often far stronger than edge exposure: adding or removing a single vertex changes many parameters (like the chromatic number) by at most 1, giving m = n steps each with c = 1, hence concentration on a scale of sqrt(n) even though there are C(n,2) edges. The honest caveat is that Azuma's bound is only as good as the Lipschitz constant: a parameter that can swing wildly under a single edge change gives a useless bound, and the method shows concentration around the MEAN E[f(G)] but says nothing about where that mean is — locating E[f(G)] is a separate problem. It also typically gives concentration on a sqrt(n) scale, which can be far weaker than the truth (the chromatic number is concentrated on a much shorter interval than sqrt(n) for many p).