## Recent progress on percolation beyond
^{d} |

## Itai Benjamini - Oded Schramm |

## Revised September 14, 1999 |

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 denote the collection of all infinite transitive graphs (everything we say about transitive graphs applies also to almost-transitive graphs), let denote the collection of all infinite unimodular transitive graphs, and let denote the collection of graphs with positive Cheeger constant.

In [3] it has been shown that if , thus confirming Conjecture 4 (of [6]) for a large class of graphs. For the product of 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
each infinite cluster of Bernoulli percolation
in the nonuniqueness phase on *G* has infinitely many ends,
was proven for
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
.
It has been shown [18] that the infinite
clusters are **indistinguishable**, in the following sense.
If
is any automorphism-invariant property of a cluster
(such as having infinitely many ends),
then a.s. all infinite clusters have ,
or
a.s. none of the infinite clusters have .
(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
,
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
has
growth bounded by a polynomial and *G* is
not quasi-isometric to
or
,
the infinite cluster
of Bernoulli(*p*) percolation is transient if *p* is
sufficiently close to 1 [8].
For
,
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
,
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
[23].
At *p*=*p*_{u}(*G*), uniqueness holds if
is planar [7].
It has been shown that
uniqueness fails at *p*=*p*_{u}(*G*) in the case
[24],
more generally if
where
and
[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
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
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
,
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
is a nonamenable finitely generated
group, then there is a finite generating set *S* for ,
such that the corresponding Cayley graph
satisfies
*p*_{c}(*G*)<*p*_{u}(*G*) [21].

Let
,
and let
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
such that
,
where
*a*<1 is some constant that depends only on *G*, and
*d*(*y*_{0},*y*_{j}) is the graph distance from *y*_{0} to *y*_{j}.
One may hope that this rapid decay of
in
some directions can be used to prove that
for some *p*>*p*_{c} close to *p*_{c}. This would prove Conjecture 6
in the unimodular setting,
since
when *p*>*p*_{u}(*G*),
by Harris's inequality.

Another newly discovered property of
on graphs
is
for all *p* in the
nonuniqueness phase [18]. This is related to
the fact that *p*_{u}(*G*), where
,
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
,
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
,
the bound
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
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 , 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 and trees, but it is beyond the scope of this short note to give adequate treatment to that subject.

I. Benjamini & O. Schramm