concentration of the chromatic number
Concentration of the chromatic number is the surprising fact that the chromatic number chi(G) of a random graph, despite being a global and combinatorially delicate quantity, is extraordinarily tightly clustered around its (typically unknown) mean — sometimes concentrated on just a handful of values. The chromatic number is the minimum number of colours needed to colour the vertices so that adjacent vertices differ; it depends on the entire graph in an intricate way. One might expect it to fluctuate substantially across random graphs, yet the opposite is true, and this is one of the cleanest illustrations of martingale concentration in combinatorics.
The first result, due to Shamir and Spencer, uses the vertex-exposure martingale: since adding a vertex changes chi by at most 1, the bounded-difference Azuma inequality gives concentration on a sqrt(n) scale, P(|chi - E[chi]| > t sqrt(n)) <= 2 e^(-t^2/2). The astonishing refinement came from Bollobas and others: for the dense random graph G(n, 1/2) the chromatic number is concentrated, with probability tending to 1, on an interval of width O(sqrt(n)/log n) and is in fact asymptotically chi(G) ~ n / (2 log_2 n). Even more striking is the sparse regime: Shamir and Spencer proved that for G(n, p) with p = n^(-alpha) and alpha > 1/2, the chromatic number is concentrated on just TWO consecutive integers with probability tending to 1 — a phenomenon called two-point concentration. The proofs combine the exposure martingale (to show whatever value chi takes, it is sharply concentrated) with a separate counting argument (to show the few values it can take are clustered), since Azuma alone never tells you where the mean sits.
Why this matters and what it warns against: it is a landmark demonstration that bounded-difference martingale concentration can be far sharper than a naive variance estimate suggests, and two-point concentration is a remarkable rigidity. But the honest subtlety is exactly the gap between concentration and location. The martingale argument proves chi is concentrated near its mean E[chi] without ever computing E[chi]; pinning down the actual interval (the two points, or the n/(2 log n) asymptotic) requires entirely separate combinatorial work bounding the number of colours actually needed. There is also a known limit: for very sparse graphs (p around 1/n) two-point concentration can fail, and determining the exact width of concentration across all densities remains partly open. Concentration does not mean we can compute the chromatic number — only that it barely varies.
Two-point concentration: for G(n, n^(-3/4)) (so alpha = 3/4 > 1/2), Shamir-Spencer's theorem says there is an integer u = u(n) such that with probability tending to 1, chi(G) is either u or u+1 — out of all the integers it conceivably could be, it lands on essentially one. The vertex-exposure martingale supplies the sharp tail; a separate first-moment count of available colourings localises which two values.
Sparse random graphs: chi(G) is concentrated on just two consecutive integers — extreme rigidity.
Concentration is not computation: the martingale shows chi barely varies around E[chi] but never gives E[chi]; locating the actual values needs separate counting, and two-point concentration can fail for very sparse graphs (p ~ 1/n).