Sketch · 2026-08-28
Site percolation, across the threshold.
A 200 by 200 lattice, each site independently occupied with probability p. Below a critical value the occupied sites fall into many small islands. Above it a single cluster suddenly reaches from one side of the board to the other. The crossing is sharp and it happens at a very specific number.
The threshold
For site percolation on the two-dimensional square lattice with
four-neighbour connectivity, the critical probability is
p_c ≈ 0.59274605. No closed
form is known. In the infinite-lattice limit the probability that
the origin sits in an infinite cluster is exactly zero below p_c
and rises smoothly above it, and the mean cluster size diverges as
p climbs to p_c from below. On a finite 200 by 200 grid the
transition is a little softer, but the jump is still striking
somewhere between 0.58 and 0.60.
How the spanning cluster is found
One pass with a disjoint-set forest. Walk the grid row by row. For each occupied cell, union it with the occupied cell above and the occupied cell to the left; two edges per site are enough because the other two are covered when their owner cells are visited. Path compression and union by rank keep each operation effectively constant. A second pass reads out cluster sizes and flags any root whose members touch both the top row and the bottom row. That root is the spanning cluster; on this page it turns amber the moment it appears.
Sources
- Broadbent, S. R. and Hammersley, J. M. (1957). Percolation processes: I. Crystals and mazes. Proc. Cambridge Phil. Soc., 53(3), 629–641. The paper that named the problem, motivated by gas flow through a random porous filter.
- Newman, M. E. J. and Ziff, R. M. (2001). Fast Monte Carlo algorithm for site or bond percolation. Physical Review E, 64, 016706. The disjoint-set trick used here, written up with the incremental version that sweeps p in one run.
- Jacobsen, J. L. (2015). Critical points of Potts and O(N) models from eigenvalue identities in periodic Temperley-Lieb algebras. J. Phys. A, 48, 454003. The current best numerical value of p_c for site percolation on the square lattice, 0.59274605079210(2).