$p_c$, $p_u$ and graph limits
Itai Benjamini
math.PR






p_c, p_u and graph limits 
    Itai Benjamini 
    2.7.17
==========================




A question relating the critical probability for percolation, the critical probability for a unique infinite cluster
and graph limits is presented, together with some partial results.


MSC subversive math




§ A QUESTION 



Let G be an infinite Cayley graph rooted at o.
Denote by B(o, n) the ball of radius n centered at o, and let H
be the limit, in the sense of <cit.>,
of the sequence of balls B(o, 1),B(o,2)...,
possibly passing to a subsequence to get convergence.
H is a unimodular random graph, <cit.>.





Does p_c(H) = p_u(G)   a.s. ?


In p-Bernoulli site percolation on a graph, each vertex is open with probability p independently.
p_c denotes the critical probability for the existence of an infinite open cluster (connected component),
and p_u is  the critical probability for uniqueness of the infinite open cluster,  see <cit.>.


A limit, a la <cit.>, of finite graphs G_n  is a random rooted infinite graph
with the property that neighborhoods of G_n around a random uniform vertex converge
in distribution to neighborhoods of the infinite graph around the root. When G is a Cayley graph
it might be the case that the limit along balls exists, and there is no need to pass to a subsequence?




Neither one of the directions in question <ref> seems immediate.
For a very simple example take G to be the 3-regular tree, T_3, then H is the canopy tree,
which can be thought of as an “infinite binary tree viewed from a leaf".
p_c(H) = p_u(G) =1. While for amenable Cayley graphs p_c = p_u <cit.>, it is conjectured that p_c < p_u
for non-amenable Cayley graphs <cit.>. It was shown in <cit.> that every non-amenable group admits a generating set
for which p_c < p_u. Showing that p_c(H) > p_c(G) for  non-amenable G, will be  an interesting progress towards question <ref>.
In <cit.>  it is proved that p > p_u is equivalent to non-decay of the connection probability.
For an amenable Cayley graph G, the limit along a Følner sequence is a.s. G.







Recall the critical parameters for weak survival of the contact process
λ_c and of strong survival λ_s, see <cit.> <cit.>.



Does λ_c(H) = λ_s(G)  a.s. ?



Question <ref>  is already non trivial for T_d, and it will be great to see a proof.




§ PARTIAL RESULTS AND FURTHER QUESTIONS


Given a Cayley graph G, it is often hard to understand the structure of H.
Still we now present several families of graphs for which the answer to question <ref> is yes.


Planar triangular lattices

When G is a cocompact triangular lattice in the hyperbolic plane, H is a.s. a triangulated quasi-canopy tree.
That is, a tree quasi isometric to the canopy tree. For simplicity we will assume it's the canopy tree.
View the canopy tree as an infinite ray with growing trees rooted along the ray. For every p_c(G) < p < p_u(G),
and any fixed vertex v  on the ray, there is a positive probability  of an open path from v to the leaves.
This gives a cutset separating o from infinity. When p > p_u(G),  the probabilities
of (1-p)- open paths from v to the leaves decays exponentially with the distance from v to o.
As the open path has to exit a ball of radius dist(v, o) centered at v,
which is isometric to a ball in the transitive lattice G.
Therefore restricted to the ball this  event has identical probability to the event of
an open path of a subcritical percolation  on G, <cit.> exiting a ball of radius dist(v, o), and by
<cit.> this probability decays exponentially.


Verify question <ref>  for  planar stochastic hyperbolic triangulations, <cit.>?



Graph products

It is interesting  to consider next the conjecture for T_d  ×, having a non planar instance with p_u < 1 analyzed.
Tom Hutchcroft challenged us with the following comment.
Grimmett and Newman's paper <cit.> implies the following statement:
Take the product of the d-regular tree with , and replace every -edge with a path of length n.
Then no matter how large n is, p_u of the resulting graph is always bounded from above by (d-1)^-1/2.
If question <ref>  has a positive answer, that would imply that if we take the product of the canopy tree with 
and stretch the lengths of the -edges  as much as we want, then p_c is always bounded above by (d-1)^-1/2 also.
Tom (private communication) proved that this is indeed the case. This supports a positive answer for T_d ×.
A first step towards a positive answer to question <ref> suggested by Tom, is to show that
p_u(T_d ×) = p_u(T_d ×). Is there non-uniqueness at p_u on T_d ×?



Percolation on T_d × at p_u admits infinitely many infinite clusters a.s., while on planar hyperbolic lattices
there is a unique infinite cluster at p_u, <cit.>, <cit.>. What is the behaviour at p_c for the corresponding H's?

Does p_c(×) = p_c(×)? Show no percolation at criticality on ×?





When a Cayley graph G is transient for the simple random walk, one expects that the infinite clusters of Bernoulli percolation are a.s.
transient as well. This is known for many families of Cayley graphs but not in general.
Show that the infinite cluster of supercritical Bernoulli  percolation on × is a.s. transient?


Free products



In <cit.> it was suggested that for any infinite Cayley graph G,
the graph limit along a converging subsequence of balls, H, is invariantly amenable,
and therefore p_c(H) = p_u(H) and λ_c(H) = λ_s(H).
In <cit.> it is proved that if G has Yu's property A, then H is hyperfinite or invariantly amenable.
These include hyperbolic groups, groups with finite  asymptotic dimension and amenable groups.
(<cit.> contains many further questions regarding graph limits along balls).



Other Cayley graphs Tom Hutchcroft  suggested to look at, as a possible counterexamples, are free product of ^2 and an edge,
and  a free product of a hyperbolic Cayley graph and an edge.



The free product of ^2 and an edge has finite asymptotic dimension, <cit.>.
Hence the limit along balls is invariantly amenable
(or hyperfinite) unimodular random graph  and thus the limiting graph has one end a.s., see <cit.>.
H is not contained in a finite number of copies of ^2  as
H has a uniform exponential lower bound on it's volume growth, as G contained a regular tree and therefore
H contained a canopy.

H intersects any copy of ^2 in a finite set, as otherwise we will get more than one end.
Thus p_c(H) =1 a.s., since the infinite  cluster has to cross infinitely many cut edges.

The free product of an hyperbolic group G and an edge is hyperbolic.
Limits along balls of hyperbolic groups is invariantly amenable,
So the limit has one end a.s.
and hence  p_c(H) = 1 a.s., by the same argument as above.



Assume a Cayley graph G has infinitely many ends. Show that p_c(H) =1.



To answer question <ref>, one needs to show that the limit along balls of any Cayley graph
which is  not quasi isometric to , has one end a.s.


Final comments

It is still open if there is a Cayley graph in which the sequences  of balls
B(o, 1),B(o,2)... is an expander family, <cit.>? I conjecture that there is no such Cayley graph.
In this case H will be non-amenable.

Recall a sequence of finite subgraphs  in a graph  is exhausting,
if  each graph in the sequences contains all the previous subgraphs and the union
is the whole graph.

If G is hyperbolic and we consider the limit along an arbitrarily
sequence of  exhausting finite sets, we expect to get p_c(H) ≥ p_u(G).
This might hold for any  exhausting sequence of   finite sets
on any Cayley graph. Gromov's monster, <cit.>, might serve as a counter example.






Let G be the Diestel-Leader graph DL(3,2), <cit.>,  which is a non-amenable, non-unimodular  vertex transitive graph.
The limit along balls of  DL(3,2)  is a horocyclic product of two
canopy trees, see figure. Show that p_c(H) < 1. Does p_c(H) = p_u(G)?
Does p_c(G) < p_u(G)?









Maybe a version of question <ref> for the critical temperature for  magnetization of the ferromagnetic Ising model,
will be more tractable?


We believe that the answer to question <ref>  will still be positive   if rather than taking limit along balls,
we  consider "round" sets such as limit of isoperimetric minimizers, or minimizers along Green balls,
or taking a sequence sets {K_n}, where K_n is a set of vertices of size n minimizing
the expected escape probability of simple random walk starting from a random uniform element on the set.

Assume G and G' are quasi isometric. Let H be the limit along some exhausting sequence of G.
Is there an exhausting sequences of G', so that H' is quasi isometric to H? That is, there is a coupling of the two
random rooted graphs H and H' which is a quasi isometry.




We would like to end with a random walk question of similar spirit.
In <cit.> it was proved that the limit of bounded degree finite planar graphs, is a.s. recurrent
for the simple random walk.

Which Cayley graphs has an exhausting sequence of subgraphs with a limit that is a.s. transient?
One feature of transient bounded degree  planar graphs, is that they admit non constant Dirichlet harmonic functions,
that is, harmonic functions with a gradient in l^2,
see <cit.> and <cit.>. Let G be an infinite transient Cayley graph.




Assume G has no non constant Dirichlet harmonic functions. Is there an exhausting  sequence of finite subgraphs, such that
H is a.s. transient?


If there is such a sequence,  probably the limit along growing balls is a.s. transient.


There are no non constant Dirichlet harmonic functions on T_3 ×.
The limit along boxes of T_3 × is a.s. a ×, which is transient.


All examples we know, including limits along balls in  products of trees, are Liouville,
 

Are there examples in which limits along balls are a.s. non-Liouville?





Acknowledgements: Thanks to Lewis Bowen,  Tom Hutchcroft for  very useful discussions.

BKC

AL
D. Aldous and R. Lyons,
Processes on unimodular random networks.
Electron. J. Probab. 12 (2007), no. 54, 1454–-1508.



BDK
G. Bell, A. Dranishnikov and J. Keesling,
On a formula for the asymptotic dimension of free products.
Fund. Math. 183 (2004), no. 1, 39–-45.

BS96
I. Benjamini and O. Schramm,
Harmonic functions on planar and almost planar graphs and manifolds, via circle packings.
Invent. Math. 126 (1996), no. 3, 565-–587.




B
I. Benjamini,
Expanders are not hyperbolic. Israel J. Math. 108 (1998), 33-–36.

BE
I. Benjamini and G. Elek,
Sparse graph limits along balls (2017).







BS96
I. Benjamini and O. Schramm, Percolation beyond ^d, many questions and a few answers.
Electron. Comm. Probab. 1 (1996), no. 8, 71-–82.

BS
I. Benjamini and O. Schramm,
Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (2001), no. 23, 13 pp.

BS01
I. Benjamini and O. Schramm,
Percolation in the hyperbolic plane. J. Amer. Math. Soc. 14 (2001), no. 2, 487-–507.






BK
R. Burton and M. Keane,  Density and uniqueness in percolation.
Comm. Math. Phys. 121 (1989), no. 3, 501–-505.



C
N. Curien, Planar stochastic hyperbolic triangulations. Probab. Theory Related Fields 165 (2016), no. 3-4, 509–-540.

DL
R. Diestel and I.  Leader,
A conjecture concerning a limit of non-Cayley graphs.
J. Algebraic Combin. 14 (2001), no. 1, 17-–25.


DT
H. Duminil-Copin and V. Tassion,
A new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model.
Comm. Math. Phys. 343 (2016), no. 2, 725-–745.

GN
G. Grimmett and C. Newman, Percolation in ∞ +1 dimensions.
Disorder in physical systems, 167–-190, Oxford Sci. Publ., Oxford Univ. Press, New York, 1990.



G
M. Gromov,
Random walk in random groups.
Geom. Funct. Anal. 13 (2003), no. 1, 73–-146.


H
T. Hutchcroft,
Harmonic Dirichlet Functions on Planar Graphs.
https://arxiv.org/abs/1707.07751



L
R. Lyons, Phase transitions on nonamenable graphs.
Probabilistic techniques in equilibrium and nonequilibrium statistical physics. J. Math. Phys. 41 (2000), no. 3, 1099–-1126.


LS
R. Lyons and O. Schramm, Indistinguishability of percolation clusters. Ann. Probab. 27 (1999), no. 4, 1809–-1836.

PS
I. Pak and T. Smirnova-Nagnibeda,
On non-uniqueness of percolation on nonamenable Cayley graphs. C. R. Acad. Sci. Paris Sér. I Math. 330 (2000), no. 6, 495-–500.



P
R. Pemantle, The contact process on trees. Ann. Probab. 20 (1992), no. 4, 2089-–2116.

S
H. Sako,
Property A and the operator norm localization property for discrete
metric spaces.
J. Reine Angew. Math. 690 (2014) 207–216.

Sh
R. Schonmann,  Percolation in ∞+1 dimensions at the uniqueness threshold.
Perplexing problems in probability, 53–-67, Progr. Probab., 44, Birkhäuser Boston, Boston, MA, 1999.





