Recent progress on percolation beyond Z^d

Itai Benjamini - Oded Schramm

Revised September 14, 1999

The purpose of this note is to give a brief indication of the recent progress made related to the problems described in [6], and to give pointers to the relevant papers. We hope to keep this survey up to date, as new results appear. The PostScript version of this note is also available.

An aspect of the theory which was not anticipated in [6] is the crucial importance of unimodularity to some of the questions raised. (Every Cayley graph is unimodular, but not every transitive graph is.) See [2] for a discussion of unimodularity and some of its implications to percolation.

In the following, let ${\cal G}$ denote the collection of all infinite transitive graphs (everything we say about transitive graphs applies also to almost-transitive graphs), let ${\cal U}$ denote the collection of all infinite unimodular transitive graphs, and let ${\cal C}$ denote the collection of graphs with positive Cheeger constant.

In [3] it has been shown that $\theta(p_c)=0$ if $G\in{\cal U}\cap{\cal C}$, thus confirming Conjecture 4 (of [6]) for a large class of graphs. For the product of ${\mathbb Z}$ with a tree of sufficiently high degree, this was proved earlier [27]. This fact also holds for the enhanced binary tree (which is not transitive) [28].

Conjecture 5, stating that for $G\in{\cal G}$ each infinite cluster of Bernoulli percolation in the nonuniqueness phase on G has infinitely many ends, was proven for $G\in{\cal U}$ in [12] (a later, simpler proof can be found in [18]), and in the nonunimodular case above p_c in [13]. Thus, the only remaining case to be treated is the (presumably nonexistant) case of a nonunimodular transitive graph such that at p_c there is a.s. an infinite cluster.

Consider Bernoulli percolation on some $G\in{\cal U}\cap{\cal C}$. It has been shown [18] that the infinite clusters are indistinguishable, in the following sense. If $\cal A$ is any automorphism-invariant property of a cluster (such as having infinitely many ends), then a.s. all infinite clusters have $\cal A$, or a.s. none of the infinite clusters have $\cal A$. (See also [12] for a simpler proof of a weaker form of this statement.) In the nonunimodular case, cluster indistinguishability holds for certain ``robust'' properties [13], but fails for general invariant properties.

It has been shown that on every $G\in{\cal U}\cap{\cal C}$, when Bernoulli percolation produces at least one infinite cluster, a.s. all infinite clusters contain subgraphs with positive Cheeger constant [5]. This was then used to show that simple random walk on these clusters is transient and has positive speed [5]. It follows from ergodicity and indistinguishability that the speed does not depend on the cluster or on the walk. When $G\in{\cal G}$ has growth bounded by a polynomial and G is not quasi-isometric to ${\mathbb Z}$ or ${\mathbb Z}^2$, the infinite cluster of Bernoulli(p) percolation is transient if p is sufficiently close to 1 [8]. For $G\in{\cal G}-{\cal C}$, all infinite clusters of Bernoulli(p) percolation are strongly amenable [14] (which means that there is a nested sequence of nonempty connected finite subgraphs with boundary to volume ratio going to zero).

It has been shown that when $G\in{\cal U}$, for every p>p_u(G) there is a.s. a unique infinite cluster of Bernoulli(p) percolation on G [12]. This was then generalized to every $G\in{\cal G}$ [23]. At p=p_u(G), uniqueness holds if $G\in{\cal G}\cap{\cal C}$ is planar [7]. It has been shown that uniqueness fails at p=p_u(G) in the case $G=T\times{\mathbb Z}$ [24], more generally if $G=A\times B$ where $A\in{\cal C}\cap{\cal G}$ and $B\in{\cal G}$ [22], or if G is the Cayley graph of a Kazhdan group [18]. Question 5 is thus answered, except that one could hope for a characterization of the transitive graphs G where there is uniqueness at p_u. For example, the case of lattices in hyperbolic 3-space is open.

Perhaps the most interesting conjecture of [6], Conjecture 6, stating that graphs in ${\cal G}\cap{\cal C}$ satisfy p_c(G)<p_u(G) (and therefore have a nonempty nonuniqueness phase), is still very much open, but some progress has been made. The conjecture was motivated by [9], which established it for the product of ${\mathbb Z}$ with a regular tree of sufficiently high degree. If the ratio between the Cheeger constant and the degree in a transitive graph G is larger than $1/\sqrt{2}$, then p_c(G)<p_u(G) [25] (this follows from combining an upper bound on p_c(G) and a lower bound on p_u(G) from [6] with a Cheeger-type inequality from [19]). The conjecture also holds for planar graphs [7]. For planar Cayley graphs with high genus, this has been shown earlier in [17]. If $\Gamma$ is a nonamenable finitely generated group, then there is a finite generating set S for $\Gamma$, such that the corresponding Cayley graph $G(\Gamma,S)$ satisfies p_c(G)<p_u(G) [21].

Let $G\in{\cal U}\cap{\cal G}$, and let $\tau_{p}(x,y)$ be the probability that the two vertices x and y are in the same component of Bernoulli(p) percolation. It can be shown [26] that one may find a sequence of vertices y_j with $d(y_0,y_j)\to\infty$ such that $\tau_{p_c}(y_0,y_j)< a^{d(y_0,y_j)}$, where a<1 is some constant that depends only on G, and d(y₀,y_j) is the graph distance from y₀ to y_j. One may hope that this rapid decay of $\tau_{p_c}$ in some directions can be used to prove that $\inf\tau_p=0$ for some p>p_c close to p_c. This would prove Conjecture 6 in the unimodular setting, since $\inf_{x,y\in V}\tau_p(x,y)> 0$ when p>p_u(G), by Harris's inequality.

Another newly discovered property of $\tau$ on graphs $G\in{\cal U}$ is $\inf \bigl\{\tau_p(x,y):\,x,y\in V\bigr\} =0$ for all p in the nonuniqueness phase [18]. This is related to the fact that p_u(G), where $G\in{\cal G}$, can be characterized as the infimum of p such that the probability of the existence of an open path joining two balls of radius r goes to 1 as $r\to\infty$, uniformly in the centers of the balls [23].

If true, Conjecture 6 provides a percolation characterization of amenability. A similar characterization using a mixture of Bernoulli percolation and the wired uniform spanning forest does exist [4]. Other characterizations, using the Ising model with an external field and the random cluster model, appear in [16] and [15], respectively.

In connection to Question 3, It has been shown that p_u(G)<1 when G is a Cayley graph of a group that is finitely presented with one end [1] or a Kazhdan group [18] or belongs to a certain collection of wreath products [18]. For every $G\in{\cal G}$, the bound $p_u(G)\geq \liminf_{n\to\infty} a_n(G)^{-1/n}$ holds, where a_n(G) is the number of simple closed paths in G of length n that contain some fixed vertex of G [26].

Conjecture 1, stating that Cayley graphs of infinite finitely generated groups that are not finite extensions of ${\mathbb Z}$ have p_c<1, is still open for groups of intermediate (sub-exponential, but super-polynomial) growth. Recently, it has been proven that p_c<1 for Grigorchuk groups [20] (which are the only known intermediate growth groups), by showing that every Grigorchuk group contains a product of two infinite groups. The questions regarding the characterization of graphs satisfying p_c(G)<1 gained importance due to [11], which showed that p_c(G)<1 is equivalent to the existence of a phase transition for several other statistical-physics models on G.

It has been shown that $p_c^{\hbox{bond}}(G)<p_c^{\hbox{site}}(G)$, except in some very special exceptional cases [10]. This is slightly related to Question 1.

Most of the progress reported above is only related to transitive graphs. Unfortunaly, there has been no progress on the other questions in [6].

Let us note that there has been some interest and progress in other statistical physics models on graphs other than ${\mathbb Z}^d$ and trees, but it is beyond the scope of this short note to give adequate treatment to that subject.

I. Benjamini & O. Schramm