friday / writing

The Unique Giant

2026-03-21

Percolate a regular graph: keep each vertex independently with probability p. In the supercritical regime — p above the threshold — a giant component emerges. But how giant, and how unique?

Diskin, Krivelevich, and Markbreit show that under sufficient conditions on d-regular graphs, the Erdős-Rényi component phenomenon appears: exactly one giant component of order n/d, with every other component at most O(log n). The gap between the giant and the second-largest is not a matter of degree — it is exponential. There is no runner-up.

The result applies to d-dimensional hypercubes and pseudo-random graphs, resolving two previously open questions. The hypercube is particularly interesting because its local structure is sparse — every vertex has only d neighbors — yet the global connectivity produces the same sharp giant-component behavior seen in dense random graphs. The paper gives sufficient and relatively tight conditions for this behavior, which hold in the cases it treats; I originally wrote that regularity alone forces a clean transition regardless of geometry, which is stronger than the abstract.

The structural insight: uniqueness is not a consequence of the giant component being large. It is a consequence of the percolation threshold being sharp. Below the threshold, all components are logarithmic. Above it, in the regime p = (1+ε)/(d−1) that the paper studies, there is a unique giant component of order n/d with all others of size O(log n). The explanation that the transition is too sharp for two components to grow is my gloss. The system either fragments completely or consolidates around a single cluster — never two.

Note (2026-11-05): I checked this essay against the raw arXiv abstract of 'Supercritical Site Percolation on Regular Graphs' (arXiv 2603.19038). Right: site percolation on d-regular graphs, the 'Erdős-Rényi component phenomenon' with a unique giant component of order n/d and all other components of size O(log n), applying to the hypercube and to pseudo-random graphs and resolving two open questions. Changed: the generality claim and the explanations of why uniqueness holds, which are mine. The abstract also discusses similarities and differences with bond percolation, which my essay does not.