## Percolation: Slipping through the CracksThe existence of a critical probability makes percolation a mathematically interesting and rich subject. ...David Austin
## IntroductionMy backyard has an area where the soil is mainly clay and another where it's mainly sand. The day after a hard rain, the sandy region is usually dry while the clay region is still damp. The process by which water moves through a medium, like sand or clay, is called Geoffrey Grimmett begins his book
This is known as the square lattice, and we will denote it by
If we imagine that the size of the channels is much smaller than the size of the rock, it is reasonable to assume that the lattice is infinite in extent. To rephrase Grimmett's question, we may ask, "What is the probability that there is a path of open edges from the origin that travels infinitely far?
We can easily make two statements. When What happens for intermediate values of p but not below. A result due to Harris and Kesten, which we'll outline later, states that the critical probability for the square lattice is _{c}p = 1/2._{c}The existence of a critical probability makes percolation a mathematically interesting and rich subject. On either side of the critical probability, the system behaves in fundamentally different ways (as water drains easily through sandy soil but not through clay). As such, it serves as a model for more complex systems that experience a phase transition when some parameter, such as temperature, passes through a critical value. Percolation provides a model that is simple enough to be mathematically accessible while still displaying many of the features of more complex systems. ## A simple exampleLet's begin with a simple example that illustrates some general principles. We will study percolation on the infinite binary tree, a portion of which is shown below.
If P be the probability that there is an open path from _{n}v to a vertex _{0}n levels below. Notice that we have P_{0} = 1. Shown in red below is a path from v to a vertex three levels below._{0}
This path moves through another vertex v to a vertex _{0}n levels below passes through v is _{1}pP_{n}_{-1}, the probability p that the edge from v to _{0}v is open times the probability _{1}P_{n}_{-1} that a path from v to a vertex _{1}n - 1 levels below it is open. Therefore, the probability that there is no open path from v to a vertex _{0}n levels below passing through v is 1 - _{1}pP_{n}_{-1}.Since any path from n levels below must pass through one of the children of v, we find that the probability that there is not an open path from _{0}v to a vertex _{0}n levels below is
and therefore
If we define the function x) = 1 - (1 - px)^{2}, we have P = _{n}f(_{p}P_{n}_{-1}). The graph of f is shown below in two different cases, depending on the derivative _{p}f._{p}'(0) = 2p
In the first case,
and if From the graph, we see that if x. Since _{0} < f_{p}(x) < xP = 1, we have_{0}
It then follows that
if
Here we see that the critical probability, p, _{c}θ(p) > 0 and we have percolation. Below the critical probability, θ(p) = 0 and there is no percolation.This example is unusual in that it is difficult to compute the critical probability and ## Percolation on the square latticePercolation theory was introduced to mathematicians by Broadbent and Hammersley in 1957. For two decades, work in this new field concentrated mainly on finding critical probabilities. For instance, Broadbent and Hammersley showed that the critical probability for the square lattice
On the basis of Monte Carlo simulations, Hammersley later suggested that this probability should be 1/2. Indeed, through work of Harris and later Kesten, it was eventually proven that p.Here is one configuration of open edges that results when
Given a configuration of open edges and a vertex v by open edges.Below we show a configuration when
Remember that p.
Based on these examples, two things can be observed. First, if we look at a fixed value of If E holds when the edges are open with probability p. By S, we will denote the event that there is an open path from a vertex _{x,n}x to another vertex whose distance from x, measured in the lattice, is n. (We measure distances in the lattice as the number of edges in the shortest possible path between the two vertices.) Though proven in considerably more generality, Menshikov's theorem roughly says that
This means that the probability of having an open path decreases exponentially as the distance traveled by the path increases. ## The Harris-Kesten TheoremFor our second observation, imagine increasing p, but around p = 0.45, its size begins to grow significantly. This leads us to suspect that the critical probability p, the probability that marks the transition from _{c}θ(p) = 0 to θ(p) > 0 occurs around 1/2.In fact, one of the first significant results in percolation theory is the Harris-Kesten Theorem
In what follows, we will outline a proof of this theorem, which divides naturally into two parts. The first half, originally proven by Harris in 1960, states that p ≤ 1/2. The result that _{c}p = 1/2 naturally follows._{c}We'll begin outlining an argument for Harris' theorem by considering the
Notice that if we are given an edge in the lattice, there is exactly one edge crossing it in the dual. Also, the dual lattice is a copy of the square lattice translated so that the vertices are in the centers of the squares. For this reason, we say the square lattice is Suppose we are given a configuration of open edges in the square lattice. We will consider an edge in the dual lattice to be open exactly when the edge it crosses in the square lattice is closed. Shown below in red is a configuration for the square lattice and, in blue, the corresponding configuration in the dual lattice.
In this way, requiring that the edges in the square lattice are open with probability Now consider p < p, then this cluster is almost surely finite. As the figure below shows, this means that there is almost surely an open cycle in the dual lattice containing the origin in its interior (shown in green)._{c}
To summarize, we see that To do this, we will find the probability that there is an open cycle in the dual lattice contained in an annulus and composed of four separate open paths as shown below.
Breaking the problem down even further, we will look at one of the four sides of this rectangular annulus, a rectangle whose dimensions are Here is a fundamental observation: Suppose we consider
Recall that H(R)) denotes the probability that there is a horizontal open path across R when edges are open with probability p. In the same way, P_{1-p}(V(R')) is the probability that there is an open vertical path across R'.Since there is either a horizontal open path across
If we consider the case that
Notice that this is independent of Now that we understand the probability of having an open path across a square, we would like to use this understanding to study more general rectangles. Remember that we would eventually like to understand rectangles of dimension Consider the figure to the left, in which we have two squares of sides
Now let 3n by 2n rectangle. We break this into smaller pieces by considering the rectangle to consist of two squares of dimension 2n by 2n overlapping in an n by 2n rectangle. Applying our previous result, we have
Continuing in this way, we may continue to understand wider rectangles by breaking them into smaller rectangles that overlap in a square. For instance, the figure to the right illustrates an argument showing that the probability there is an open path across a With some additional work, we see that the probability that there is an open horizontal path across a Remember that we are interested in finding an open cycle around the annulus shown below. Decomposing the annulus into four rectangles whose dimensions are
We now imagine ringing the origin with a set of concentric annuli as shown.
We now know that the probability there is θ(1/2) = 0 and p ≥ 1/2. This completes the proof of Harris' Theorem._{c}To complete the proof of the Harris-Kesten theorem, we also need to prove Kesten's theorem, which says that p > 1/2 and arriving at a contradiction. The argument sketched here is not Kesten's original proof._{c}If we assume that p = 1/2 is below the critical probability. Recalling Menshikov's theorem, which we stated earlier, we then have
where x to a vertex whose distance from x is n.Consider an By choosing ## Some other resultsThe early days of mathematical work in percolation focused on finding critical probabilities for various combinatorial graphs. After a considerable amount of effort, relatively little is known. Here is a summary. The scenario we have presented, where edges are declared to be open or closed, is usually known as Shown below, for instance, are the vertices in the triangular lattice
Aside from these results and those for regular graphs, which are similar to the binary tree we looked at earlier, very little is known about the exact values of critical probabilities for other graphs. ## Conformal InvarianceAs mentioned before, early work in percolation theory concentrated on finding critical probabilities. Recently, however, theoretical physics has raised interesting questions in some different directions. It should be clear that the critical probability depends on geometric properties of the graph. However, there is evidence that certain percolation probabilities remain unchanged under "conformal maps." A conformal map of the plane is a function from one region in the plane to another that may distort distances but must preserve angles. Examples are provided by complex analytic functions such as To begin, we will consider a region P, _{2}P, and _{3}P. These points divide the boundary of _{4}D into four arcs A, _{1}A, _{2}A, and _{3}A. We will call this data a _{4}4-marked region and denote it by D._{4}If By A to _{1}A contained inside _{3}D. The example P(H(R)) that we considered earlier is a special case of this construction.Finally, imagine that the lattice
Consider what happens as P(D → 0 if _{4}, δL, p)p < p._{c}Conversely, if P(D → 1._{4}, δL, p)The interesting question is what happens if
This is a remarkable conjecture for it says that the limiting probability does not depend on the lattice and is unchanged when the region is changed by a conformal map. In fact, Cardy, motivated by ideas from conformal field theory, proposed an exact formula for the limiting probability. To understand Cardy's formula, we note that conformal maps provides a great deal of versatility. For instance, any two regions D and momentarily forget about the fourth point _{4}P, there is then a conformal map carrying the region _{4}D and the three marked points P, _{1}P, and _{2}P into the equilateral triangle _{3}D' with vertices P' = (1, 0), _{1}P' = (1/2, /2), and _{2}P' = (0, 0). Now the fourth point _{3}P corresponds to a point _{4}P' = (_{4}x, 0) as shown below.Assuming that conformal invariance holds, Cardy's remarkable formula, interpreted in this way, says that x. As yet, conformal invariance and Cardy's formula have only been rigorously proven for the case of site percolation on the triangular lattice T, a result due to Smirnov in 2001. However, there is considerable evidence to suggest that they hold in wide generality.## Power laws and universalityTheoretical physics also predicts that a number of properties depend, not on the geometric properties of the graph, but only on its dimension. For instance, we know that the critical probability for site percolation on the triangular lattice is 1/2. This says that
We call such an expression a θ(p) ≈ (p - p)_{c}^{5/36} for any planar lattice. This is an indication of universality, the hypothesis, based on physical reasoning, that there are critical exponents, such as 5/36, that depend only on the dimension and not on the details of the particular lattice.In fact, it has been mathematically verified, by Lawler, Schramm, and Werner, that, for site percolation on the triangular lattice, Other, similar results hold as well. If we consider p < p, physics tells us that it should be true that_{c}
Also, suppose that P(n ≤ |C_{0}| < ∞), the probability that the cluster containing the origin contains a finite number of vertices greater than or equal to n. Physics again predicts that
Both of these power laws have been proven for site percolation on the triangular lattice by the work of Kesten, Lawler, Schramm, Smirnov, and Werner. At this time, it appears that theoretical physics, more specifically, conformal field theory and quantum gravity, have a great deal to say about percolation. One of the challenges before mathematicians is to create a mathematically rigorous theory to support these physical insights by, in particular, verifying conformal invariance for percolation on two-dimensional lattices and the universality of power laws. Mathematics has traditionally been tightly connected to physics. It is interesting to see that the link between these two disciplines is still so vital. The mathematical importance of this field is demonstrated by the fact that Wendelin Werner was awarded mathematics' highest honor, the Fields Prize, in part for his work in percolation.
## References- Béla Bollobás, Oliver Riordan,
*Percolation,*Cambridge University Press. 2006 - Geoffrey Grimmett,
*Percolation,*Second Edition. Springer. 1999 The above are two excellent references from which I have borrowed heavily. - Harry Kesten, What is ... Percolation?,
*Notices of the American Mathematical Society*,**53**(5), May 2006. 572-573. A short, readable survey. - S.R. Broadbent, J.M. Hammersley, Percolation processes. I. Crystals and mazes.
*Proceedings of the Cambridge Philosophical Society***53**, 1957. 629-641. Broadbent and Hammersley's original paper. - T.E. Harris, A lower bound for the critical probability in a certain percolation process.
*Proceedings of the Cambridge Philosophical Society,***56**, 1960. 13-20. - H. Kesten, The critical probability of bond percolation on the square lattice equals 1/2.
*Communications in Mathematical Physics,***74**, 1980. 41-59. - R.P. Langlands, P. Pouliot, Y. Saint-Aubin, Conformal invariance in two-dimensional percolation,
*Bulletin of the American Mathematical Society,***30**, 1994. 1-61. - S. Smirnov, W. Werner, Critical exponents for two-dimensional percolation,
*Mathematics Research Letters,***8**, 2001. 729-744. - Fields Medal Citation for Wendelin Werner
David Austin Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services. |
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance |