Phase Transitions, Critical Phenomena, and Cluster Formation
In site percolation, each site on a grid is independently occupied with probability p. Two occupied sites are considered connected if they are adjacent (horizontally or vertically). As p increases, small isolated clusters merge into larger ones. At the critical threshold pc ≈ 0.593 for the 2D square lattice, a giant cluster emerges that spans the entire system.
Applications: Forest fire spread, disease transmission, porous media flow, network connectivity.
In bond percolation, every site is present, but connections (bonds) between adjacent sites exist with probability p. Two sites are in the same cluster if they are connected by a path of open bonds. For the 2D square lattice, the critical threshold is exactly pc = 0.5, a remarkable result proven analytically.
Applications: Network reliability, electrical conductivity, polymer gelation.
The percolation threshold marks a dramatic phase transition. Below pc, only small finite clusters exist. Above pc, an infinite spanning cluster appears with probability 1 (in the infinite lattice limit). At exactly pc, the system exhibits scale-invariant fractal structure and power-law behavior.
Each connected component (cluster) is colored differently. The Union-Find algorithm efficiently identifies clusters in O(N α(N)) time, where α is the inverse Ackermann function (effectively constant). Near pc, you'll see a beautiful fractal distribution of cluster sizes - small clusters everywhere, with occasional large sprawling clusters.