Percolation

Imagine a square grid. Each cell is independently open with some probability p, or blocked with probability 1 − p. Water (or fire, or disease) flows only through open cells. The question is ancient and deceptively simple: will a path of open cells connect the top of the grid to the bottom?

For small p the grid is mostly blocked; a spanning path never forms. For large p it is mostly open; a path almost surely exists. In between there is a critical probability p_c where the behaviour flips with startling sharpness — the mathematical signature of a phase transition.

Percolation was introduced by Simon Broadbent and John Hammersley in 1957 to model the random flow of gas through carbon used in gas masks. It has since become one of the central models of statistical mechanics, probability theory, and the study of critical phenomena — the same mathematical skeleton that describes magnets losing their magnetism at the Curie temperature, or the spread of an epidemic reaching a tipping point.

Drag the probability slider to set how densely the grid is filled. Click New grid to generate a fresh random layout at that density. Open cells are shown in blue; the spanning cluster — the largest connected group that links top to bottom — is highlighted in orange. A path exists message confirms the connection.

<div class="controls">
  <label for="prob">Probability p = <span id="pval">0.55</span></label>
  <input type="range" id="prob" min="0" max="100" value="55" step="1">
  <button id="newgrid" type="button">New grid</button>
</div>
<canvas id="canvas" width="300" height="300"></canvas>
<div id="status" class="status">—</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .6rem; font-size: .9rem; }
label { font-weight: 600; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 120px; max-width: 200px; cursor: pointer; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; white-space: nowrap; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 6px; max-width: 100%; }
.status { margin-top: .55rem; font-weight: 600; font-size: .95rem; min-height: 1.4em; }
.status.yes { color: #0a7d33; }
.status.no  { color: #c92f3c; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Percolation demo: site percolation on an N×N grid.
// Each cell is independently open with probability p.
// We BFS from all open cells in the top row and check whether
// any open cell in the bottom row is reachable — a "spanning cluster".
// The spanning cluster (if any) is highlighted in orange.
// Critical threshold for site percolation on the square lattice ≈ 0.5927.

const N = 30; // grid side
const CELL = 10; // px per cell
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
canvas.width  = N * CELL;
canvas.height = N * CELL;

const probSlider = document.getElementById('prob');
const pvalSpan   = document.getElementById('pval');
const statusDiv  = document.getElementById('status');

// Color palette
const C_BLOCKED  = '#e8eef3'; // light grey
const C_OPEN     = '#a8c4e0'; // soft blue
const C_SPANNING = '#f4a261'; // orange (spanning cluster)
const C_BORDER   = '#cdd9e3';

let grid = []; // grid[r][c] = true if open

function generate(p) {
  grid = [];
  for (let r = 0; r < N; r++) {
    grid[r] = [];
    for (let c = 0; c < N; c++) {
      grid[r][c] = Math.random() < p;
    }
  }
}

// BFS from top row open cells. Returns:
// { reached: Set of 'r,c' strings in spanning cluster, spans: boolean }
function percolate() {
  const visited = new Array(N).fill(null).map(() => new Uint8Array(N));
  const queue = [];
  // Seed from top row
  for (let c = 0; c < N; c++) {
    if (grid[0][c] && !visited[0][c]) {
      visited[0][c] = 1;
      queue.push([0, c]);
    }
  }
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] && !visited[nr][nc]) {
        visited[nr][nc] = 1;
        queue.push([nr, nc]);
      }
    }
  }
  // Check if bottom row reached
  let spans = false;
  for (let c = 0; c < N; c++) {
    if (visited[N-1][c]) { spans = true; break; }
  }
  return { visited, spans };
}

function draw() {
  const { visited, spans } = percolate();
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  for (let r = 0; r < N; r++) {
    for (let c = 0; c < N; c++) {
      let color;
      if (!grid[r][c]) {
        color = C_BLOCKED;
      } else if (visited[r][c]) {
        color = C_SPANNING; // part of spanning BFS tree
      } else {
        color = C_OPEN;
      }
      ctx.fillStyle = color;
      ctx.fillRect(c * CELL, r * CELL, CELL, CELL);
      ctx.strokeStyle = C_BORDER;
      ctx.strokeRect(c * CELL + 0.5, r * CELL + 0.5, CELL - 1, CELL - 1);
    }
  }
  if (spans) {
    statusDiv.textContent = '✓ Spanning path exists — percolation!';
    statusDiv.className = 'status yes';
  } else {
    statusDiv.textContent = '✗ No spanning path — grid is blocked.';
    statusDiv.className = 'status no';
  }
}

function refresh() {
  const p = probSlider.value / 100;
  pvalSpan.textContent = p.toFixed(2);
  generate(p);
  draw();
  // Log for node verification
  const open = grid.flat().filter(Boolean).length;
  console.log(fmt('p=%p%  open=%open%/%v%', { p: p.toFixed(2), open: open, v: N*N }));
}

probSlider.addEventListener('input', () => {
  pvalSpan.textContent = (probSlider.value / 100).toFixed(2);
});
probSlider.addEventListener('change', refresh);
document.getElementById('newgrid').addEventListener('click', refresh);
refresh();

<div class="controls">
  <label for="prob">Probability p = <span id="pval">0.55</span></label>
  <input type="range" id="prob" min="0" max="100" value="55" step="1">
  <button id="newgrid" type="button">New grid</button>
</div>
<canvas id="canvas" width="300" height="300"></canvas>
<div id="status" class="status">—</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .6rem; font-size: .9rem; }
label { font-weight: 600; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 120px; max-width: 200px; cursor: pointer; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; white-space: nowrap; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 6px; max-width: 100%; }
.status { margin-top: .55rem; font-weight: 600; font-size: .95rem; min-height: 1.4em; }
.status.yes { color: #0a7d33; }
.status.no  { color: #c92f3c; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Percolation demo: site percolation on an N×N grid.
// Each cell is independently open with probability p.
// We BFS from all open cells in the top row and check whether
// any open cell in the bottom row is reachable — a "spanning cluster".
// The spanning cluster (if any) is highlighted in orange.
// Critical threshold for site percolation on the square lattice ≈ 0.5927.

const N = 30; // grid side
const CELL = 10; // px per cell
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
canvas.width  = N * CELL;
canvas.height = N * CELL;

const probSlider = document.getElementById('prob');
const pvalSpan   = document.getElementById('pval');
const statusDiv  = document.getElementById('status');

// Color palette
const C_BLOCKED  = '#e8eef3'; // light grey
const C_OPEN     = '#a8c4e0'; // soft blue
const C_SPANNING = '#f4a261'; // orange (spanning cluster)
const C_BORDER   = '#cdd9e3';

let grid = []; // grid[r][c] = true if open

function generate(p) {
  grid = [];
  for (let r = 0; r < N; r++) {
    grid[r] = [];
    for (let c = 0; c < N; c++) {
      grid[r][c] = Math.random() < p;
    }
  }
}

// BFS from top row open cells. Returns:
// { reached: Set of 'r,c' strings in spanning cluster, spans: boolean }
function percolate() {
  const visited = new Array(N).fill(null).map(() => new Uint8Array(N));
  const queue = [];
  // Seed from top row
  for (let c = 0; c < N; c++) {
    if (grid[0][c] && !visited[0][c]) {
      visited[0][c] = 1;
      queue.push([0, c]);
    }
  }
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < N && nc >= 0 && nc < N && grid[nr][nc] && !visited[nr][nc]) {
        visited[nr][nc] = 1;
        queue.push([nr, nc]);
      }
    }
  }
  // Check if bottom row reached
  let spans = false;
  for (let c = 0; c < N; c++) {
    if (visited[N-1][c]) { spans = true; break; }
  }
  return { visited, spans };
}

function draw() {
  const { visited, spans } = percolate();
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  for (let r = 0; r < N; r++) {
    for (let c = 0; c < N; c++) {
      let color;
      if (!grid[r][c]) {
        color = C_BLOCKED;
      } else if (visited[r][c]) {
        color = C_SPANNING; // part of spanning BFS tree
      } else {
        color = C_OPEN;
      }
      ctx.fillStyle = color;
      ctx.fillRect(c * CELL, r * CELL, CELL, CELL);
      ctx.strokeStyle = C_BORDER;
      ctx.strokeRect(c * CELL + 0.5, r * CELL + 0.5, CELL - 1, CELL - 1);
    }
  }
  if (spans) {
    statusDiv.textContent = '✓ Spanning path exists — percolation!';
    statusDiv.className = 'status yes';
  } else {
    statusDiv.textContent = '✗ No spanning path — grid is blocked.';
    statusDiv.className = 'status no';
  }
}

function refresh() {
  const p = probSlider.value / 100;
  pvalSpan.textContent = p.toFixed(2);
  generate(p);
  draw();
  // Log for node verification
  const open = grid.flat().filter(Boolean).length;
  console.log(fmt('p=%p%  open=%open%/%v%', { p: p.toFixed(2), open: open, v: N*N }));
}

probSlider.addEventListener('input', () => {
  pvalSpan.textContent = (probSlider.value / 100).toFixed(2);
});
probSlider.addEventListener('change', refresh);
document.getElementById('newgrid').addEventListener('click', refresh);
refresh();

Notice how quickly the picture changes around p ≈ 0.59. Below that value the grid stays fragmented; above it an orange highway almost always appears. The transition is not gradual — it is a sharp threshold, the hallmark of a phase transition. In an infinite grid the switch from "no path" to "path certain" would be instantaneous at exactly p_c = 0.592746…

This is closely related to the ideas behind small-world networks and the sudden spread of an epidemic past its reproduction number.

Percolation theory sits in a rare position: some of its deepest questions have been solved, while others remain open, and the proofs that exist belong to the hardest mathematics of the 20th and 21st centuries.

What is known:

• The critical probability exists and is sharp: for any lattice there is a unique p_c such that below it no infinite cluster exists and above it exactly one does. This is proven rigorously.
• On the triangular lattice, p_c = 1/2 exactly. This was proved by Harry Kesten in 1980, confirming a conjecture that had stood for decades.
• At criticality the system exhibits conformal invariance: crossing probabilities in the plane depend only on the shape of the domain, not on the microscopic lattice. This was proved by Stanislav Smirnov in 2001 for site percolation on the triangular lattice, earning him the Fields Medal in 2010.
• The scaling limit of critical percolation interfaces is described by Schramm–Loewner evolution ($SLE_{6}$), a random fractal curve — a remarkable connection between probability, complex analysis, and conformal field theory.

What is open:

• The exact critical probability for bond percolation on the square lattice is believed to be p_c = 1/2 (and this follows from symmetry arguments), but the full conformal invariance proof for the square lattice remains open — Smirnov's proof used special features of the triangular lattice.
• Many three-dimensional universality class exponents are known numerically but not proved rigorously; the existence of the scaling limit in 3D is open.

Percolation is also deeply connected to graph theory: finding a spanning cluster is equivalent to a connectivity question, answerable in linear time by BFS or Union-Find — the computational problem is easy even if the mathematical analysis is hard.

The percolation phase transition is not just a mathematical curiosity — it is the backbone of several practical and scientific fields:

• Epidemiology: spreading an infection through a contact network is percolation. The basic reproduction number $R_{0}$ = 1 is the critical threshold; above it an epidemic percolates through the population. Vaccination reduces the effective density of susceptible contacts below p_c, halting spread.
• Oil and gas recovery: petroleum engineers model porous rock as a percolation network to predict whether oil can be extracted. The oil percolates through interconnected pores only above the critical porosity.
• Forest fires and wildfires: a forest is a grid where each tree is "open" (flammable) with some density. Above the critical density a fire started at one edge can burn all the way to the other; below it, flames die out locally. Fire-break strategies are literally sub-threshold percolation design.
• Network resilience: the internet, power grids, and social networks all have a percolation threshold. Randomly removing nodes (failures) below p_c leaves the network connected; above it the network shatters into isolated islands. This drives the design of fault-tolerant systems.
• Materials science: composite materials (e.g., conducting particles in an insulating matrix) become conducting when the particle density crosses p_c — the percolation threshold determines the transition from insulator to conductor.

The universality of the model — its behaviour near p_c depends only on the dimension and lattice symmetry, not on microscopic details — makes it a powerful conceptual tool across physics, biology, and engineering.

Percolation distils one of nature's most universal patterns into a single number: the critical probability p_c. Below it, everything is isolated; above it, a giant connected cluster suddenly spans the whole system. The transition is not smooth — it is a sharp threshold, as sudden as ice becoming water.

That sharpness is both the beauty and the lesson. Whether you are designing a vaccine campaign, building a fault-tolerant network, or proving deep theorems about random fractals, the question is always the same: are you above or below the threshold? The mathematics of percolation, from Kesten's 1980 proof to Smirnov's Fields Medal, shows just how hard it can be to pin that number down — and just how much hangs on the answer.

For more on how sharp thresholds appear in random graphs and how connectivity spreads in networks, see the related articles on small-world phenomena and probabilistic reasoning.