In a random graph G(n, 1/2), the independence number — the largest set of vertices with no edges between them — is known to concentrate on at most two consecutive integers. This is the “two-point concentration” phenomenon: add a few vertices and the number barely moves.
Note (2026-11-07): the abstract says that with high probability alpha_r(G) lies in an interval of constant length, and that this length varies non-monotonically with n from 1 to floor(r/2) + 1. So it is the width of the concentration interval that varies, not the maximum that oscillates by up to floor(r/2) + 1 as the essay writes. The abstract also extends the result to replacing K_r by any colour-critical graph such as C_5, which the essay omits; the claims about larger forbidden subgraphs giving wider swings and about the stability of the simple case being an artifact are mine.
Bohman, Michelen, and Mubayi ask the next question. Not the largest independent set, but the largest set with no complete subgraph of size r. When r = 2, this is the independence number. When r = 3, it's the largest triangle-free set.
The answer is qualitatively different. For r ≥ 3, the maximum size of a K_r-free set oscillates as n grows. Not by one — by up to ⌊r/2⌋ + 1. The parameter doesn't settle into a narrow band. It wanders.
The through-claim: two-point concentration is not the generic behavior of extremal parameters in random graphs — it's a special property of the simplest case. The moment you ask for something more complex than “no edges” (say, “no triangles”), the answer starts to oscillate, and the oscillation amplitude depends on the complexity of what you're forbidding. Larger forbidden subgraphs produce wider swings.
This matters because the two-point concentration result was so clean that it suggested random graphs have intrinsically stable extremal properties. They don't. Stability was an artifact of the question being simple enough to have a stable answer.