Percolation theory: basic concepts

Note: In this post, I will use standard terminology of graph theory, such as vertex, edge, component, path, subgraph, etc.

Consider the following scenarios:

1. Suppose a large porous rock is submerged under water for a long time, will the water reach the center of the stone?
2. How far from each other should trees in an orchard be planted in order to minimize the spread of fire?
3. How infectious does a strain of flu have to be to create a pandemic? What is the expected size of an outbreak?

The problems above are all related to percolation theory.

The aim of this post is to introduce some basic concepts of percolation theory. Percolation is a simple probabilistic model which exhibits critical phenomena. This means that there is a natural parameter in the model at which the behavior of the system changes drastically. Interpreted narrowly, percolation theory can be taken as the study of the component structure of random subgraphs of graphs.

In the standard model of percolation theory, we consider the underlying graph to be a lattice or lattice-like graph. For example, suppose the graph consists of the set as the vertex set together with an edge between any two points having Euclidean distance 1. For Percolation, we use the term sites instead of vertices and bonds instead of edges. To obtain a random subgraph of , we let be the crucial parameter of our model. Then we select bonds and sites independently with the same probability . The sited and bonds selected are called open and those not selected are called closed. (In other words, each sites or bonds open with probability and closed with probability ). When our random subgraph is obtained by keeping the open sites, we speak of site percolation; when we keep the open bonds, bond percolation. In site percolation, the open subgraph is formed by the open sites; in bond percolation, the open subgraph is formed by the open edges and all vertices.

In general, we assume that is connected, infinite, and locally finite (i.e., every vertex has finite degree). An open path is a path (i.e., self-avoiding walk) in the open subgraph. For sites and in the open subgraph, we write if there is an open path from to . We also write {} if there is an infinite open path starting at .

Let denote the component (i.e., the set vertices connected to via an open path) containing in our random subgraph. In percolation, we call the components of the random subgraph open clusters. Since the graphs we consider are locally finite, an open cluster is infinite if and only if, for every site in the cluster, {} holds. If is not open, then in site percolation, , and in bond percolation, .

Using figures 1 and 2 as an example: there are 10 open clusters for bond percolation in figure 1, and there are 4 open clusters for site percolation in figure 2.

Now, our first basic question is the following: what is the probability that there exists an open path from an open site to infinity? This is the same as asking for the probability that is infinite. We denote this probability as and call it as percolation probability.

More formally, we can use bond percolation as an example. , where is the number of sites in . Two sites and are equivalent if there is an automorphism of mapping to . If we assume that all sites of are equivalent, then is the same for all sites and we can write . Clearly, and , since there are no open bonds at all when and all bonds are open when . If and are sites at distance , then , so either for every site , or for every site . It is also intuitively clear that is an increasing function of . Thus, the graph of should have the form indicated in figure 3. It now follows that we can define a critical probability (indicated as in figure 3), , by supinf. This means that if , then , and if , then . For a graph , we write for site percolation and for bond percolation.

Figure 3. Graph of with respect to .

In the next post, we will talk more about critical probability and percolation on .