This post presents a couple of results regarding percolation on (and especially ), which are valuable mainly because they tell us that percolation on these graphs is non-trivial i.e. none of the critical probabilities is 0 or 1. But on a concrete level, they actually do more: they give explicit bounds on the critical probabilities.
Proposition 1. For bond percolation on , we have
This proof hinges on counting , the number of self-avoiding walks of length (in the language of graph theory, paths) on . We will make use of the obvious bound
Proof: The middle inequality was discussed in the previous post, so it suffices to do the first and last ones. Let’s start with the first.
Choose some and consider the bond percolation on where every bond is open with probability . Let be the cluster containing the origin and note that any site in must be connected to the origin by an open path starting at the origin. (It’s a little hard to see, but this is where the self-avoiding condition comes in: if the walk from the origin to the site intersected itself, we could “excise” the loop and then get another path that’s more likely to be open, because it is shorter.) The size of is bounded by the number of such paths and the probaibility of a path of length being open is , so
because . Since the expected size of is finite for any , we conclude that .
Proposition 2. For bond percolation on , we have
This proof hinges on studying the dual graph of (more on this in a second) and using a technical lemma that I won’t prove.
For a graph , the dual is a graph whose vertices correspond to faces of with edges connecting adjacent faces in . For example,
In the context of percolation, we call the sites and bonds of dual sites and dual bonds, with a dual bond taken to be closed when the original bond is open, or vice versa. (We’re associating bonds to dual bonds here by where is the edge of connecting the faces of that meet at ).
In , if is a finite subgraph of with vertex set , then must have some infinite component . We define to be the bonds of that are dual to bonds of joining and .
Put another way, you take some finite subgraph, and look at all the edges connecting it to the infinite component of it’s complement. This set of edges maps to some set of edges in the dual, and that set is . The lemma says that looks like the boundary of .
Lemma 3. is a cycle containing .
Proof: As before, take some , and consider bond percolation on where each bond is open with probability . Take dual bonds to be open if is closed and vice versa, and call a cycle in the dual consisting of open bonds an open dual cycle.
Let be the segment connecting the origin to and some dual cycle of length surrounding . must cut the -axis between and , so there are fewer than choices for the dual bond that cuts the -axis. The rest of is a path of length , and since the dual of is isomorphic to , there are possibilities for this portion of . In total, we have fewer than possibilities for .
Let be the number of open dual cycles surrounding . An open dual cycle of length occurs with probability , so
This means that as , and in particular, eventually. If is the event that , this means that (if were never zero, then integrating over a set of measure 1 would have to give something that is at least 1). Now let be the event that all the bonds in are open, which occurs with probability , which is independent of .
If and both occur, then cannot be contained in a cycle of the dual graph (since ), so it must be infinite by our lemma. Thus
so there is an infinite open cluster with probability 1. This means that , and since is any probability , we have .
Remark 1. \leavevmode
- Recalling that , we can chain these together into
showing that the critical probabilities for bond percolation on are non-trivial.
- The bound of is crude, and these inequalities can be sharpened by using tighter inequalities. For example, noting that (you can just concatenate paths), we see by Fekete’s lemma that . This is called the connective constant, and our result becomes
so we just need to estimate this constant, which I won’t get into but can certainly be done.
- Since contains within it for , we can recall the result at the end of the previous post to obtain
giving non-triviality of critical probabilities for .
These results are only for bond percolation. We can use them to say things about site percolation as well though, by showing that percolation is “more likely” in the site model than the bond model.
Theorem 4. For any graph , we have and .
Proof: The key claim is that for any site , integer , and probability ,
(Here, and are the probability measures induced by bond and site percolation where bonds and sites are open with probability , respectively. Throughout this proof, we use such superscripts to indicate the type of percolation being considered.)
From this claim, we let to obtain . Then, if , we have as well, so .
For , we argue similarly:
and so , meaning that
It remains to show the claim. We begin by writing as
If is closed, is empty, so the second term is zero. Thus we see that
and so our claim is equivalent to
Next, we note that since the event depends only on vertices that are within of , it suffices to consider the subgraph of points within of . The idea now is to construct a sequence of subsets of (the vertex set of denoted such that . The constant is random, and the letters stand for reached, dead, and untested respectively.
The construction is as follows:
- Pick a bond where and . Remove from . If is open, add it to and leave alone; otherwise add it to and leave alone. This gives the new triplet.
- Repeat 2 until no such bond exists, and set , completing the process. (This must happen eventually because is finite.)
In the end, is a connected set of open sites with no neighbors in that is disjoint from the sites of which are all closed, so it is exactly . Note that the conditional probability of being open is always .
Now, consider an analogous sequence for , . The difference here is that after picking , we check whether is open (conditioned on the sequence up to that open). This probability is always as well, so and have the same distribution.
In particular, and have the same distribution. Since is contained in (it is the vertex set of the subgraph spanned by the bond we found to be open), the claim follows, concluding the proof.
So this shows that are not zero. To show that they are also not 1, we need another inequality, namely:
Theorem 5. For percolation on an infinite connected graph with maximum degree ,
The proof is similar, but more involved, so I’ll skip it here. The upshot of all this is that are all non-trivial for . In the next few posts, we’ll take the next step and actually determine and .