Percolation

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

Consider the following scenarios:

Suppose a large porous rock is submerged under water for a long time, will the water reach the center of the stone?
How far from each other should trees in an orchard be planted in order to minimize the spread of fire?
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 $\wedge$ consists of the set $\mathbb{Z}^d$ 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 $\wedge$ , we let $p \in [0,1]$ be the crucial parameter of our model. Then we select bonds and sites independently with the same probability $p$ . 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 $p$ and closed with probability $1-p$ ). 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.

Figure 1. Parts of the open subgraphs in bond percolation on the square lattice $\mathbb{Z}^2$ .

Figure 1. Parts of the open subgraphs in bond percolation on the square lattice $\mathbb{Z}^2$ .

Figure 2. Parts of the open subgraphs in site percolation on the square lattice $\mathbb{Z}^2$ . The filled circles are the open sites.

In general, we assume that $\wedge$ 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 $x$ and $y$ in the open subgraph, we write ${x \rightarrow y}$ if there is an open path from $x$ to $y$ . We also write { ${x \rightarrow \infty}$ } if there is an infinite open path starting at $x$ .

Let $C_x$ denote the component (i.e., the set vertices connected to $x$ via an open path) containing $x$ 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 $x$ in the cluster, { $x \rightarrow \infty$ } holds. If $x$ is not open, then in site percolation, $C_x = \emptyset$ , and in bond percolation, $C_x = {x}$ .

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 $x$ to infinity? This is the same as asking for the probability that $C_x$ is infinite. We denote this probability as $\theta_{x}(p)$ and call it as percolation probability.

More formally, we can use bond percolation as an example. $\theta_{x}(p)=P(x \rightarrow \infty ) = P(|C_x| = \infty )$ , where $|C_x|=|V(C_x)|$ is the number of sites in $C_x$ . Two sites $x$ and $y$ are equivalent if there is an automorphism of $\wedge$ mapping $x$ to $y$ . If we assume that all sites of $\wedge$ are equivalent, then $\theta_{x}(p)$ is the same for all sites $x$ and we can write $\theta_{x}(p)=\theta(p)$ . Clearly, $\theta_{x}(0)=0$ and $\theta_{x}(1)=1$ , since there are no open bonds at all when $p=0$ and all bonds are open when $p=1$ . If $x$ and $y$ are sites at distance $d$ , then $\theta_{x}(p)\geq p^d\theta_{y}(p)$ , so either $\theta_{x}(p)=0$ for every site $x$ , or $\theta_{x}(p)>0$ for every site $x$ . It is also intuitively clear that $\theta(p)$ is an increasing function of $p$ . Thus, the graph of $\theta(p)$ should have the form indicated in figure 3. It now follows that we can define a critical probability $p_H$ (indicated as $p_c$ in figure 3), $0\geq p_H \geq 1$ , by $p_H =$ sup $\{p:\theta(p)=0\}=$ inf ${p:\theta(p)>0}$ . This means that if $p<p_H$ , then $\theta_{x}(p)=0$ $\forall x$ , and if $p>p_H$ , then $\theta_{x}(p)>0$ $\forall x$ . For a graph $\wedge$ , we write $p^{s}_{H}$ for site percolation and $p^{b}_{H}$ for bond percolation.

Figure 3. Graph of $\theta(p)$ with respect to $p$ .

In the next post, we will talk more about critical probability and percolation on $\mathbb{Z}^2$ .