Percolation Theory for Mathematicians

The earliest example of percolation was discussed in Broadbent (1954) and Broadbent and Hammersley (1957) as a model for the spread of fluid or gas through a random medium. The fluid, say, spreads through channels; fluid will move through a channel if and only if the channel is wide enough. There is therefore no randomness in the motion of the fluid itself, such as in a diffusion process, but only in the medium, i.e., in the system of channels. Broadbent and Hammersley modeled this as follows. The channels are the edges or bonds between adjacent sites on the integer lattice in the plane, ℤ². Each bond is passable (blocked) with probability p(q = 1 − p), and all bonds are independent of each other. Let P_p denote the corresponding probability measure for the total configuration of all the bonds. One is now interested in probabilistic properties of the configuration of passable bonds, and, especially in the dependence on the basic parameter p of these properties. Broadbent and Hammersley began with the question whether fluid from outside a large region, say outside |x| < N, can reach the origin. This is of course equibalent to asking for the probability of a passable path¹⁾ from the origin to |x| ≥ N. For v ε ℤ², let W(v) be the union of all edges which belong to a passable path starting at v.

This chapter discusses the graphs with which we shall work, as well as several graph-theoretical tools. Except for the basic definitions in Sect. 2.1–2.3 the reader should skip the remaining parts of this chapter until the need for them arises.

Let G be a graph satisfying (2.l)–(2.5) with vertex set l and edge set ε. The most classical percolation model is the one in which all bonds of q are randomly assigned to one of two classes, all bonds being assigned independently of each other. This is called bond-percolation, and the two kinds of bonds are called the passable or open bonds and the blocked or closed bonds. Instead of partitioning the bonds one often partitions the sites into two classes. Again all sites are assigned to one class or the other independently of each other. One now speaks of site-percolation and uses occupied and vacant sites to denote the two kinds of sites. The crucial requirement in both models is the independence of the bonds or sites, respectively. This makes the states of the bonds or sites into a family of independent two-valued random variables. Accordingly the above models are called Bernoulli-percolation models.

This chapter contains the well known FKG inequality and a formula of Russo’s for the derivative of P_p{E} with respect to p for an increasing event E. No periodicity assumptions are necessary in this chapter, so that we shall take as our probability space the triple (Ω_l, B_l, P_l) as defined in Sect. 3.1. E₁ will denote expectation with respect to P_l.

The principal result of this chapter is that decreases exponentially in n, provided certain crossing probabilities are sufficiently small. This is almost the only theorem which works for a general periodic percolation problem in any dimension. No axes of symmetry are required, nor does the graph have to be one of a matching pair. When Theorem 5.1 is restricted to one-parameter problems, then it shows that (5.1) decreases exponentially for p < p_T and that in general p_T = p_S (see (3.62)–(3.65) for definition). In Sect. 5.2 we discuss lower bounds for when p is so large that percolation occurs. In the one-parameter case this is the interval p_H < p ≤ 1. It turns out that (5.2), and hence (5.1) does not decrease exponentially in this domain.

The object of this chapter is a result which states that if the crossing probabilities of certain rectangles in both the horizontal and vertical direction are bounded away from zero, then so are the crossing probabilities for larger rectangles. This result will then be used to prove the existence of occupied circuits surrounding the origin. The idea is to connect an occupied horizontal crossing of [0,n₁] × [0,n₂] and an occupied horizontal crossing of [m,n₁ + m] × [0,n₂] by means of a suitable occupied vertical crossing, in order to obtain a horizontal crossing of [0,n₁ + m] × [0,n₂]. This would be quite simple (compare the proof of Lemma 6.2) if one had a lower bound for the probability of an occupied vertical crossing of [m,n₁] × [0,n₂], but in the applications one only has estimates for the existence of occupied vertical crossings of rectangles which are wider and/or lower. One therefore has to use some trickery, based on symmetry to obtain the desired connections. Such tricks were developed independently by Russo (1978) and Seymour and Welsh (1978). (See also Smythe and Wierman (1978), Ch. 3 and Russo (1981).) These papers dealt with the one-parameter problems on the graphs G₀ or G₁ (see Ex. 2.1(i) and (ii)) and therefore had at their disposal symmetry with respect to both coordinate axes, as well as invariance of the problem under interchange of the horizontal and vertical direction. We believe that neither of these properties is necessary, but so far we still need at least one axis of symmetry. We also have to restrict ourselves to a planar modification G_pl of a graph G which is one of a matching pair of graphs in ℝ².

The first step is to show that for a parameter point p₀ which satisfies Condition A or B of Ch. 3 there exist large rectangles for which the crossing probabilities in both the horizontal and vertical direction are bounded away from zero.

In this chapter we study the behavior of the percolation probability and the expected size of an occupied cluster in a one-paremeter problem. As defined in Ch. 3 this means that we consider probability measures for which is the same for all vertices v of the studied graph G, and the occupancies of all vertices are independent.

The arguments of Sykes and Essam (1964) which led them (not quite rigorously) to values for p_H(G) for certain graphs were based on “the average number of clusters per site”.

We first give a theorem of Hammersley’s (1961) stating that for any connected graph G the critical probability in a one-parameter problem for site-percolation on G( = p_H(G) in our notation) is at least as large as the critical probability for bond-percolation on G( =p_H( is the covering graph of G; see Sect. 2.5).

Many people have studied the electrical resistance of a network made up of random resistors. It was realized quite early that critical phenomena occur, and that there is a close relation with percolation theory, in special cases where the individual resistors can have infinite resistance (or zero resistance). We refer the reader to Kirkpatrick (1978) and Stauffer (1979) for a survey of much of this work. In these introductory paragraphs we shall assume that the reader knows what the resistance of a network is, but we shall come back to a description of resistance in Sect. 11.3.

We shall list here some problems which seem of interest to us, in the order of the chapters to which they refer. It appears that the most significant problem is problem 8. We know little about how the problems compare in difficulty, but some of the problems are only of technical interest.