Why a mean is not enough
The earlier guides in this rung computed expectations and variances of combinatorial random variables — the number of triangles in G(n,p), the size of a maximum independent set, the chromatic number. But knowing E[X] and even Var(X) leaves a gap: an average is compatible with wild swings, and the second-moment method only gives polynomial-strength control through Chebyshev's inequality. What we want for the hardest problems is concentration: the statement that X lies within a tiny window around its mean not merely on average but with probability tending to 1 exponentially fast. This is the difference between 'the chromatic number is about k on average' and 'the chromatic number is k or k+1 with overwhelming probability'.
Where Vol I gave you concentration for sums of independent variables — Hoeffding and Chernoff bounds — combinatorial quantities are usually not sums of independent things. The number of triangles is a sum of strongly dependent indicators; the chromatic number is a tangled global function of all the edges. The art of combinatorial concentration is to find the right structure hiding inside that dependence. Two structures dominate this guide. The first is a martingale: even a complicated function reveals its randomness one coordinate at a time, and the running conditional expectation is a martingale we can control. The second is the special algebra of monotone events, which lets Janson's inequality turn a near-Poisson heuristic into a genuine exponential lower-tail bound.
Azuma's inequality and the exposure martingale
The engine is Azuma's inequality, the martingale generalization of Hoeffding. Suppose M_0, M_1, ..., M_n is a martingale with bounded increments, |M_k - M_(k-1)| <= c_k for each k. Then for any t > 0, P(|M_n - M_0| >= t) <= 2 * exp(-t^2 / (2 * sum_k c_k^2)). The hypotheses are exactly two: it must be a true martingale (E[M_k given F_(k-1)] = M_(k-1)), and the increments must be bounded almost surely. No independence is required — the martingale structure already builds in 'fairness' step by step, and the proof is the same Hoeffding-style bound on E[e^(theta(M_k - M_(k-1)))] applied conditionally and chained through the tower property.
How do we get a martingale out of a static quantity like the chromatic number? With the Doob exposure martingale. Let X = f(Z_1, ..., Z_n) be any function of independent random pieces Z_1, ..., Z_n, and define M_k = E[X given Z_1, ..., Z_k], the best guess for X after the first k pieces are exposed. By construction M_0 = E[X], M_n = X, and the tower property makes M_k a Doob martingale. We have manufactured a martingale that starts at the mean and ends at the random variable itself, so Azuma will bound how far X = M_n drifts from E[X] = M_0 — provided we can bound the increments. In graphs there are two canonical choices for the Z_k, giving the vertex- and edge-exposure martingales.
McDiarmid and the chromatic number
Packaging the exposure martingale once and for all gives the bounded differences inequality, also called McDiarmid's inequality — the form you actually reach for in practice. Suppose X = f(Z_1, ..., Z_n) with the Z_k independent, and f satisfies the bounded differences condition: changing any single coordinate Z_k, while holding the rest fixed, changes f by at most c_k. Then the Doob increments are bounded by c_k, Azuma applies, and P(|X - E[X]| >= t) <= 2 * exp(-t^2 / (2 * sum_k c_k^2)). You never have to mention martingales again; you just check one Lipschitz-type condition on f and read off the bound. This is the single most-used concentration tool in combinatorics.
The crown jewel is the concentration of the chromatic number. Let X = chi(G(n,p)). Use vertex exposure: revealing one new vertex (together with all its edges to earlier vertices) can change the chromatic number by at most 1, because the new vertex needs at most one extra colour. So all n increments satisfy c_k = 1, McDiarmid gives sum_k c_k^2 = n, and we obtain P(|chi(G(n,p)) - E[chi]| >= t) <= 2 * exp(-t^2 / (2n)). Setting t = lambda * sqrt(n) shows chi concentrates within O(sqrt(n)) of its mean. This is Shamir and Spencer's theorem, and it is remarkable for what it does NOT need: we have a sharp concentration result while having essentially no idea what E[chi] actually equals.
Janson's inequality: the lower tail of subgraph counts
Azuma is symmetric and generic; it does not know that 'no triangle at all' is special. For the canonical combinatorial question — what is the probability that G(n,p) contains NO copy of a fixed subgraph H? — the second-moment method proves the count is positive w.h.p. above the threshold, but only with polynomial control. Janson's inequality is the tool that turns this into a sharp exponential bound on the lower tail. Set up the standard frame: let {A_i}_(i in I) be a family of events, each A_i = 'a particular copy of H is present', and let X = sum_i 1_(A_i) be the number of copies. Write i ~ j when A_i and A_j are dependent (their edge sets overlap), and define mu = E[X] = sum_i P(A_i) and Delta = sum_(i ~ j) P(A_i and A_j), the total pairwise overlap.
Janson's inequality (events A_i increasing in the same independent coords):
mu = sum_i P(A_i) (mean number of copies)
Delta = sum_{i ~ j, i < j} P(A_i & A_j) (ordered-pair dependency sum)
P( X = 0 ) = P( no A_i occurs ) <= exp( - mu + Delta )
Generalized Janson (lower tail, 0 <= t <= mu):
P( X <= mu - t ) <= exp( - t^2 / ( 2 (mu + Delta) ) )
regime Delta = o(mu) (sparse / few overlaps) => P(X = 0) ~ e^{-mu}
regime Delta >> mu (heavy overlaps) => use Delta-corrected
bound e^{-mu^2/(2 Delta)}The picture is clean. If the events were independent we would have P(X = 0) = prod_i (1 - P(A_i)) <= exp(-sum_i P(A_i)) = e^(-mu), the exact Poisson approximation for rare events. Janson says the dependencies cost you only the correction factor e^(Delta): P(X = 0) <= e^(-mu + Delta). So whenever the overlap term Delta is small compared to mu, the answer is essentially the independent one, e^(-mu), now as a rigorous bound rather than a heuristic. This is exactly the lower tail the second moment could not reach: it converts 'X is usually positive' into 'X is zero with probability at most e^(-mu(1 - o(1)))', exponentially small.
Two honesty notes fix the scope. First, Janson needs the A_i to be increasing events on the same set of independent coordinates — present-edges in G(n,p) — so the proof can use the FKG/Harris positive correlation that increasing events help each other; it is not a tool for arbitrary dependent events. Second, the bound e^(-mu+Delta) is only useful when Delta = O(mu); once Delta dominates mu it is vacuous, and you switch to the generalized Janson bound e^(-mu^2/(2*Delta)), which stays meaningful in the heavily-overlapping regime. Knowing which regime you are in — comparing the subgraph-count variance term Delta against mu — is the whole skill.
Choosing your tool, and where this rung is heading
The two tools answer different shapes of question, and matching them is the practical lesson of this guide.
- Is X a global Lipschitz function of many independent coordinates (chromatic number, max independent set, longest increasing subsequence)? Reach for the exposure martingale and McDiarmid — you get two-sided concentration around the mean for free, even without knowing the mean.
- Do you specifically need the lower tail of a count of small substructures — the probability of seeing FEWER copies than expected, or none at all? Reach for Janson; it is sharp exactly where the symmetric Azuma bound is too weak, capturing the e^(-mu) decay of 'no copies'.
- Check the overlap budget before trusting Janson: compute mu and Delta. If Delta = o(mu) the answer is the clean Poisson e^(-mu); if Delta >> mu switch to the generalized form e^(-mu^2/(2 Delta)).
- If McDiarmid's sum_k c_k^2 is dominated by a few rare bad coordinates, upgrade to Talagrand's convex-distance inequality, which charges only for the increments that actually occur — the sharper successor to Azuma in this rung.
Place these two against the rest of the rung. The first moment and second moment methods locate where a property turns on; Azuma and Janson then prove it turns on sharply, with exponentially small failure probability. The Lovász Local Lemma from guide 3 attacks the complementary problem of avoiding many bad events at once under a sparse dependency condition, where Janson's increasing-event hypothesis would not apply. And the lower-tail constant e^(-mu) that Janson extracts is precisely the Poisson signature that the final guide of this rung explains from first principles: when many rare, weakly dependent events combine, the count is approximately Poisson, and Stein's method turns 'approximately' into a quantitative bound on the distance to the Poisson law. Concentration tells you a quantity barely moves; Stein's method tells you the exact shape of the small wiggle that remains.