Percolation theory

Percolation theory asks how many local connections must be available before a large connected structure appears. Start with a graph, randomly retain some edges or vertices, and study the resulting percolation clusters. In independent bond percolation, every edge is open with probability $p$, independently of the others. In independent site percolation, the random decisions concern vertices instead. A percolation cluster is a connected component of a graph formed by the available connections; an open path joins two vertices exactly when they belong to the same percolation cluster.

The attraction is that a local rule can produce a global change. One open edge says little about travel across a large graph. Many alternative graph paths can nevertheless make distant connections likely. The model separates the geometry of possible connections from the probability distribution of which connections are usable. This was the central perspective of Broadbent and Hammersley's 1957 paper, which discussed porous solids and disease transmission as interpretations of the same mathematical structure: ^[ref]. Independent bond percolation supplies a simplified model of those systems; the physical interpretation still requires justification of its independence assumptions.

For a completely calculable example, consider the four edges around a square and ask whether opposite corners $A$ and $C$ are connected. There are two graph paths, each using two edges. Each open path has probability $p^2$. Their events are independent events because the paths share no edges, even though they share endpoints. The inclusion-exclusion principle therefore givesAt $p=1/2$, the connection probability is $7/16$, larger than the $1/4$ for either chosen graph path. Counting all sixteen equally likely edge configurations gives the same answer: two configurations with exactly two open edges, four with three, and one with four connect $A$ to $C$. Connectivity benefits from alternative routes; adding their probabilities without subtracting their overlap would count the all-open configuration twice.

This finite calculation is already useful for studying redundant connections. The deeper question is what happens as the graph becomes arbitrarily large: does connectivity remain confined to finite percolation clusters, or can an infinite percolation cluster appear? The percolation probability and percolation critical probability make that question precise. A finite picture can illustrate the geometry, but cannot establish the existence of an infinite percolation cluster.

Percolation theory is a mathematical concept originally developed in the context of physics and materials science to study the behavior of connected clusters in a random medium. It explores how the properties of such clusters change as the density of the medium is varied. The theory has applications in various fields, including physics, chemistry, computer science, biology, and even social sciences.