Percolation theory

In mathematics, 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.

Introduction

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 $n\; imes\; n\; imes\; n$ 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 $p\_c$) 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".

states that the value of $p\_c$ is connected to the local structure of the graph, while the behavior of clusters below, at and above $p\_c$ 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

For

When $p>p\_c$ just the opposite occurs, with closed islands in an open sea. These facts were proved by Mikhail Menshikov in 1986 and independently by Michael Aizenman and David Barsky in 1987.

The critical phase

Arguments from quantum field theory and quantum gravitation make a sequence of impressive conjectures about the critical phase, most of which are unproved Fact|date=April 2008:
* There are no infinite clusters (open or closed)
* The probability that there is an open path from some fixed point (say zero) to a distance of "r" decreases "polynomially", i.e. is on the order of $r^alpha$ for some α
** α does not depend on the particular lattice chosen, or on other local parameters. It depends only on the dimension (this is an instance of the universality principle).
** $alpha\_d$ decreases from "d" = 2 until "d" = 6 and then stays fixed.
** $alpha\_6=-1$
** $alpha\_2=-5/48$.
* The stochastic behavior of large clusters in two dimensions is conformally invariant.

In dimension ≥ 19, these facts (except universality) are proved. In dimension 2, the first fact ("no percolation in the critical phase") is proved for all lattices, but the rest have only been proved for site percolation on the honeycomb or hexagonal lattice, and of course, universality is not proved. In dimensions 3 to 18, even the first conjecture is still open.

The different models

*The first model studied was Bernoulli percolation. In this model all bonds are independent. This model is called bond percolation by physicists.
*A generalization next was introduced as the Fortuin–Kasteleyn random cluster model, which has many connections with the Ising model and other Potts models.
*Bernoulli (bond) percolation on complete graphs is an example of a random graph. The critical probability is p=1/N.
*Directed percolation, which has connections with the contact process.
*First passage percolation.
*Invasion percolation.

ee also

* Percolation threshold

References

* [http://www.statslab.cam.ac.uk/~grg/papers/perc/perc.html Percolation] , by G.R. Grimmett
*Percolation for mathematicians by H. Kesten
* [http://www.cambridge.org/catalogue/catalogue.asp?isbn=0521872324 Percolation] , by B. Bollobas et O. Riordan
* [http://ibiblio.org/e-notes/Perc/contents.htm Interactive Percolation]
* Introduction to Percolation Theory by Junqiao Wu

External links

*