The Oscillating Maximum

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.

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.