The Threshold That Changes Everything

Drag the p slider slowly through 0.59. Below it, the grid breaks into isolated islands. At 0.5927, a cluster spanning top to bottom first appears. The spanning cluster toggles on: a path now threads the entire medium. The sketch displays that transition from none to one.

The question that launched percolation theory was about coffee. Or rather, Simon Broadbent (a statistician at the UK Coal Board) described the problem in terms of fluid finding a path through a porous stone, but the underlying question is the same one that faces anyone pouring water through grounds and wondering why it sometimes channels and sometimes doesn't. In 1957 Broadbent presented the problem to John Hammersley at a symposium and they published a foundational paper together in the Mathematical Proceedings of the Cambridge Philosophical Society. The difference between their model and classical diffusion was precise and consequential: in diffusion, the randomness is in the fluid; in percolation, the randomness is in the medium. Each site in the lattice is occupied with probability p, independently of every other site. The fluid goes where it can.

Broadbent and Hammersley proved that a critical threshold p_c changes the system's behavior qualitatively, a result physicists and mathematicians spent the next fifty years making rigorous. Below it, all clusters remain finite: any path through the medium eventually hits a blocked site and terminates. Above it, a single cluster of infinite extent (or, on a finite lattice, one that spans from edge to edge) first appears. For site percolation on a square lattice, that threshold is approximately 0.592746. The number itself is not derivable from simple combinatorics; it has been computed to extraordinary precision via Monte Carlo simulation and, more recently, graph polynomial methods, which pin it to 0.592746050792 with uncertainty only in the last two digits. The threshold for bond percolation on the same lattice is exactly 1/2, which Kesten proved in 1980, one of the few cases where the exact value is known analytically.

Exactly at p_c, the largest cluster is a branching fractal with the same qualitative structure at every scale, neither a dense mass nor sparse dust. The fractal dimension of the critical cluster in two dimensions is approximately 91/48 ≈ 1.896, a value that holds regardless of whether the underlying lattice is square, triangular, or hexagonal. This universality (that the exponents depend only on spatial dimension, not on lattice geometry) connected percolation to the broader apparatus of statistical mechanics. The Ising model at its critical temperature, percolation at p_c, and several other systems in two dimensions exhibit critical behavior described through what physicists call universality classes.

The artifact implements site percolation with a union-find algorithm, which is the standard approach for labeling clusters in a single pass without BFS or DFS. Each occupied site that has no occupied neighbors to its left or above becomes a new singleton component. Each site that has occupied neighbors merges their components. The union step uses union by rank with path compression, keeping nearly every find operation at amortized O(α(N)), essentially constant:

function find(x){
  while(parent[x] !== x) x = parent[x] = parent[parent[x]];
  return x;
}
function union(a, b){
  a = find(a); b = find(b);
  if(a === b) return;
  if(rank[a] < rank[b]){ const t = a; a = b; b = t; }
  parent[b] = a;
  if(rank[a] === rank[b]) rank[a]++;
}

Path compression (the parent[x] = parent[parent[x]] line) halves the path length on each traversal without a separate flattening pass. After the scan completes, every label is canonicalized by calling find one more time, and cluster sizes are tallied from the canonical labels. The spanning check then looks for any label that appears in both the top row and the bottom row: if one exists, a path connects the two edges, and the medium percolates.

Broadbent's motivating image was a crystal growing inside a porous rock, blocked by the rock's structure from spreading uniformly, hence the name they gave the model in their paper: "percolation processes." The coffee analogy is retroactive and slightly too tidy. The model applies to any situation where connectivity emerges from local independent decisions. Forest fire spread, epidemic contagion, oil reservoir simulation, polymer gelation, and electrical conductance in composites all exhibit the same qualitative transition: below a threshold, the medium is an insulator or a firebreak; above it, it conducts or burns through. The identity of the threshold differs across models and geometries. The existence of a threshold and the universal character of behavior at criticality are general.

The "Animate p" button in the artifact sweeps the probability slowly from 0 to 1 and back. At p = 0.20 the grid is mostly empty, clusters are tiny, and nothing spans. At p = 0.45 recognizable islands appear, but they stay isolated. The first spanning cluster appears near 0.59, flickering in and out for a few probability steps, then persisting reliably above 0.62. That flicker reflects the behavior of a finite lattice near a continuous phase transition, where fluctuations are large and the system sits at the edge of two stable phases. An infinite lattice would show a sharp step function. A 150×150 grid shows the step rounded by finite-size effects, spread across a probability interval proportional to N^-3/4. The larger the grid, the sharper the transition. The artifact lets you push the grid up to 400×400 to see this directly.

The full interactive version is at the artifact page. The gallery sketch at gallery/percolation runs the same simulation in a stripped frame. Start with Animate p, watch the transition, then push p back to 0.5927 by hand and use Show Spanning to highlight the path — if one exists. At exactly the threshold, it often doesn't.