, percolation theory
describes the behavior of connected
clusters in a random graph
. The applications of percolation theory to materials science
and other domains are discussed in the article percolation
A representative question (and the source
of the name) is as follows. Assume we have some porous
material and we pour some liquid on top. Will the liquid be able to make its way from hole to hole and reach the bottom? We model
the physical question
mathematically as a three-dimensional network of
points (or vertices
) the connections (or edges
) between each two neighbors may be open (allowing the liquid through) with probability p
, or closed with probability 1–p
, and we assume they are independent. We ask: for a given p
, what is the probability that an open path exists from the top to the bottom? Mostly we are interested in the behavior for large n
As is quite typical, it is actually easier to examine infinite networks than just large ones. In this case the corresponding question is: does an infinite open cluster exist? That is, is there a path of connected points of infinite length "through" the network. In this case we may use Kolmogorov's zero-one law to see that, for any given p, the probability that an infinite cluster exists is either zero or one. Since this probability is increasing (this is obvious intuitively, but mathematicians need a coupling argument to prove it), there must be a critical p (denoted by ) below which the probability is always 0 and above which the probability is always 1. In practice, this criticality is very easy to observe. Even for n as small as 100, the probability of an open path from the top to the bottom increases sharply from very close to zero to very close to one in a short span of values of p.
In some cases may be calculated explicitly. For example, for the square lattice in two dimensions, , a fact which was an open question for more than 20 years and was finally resolved by Harry Kesten in the early '80s. A limit case for lattices in many dimensions is given by the Bethe lattice, whose threshold is at for a coordination number . More often than not, cannot be calculated. For example, is not known in three dimensions. However, it turns out that calculating is not necessarily the most interesting thing to do. The universality principle states that the value of is connected to the local structure of the graph, while the behavior of clusters below, at and above are invariant with respect to the local structure, and therefore, in some sense are more natural quantities to consider.
Sometimes it is easier to open and close vertices rather than edges. This is called site percolation while the model described above is more properly called bond percolation.
The subcritical and supercritical phases