IS THE CRITICAL PERCOLATION PROBABILITY LOCAL? ITAI BENJAMINI,ASAFNACHMIASANDYUVAL PERES 9 Abstract. Weshowthatthecriticalprobabilityforpercolationonad-regularnon- 0 amenable graph of large girth is close to the critical probability for percolation on 0 an infinite d-regular tree. This is a special case of a conjecture due to O. Schramm 2 n on thelocality of pc. Wealso provea finiteanalogue of theconjecturefor expander a graphs. J 9 2 ] 1. Introduction R P Denotebyp (G)thecritical probabilityforBernoullibondpercolation onaninfinite c . h graph G, that is, t a m p (G) = inf p ∈ [0,1] : P ∃ an infinite component > 0 . c n p o (cid:0) (cid:1) [ Isthevalueof p determinedbythelocal geometry of thegraphor byglobal properties 1 c v (such as volume growth and expansion)? In this note we show that the former is the 6 1 correct answer for non-amenable graphs with tree-like local geometry, and discuss a 6 conjecture of Schramm that p is locally determined in greater generality. 4 c 1. Recall that the girth g of a graph G is the minimum length of a cycle in G. Let P be 0 the transition matrix of the simple random walk (SRW) on G and let I be the identity 9 0 matrix. The bottom of the spectrum of I −P is defined to be the largest constant λ 1 : v with the property that for all f ∈ ℓ2(G) we have i X r hf,(I −P)fi≥ λ1hf,fi. (1.1) a Kesten ([9], [10]) proved that G is a non-amenable Cayley graph if and only if λ > 0. 1 This was extended by Dodziuk [7] to general infinite bounded degree graphs (for more background on non-amenability see [11] and [14]). Theorem 1.1. There exists an absolute constant C > 0 such that if G is a non- amenable regular graph with degree d and girth g such that the bottom of spectrum of I −P is λ > 0, then 1 Clog 1+ 1 p (G) ≤ 1 + (cid:0) λ21(cid:1) . c d−1 dg 1 2 ITAIBENJAMINI,ASAFNACHMIASANDYUVALPERES Recall that p (T ) = 1 where T is an infinite d-regular tree and that for any d- c d d−1 d regular graph G we have p (G) ≥ 1 . Thus, Theorem 1.1 asserts that non-amenable c d−1 graphs with large girth and degree d have p close to the lowest possible value, p (T ). c c d It is easy to construct non-amenable graphs with arbitrary girth, for example, take the Cayley graph of ha,b,c | cn = 1i. Olshanskii and Sapir [13] constructed for any k ≥ 2a group Γ with the following property. For any ℓ > 0 there is a set S consisting k ℓ of k generators for Γ , such that the Cayley graph G(Γ ,S ) has girth at least ℓ and k k ℓ inf λ (G(Γ ,S )) > 0(asremarkedin[13],fork ≥ 4suchgroupswerealsoconstructed ℓ 1 k ℓ by Akhmedov [2]). Let G be a graph and v a vertex in G. Denote by B (v,R) the ball of radius R in G G centered at v, in the graph metric, with its induced graph structure. We say that a sequence of transitive graphs G converges to G if for any integer R > 0 there exists n N such that B (v ,R) and B (v,R) are isomorphic as rooted graphs, for all n ≥ N Gn n G (note that the choices of v and v are irrelevant due to transitivity). Oded Schramm n (personal communication) suggested the following conjecture. Conjecture1.2. LetG besequenceofvertextransitiveinfinitegraphswithsup p (G ) < n n c n 1 such that G converges to a graph G. Then p (G ) → p (G). n c n c Thisconjecture is open for infinitegraphseven if weassume thatthey are uniformly nonamenable. Wecanprovethefollowinganalogueoftheconjectureforfiniteexpander graphs, by extending the analysis of [1], Proposition 3.1. For each n ≥ 1, let G be n a finite graph and let U be a uniformly chosen random vertex in G . We say that n n the sequence of finite graphs {G } converges weakly to an infinite rooted graph (G,ρ) n (where ρ is a fixed vertex of G) if for each R > 0 we have P B (U ,R)6= B (ρ,R) → 0 as n → ∞, (cid:16) Gn n G (cid:17) where the event above means that the balls are not isomorphic as rooted graphs. This is a special case of the graph limits defined in [5]. For two sets of vertices A and B, write E(A,B) for the set of edges with one endpoint in A and the other in B. Recall that the Cheeger constant h(G) of a finite graph G = (V,E) is defined by |E(A,V \A)| h(G) = min : 0< |A| ≤ |V|/2 . n o A⊂V |A| Theorem 1.3. Let (G,ρ) be an infinite bounded degree rooted graph and let G be a n sequence of finite graphs with uniform Cheeger constant h > 0 and a uniform degree bound d, such that G → G weakly. Let p ∈ [0,1] and write G (p) for the graph of open n n IS THE CRITICAL PERCOLATION PROBABILITY LOCAL? 3 edges obtained from G by performing bond percolation with parameter p. If p < p (G), n c then for any constant α > 0 we have P G (p) contains a component of size at least α|G | → 0 as n→ ∞, (cid:16) n n (cid:17) and if p > p (G), then there exists some α > 0 such that c P G (p) contains a component of size at least α|G | → 1 as n→ ∞. (cid:16) n n (cid:17) For the reader’s convenience, we present the proof of Theorem 1.3 in Section 4. 1.1. Further discussion. Conjecture 1.2 suggests that the critical percolation prob- ability is locally determined. This contrasts with critical exponents which are believed to be universal and depend only on global properties of the graph. For instance, the value of p on the the two dimensional square lattice is 1, but on the two dimensional c 2 triangular lattice it is 2sin(π/18); however, the critical exponents are believed to be the same. It is worth noting another example of the locality of p where the limit graph is the c lattice Zd. For d> 1 and n> 1, write Zd for the d-dimensional torus with side n. The n following theorem is an immediate corollary of a theorem of Grimmett and Marstrand [8] combined with the fact that the critical probability of a quotient graph is always at least the critical probability of the original graph (see [4], [6] or [11]). Theorem 1.4 (Grimmett, Marstrand [8]). For any d > 1 and k satisfying 2 ≤ k < d we have p (Zk ×Zd−k)→ p (Zd) as n → ∞. c n c Observe that this is theorem is a special case of Conjecture 1.2. For background and further conjectures regarding percolation on infinite graphs see [4, 11]. 2. Uniform escape probability In this section we prove a useful lemma. Lemma 2.1. Consider a reversible irreducible Markov chain {X } on a countable t state space V, with infinite stationary measure π and transition matrix P, such that the bottom of the spectrum of I −P is λ > 0 (that is, (1.1) holds for any f ∈ ℓ2(π)). 1 Let A ⊂ V be a nonempty set of states with π(A) < ∞ and let π (·) = π(·)/π(A) be A the normalized restriction of π to A. Then P X never returns to A ≥ λ . πA(cid:16) t (cid:17) 1 4 ITAIBENJAMINI,ASAFNACHMIASANDYUVALPERES Proof. Let B ⊂ V be disjoint from A such that V \(A∪B) is finite. Define τ = min{t ≥ 0: X ∈ A∪B} and τ+ = min{t > 0: X ∈ A∪B}. t t The irreducibility assumption and the finiteness of the complement of A∪ B imply that τ+ <∞ a.s. for any starting state. We will show that for all sets B as above, P X ∈B ≥ λ . (2.1) πA(cid:0) τ+ (cid:1) 1 The assertion of the lemma then follows by enumerating V \A as v ,v ,v ,..., taking 1 2 3 B = B = {v : j ≥ k} and intersecting the events in (2.1) over all these sets B = B k j k for k ≥ 1. Let f(x)= P (X ∈ A). x τ Observe that f ≡ 1 on A and f ≡ 0 on B. For all x ∈G, (Pf)(x) = P X ∈A . x τ+ (cid:0) (cid:1) In particular, f is harmonic (satisfies Pf = f) on G\(A∪B). Thus ((I −P)f)(x) = P X ∈ B for x∈ A and ((I −P)f)(x) = 0 for x∈ G\(A∪B). Therefore x τ+ (cid:0) (cid:1) hf,(I −P)fi = π(x)P X ∈ B = π(A)P X ∈B . X x(cid:0) τ+ (cid:1) πA(cid:0) τ+ (cid:1) x∈A On the other hand, clearly, hf,fi≥ π(x)f(x)2 = π(A). X x∈A The claim (2.1) follows by inserting the last two formulas in (1.1). (cid:3) 3. Proof of Theorem 1.1 We return to the setting of Theorem 1.1. Let G be regular graph of degree d and girth g and write g := ⌈g/2⌉−1. Given a set of vertices A in G and α ∈ (0,1), we say that an edge (x,ue) is (α,A)-good if x ∈ A and at least an α fraction of the (d−1)eg non-backtracking paths of length g emanating from u, for which the first step is not x, avoid A (in particular, u 6∈ A.) eThe following lemma is a corollary of Lemma 2.1. Corollary 3.1. Let G be a regular graph with degree d and girth g. If G is nona- menable, i.e., it satisfies λ > 0, then for any finite set A ⊂ V(G), there exist at least 1 λ1d|A| edges (x,u) which are (λ /2,A)-good. 2 1 IS THE CRITICAL PERCOLATION PROBABILITY LOCAL? 5 Proof. For an edge (x,u) with x ∈ A, let β = P (X = u and ∀t > 0 X 6∈ A), (x,u) x 1 t where {X } is a SRW in G, started at x. Let τ := min{t : dist(u,X ) = g}. Since t t the ball B (u,g) is a spherically symmetric tree, the loop erasure of (X )τ e yields a G t t=0 uniform randome non-backtracking path of length g from u. Thus if β ≥ α, then (x,u) the edge (x,u) is (α,A)-good. By Lemma 2.1, e 1 β ≥ λ , d|A| X (x,u) 1 (x,u):x∈A and we conclude that at least λ1d|A| edges (x,u) with x ∈ A must satisfy β ≥ 2 (x,u) λ /2. (cid:3) 1 Proof of Theorem 1.1. Let ǫ > 0 be a small number and set p = 1 +ǫ. For each d−1 edge e we draw two independent Bernoulli random variables X (p) and Y (ǫ) with e e means p and ǫ respectively. We say that an edge is open if one of these variables takes the value 1 and closed otherwise. We also say that the edge e is p-open if X (p) = 1 e and ǫ-open if Y (ǫ) = 1. For a vertex v we write C(v) for the open cluster of v. e The probability that an edge is closed is (1−p)(1−ǫ), hence |C(v)| is dominated by the cluster size in (p + ǫ)-bond percolation. Our goal is to show that with positive probability |C(v)| = ∞. We perform the following exploration process, which will produce an increasing sequence {A } of connected vertex sets in which A ⊂ C(v) for all t. At each step, t t some of the edges touching A will beǫ-closed and some will beǫ-unchecked. We begin t by setting A to bethe p-cluster of v (that is, all the vertices connected to v by p-open 0 paths) and all the edges touching A are ǫ-unchecked. We assume that A is finite 0 0 (otherwise we are finished). At step t > 1 let E be the set of ǫ-unchecked edges t−1 (x,u) such that (x,u) is (λ /2,A )-good. If E is empty, the process ends. If not, 1 t−1 t−1 we choose (x,u) ∈ E according to some prescribed ordering of the edges and check t−1 whether the edge is ǫ-open. If it is ǫ-closed we put A = A and continue to the next t t−1 step of the process. Otherwise, we let A = A ∪V, t t−1 where V is the set of vertices v of distance at most g from u such that the unique path of length at most g between u and v avoids A aend is p-open. t−1 This finishes theedescription of the exploration process. To analyze this process we introduce the following random variable Z = e: e is an ǫ-closed and ǫ-checked edge touching A . t t (cid:12)(cid:8) (cid:9)(cid:12) (cid:12) (cid:12) 6 ITAIBENJAMINI,ASAFNACHMIASANDYUVALPERES Let τ be the stopping time 2t τ = min t :|A |< . n t o λ d 1 At each step we check the ǫ-status precisely one edge, hence Z ≤ t for all t. Thus, by t Corollary 3.1, if |A |> 2t there must exist at least one ǫ-unchecked edge (x,u) which t λ1d is (λ /2,A )-good. Write F for the σ-algebra generated by the ǫ and p status of the 1 t t edges we examined in the exploration process up to time t and let ξ = |A |−|A |. t t+1 t By the discussion above we have that ǫλ eg λ [(1+ǫ(d−1))eg −1] E[ξ |F ,τ > t] ≥ 1 (1+ǫ(d−1))j ≥ 1 . (3.1) t t−1 2 X 2(d−1) j=1 To see the first inequality in (3.1), recall that (x,u) is ǫ-open with probability ǫ. Also, for any j ≤ g the expected number of vertices of distance j from u such that the path between theem and u avoids A and is p-open is at least λ1(p(d−1))j = λ1(1+ǫ(d−1))j. t 2 2 We now assume that log 1+ 8 g ≥ (cid:0) λ21(cid:1) , (3.2) log(1+ǫ(d−1)) e sothatE[ξ |F ,τ > t]≥ 4d−1λ−1 by(3.1). Since|ξ | ≤ (d−1)eg, Azuma-Hoeffding’s t t−1 1 t inequality (see Chapter 7 of [3]) gives that for any t > 1 t 2t P τ = t+1 | A ≤ P ξ ≤ ≤ e−ct, (3.3) (cid:0) 0(cid:1) (cid:16)X i dλ (cid:17) 1 i=1 where c = 2λ−2d−2(d−1)−2eg > 0. Since |A | is a non-decreasing sequence we have 1 t that τ > λ1d|A0|. For any K > 0 there is some positive probability (depending on K) 2 of having |A |≥ K and we infer from (3.3) that 0 P(τ = ∞) ≥ P(|A |≥ K)P τ =∞ | |A | ≥ K 0 0 (cid:0) (cid:1) ≥ P(|A |≥ K) 1− e−ct > 0, 0 h X i t≥λ1dK 2 as long as we choose K = K(g,λ ,d) to be large enough. The event τ = ∞ implies 1 that |C(v)| = ∞, and hence, by (3.2) when ǫ ≥ C(dg)−1log 1+ 1 there is positive (cid:0) λ21(cid:1) probability of an infinite component in 1 +2ǫ -bond percolation (for ǫ ≤ (d−1)−1 (cid:0)d−1 (cid:1) one can take C = 128 using the inequalities log(1+8x)≤ 8log(1+x) and log(1+x)≥ x/2 valid for x∈ (0,1)). This concludes the proof of the theorem. (cid:3) IS THE CRITICAL PERCOLATION PROBABILITY LOCAL? 7 4. Proof of Theorem 1.3 Without loss of generality assume that |G | = n. We first take p < p (G) and fix n c α > 0. Since p < p (G), for any ǫ > 0 there exists R = R(ǫ) large enough such that in c G P ρ↔ ∂B(ρ,R) < ǫ. p (cid:0) (cid:1) Thus for large enough n we have in G n L×P U ↔ ∂B(U ,R) ≤ ǫ, p(cid:16) n n (cid:17) where L is the law of U . Since G has bounded degree, we deduce that for any ǫ > 0 n there exists n large enough such that L×P |C(U )| ≥ dR+1 ≤ ǫ. p(cid:16) n (cid:17) Write C (n) for the largest component of G (p) and note that as long as dR+1 ≤ αn 1 n we have that L×P |C(U )| ≥ dR+1 ≥ αP |C (n)| ≥ αn , p(cid:16) n (cid:17) p 1 (cid:0) (cid:1) and we get that P |C (n)| ≥ αn ≤ǫα−1, p 1 (cid:0) (cid:1) which proves the first assertion of the theorem. Toprove thesecond assertion of thetheorem weuseasprinklingargument, as in [1]. Assumep > p (G)andforsomeǫ > 0letp = p (G)+ǫsuchthat1−p = (1−p )(1−ǫ). c 1 c 1 We first consider G (p ). Since p > p (G), there exists some δ > 0 such that for all n 1 1 c R > 0 we have P ρ↔ ∂B(ρ,R) ≥ δ. p1(cid:0) (cid:1) For v ∈ G , write B (v,R) for the set of vertices in G (p ) which are connected to v n p1 n 1 in a p -open path of length at most R. We get that for any R > 0 there exists n such 1 0 that for n ≥ n we have in G 0 L×P |B (U ,R)| ≥ R ≥ δ/2. (cid:16) p1 n (cid:17) Let X denote the random variable R X = v ∈ G : |B (v,R)| ≥ R , R (cid:12)n n p1 o(cid:12) (cid:12) (cid:12) (cid:12) (cid:12) 8 ITAIBENJAMINI,ASAFNACHMIASANDYUVALPERES so that EX ≥ δn/2. On the other hand, note that changing the status of a single R edge can change X by at most dR, where d is the degree bound of G . The method R n of bounded differences (see Theorem 3.1 of [12] or Chapter 7 of [3]) gives that δn δ2n P X ≤ ≤ exp − . (4.1) (cid:16) R 4 (cid:17) (cid:0) 8d2R(cid:1) Assume now that X ≥ δn/4 and consider the connected components of G (p ) of R n 1 size at least R. Their number m is at most n/R. We now consider the union of G (p ) n 1 with G (ǫ) and claim that many of these components join together by edges of G (ǫ) n n and create a component of linear size. Indeed, consider a partitition of the m large components of G (p )into two sets, AandB, each spanningat least δn/12 vertices. If n 1 for any such partition there is an open path in G (ǫ) connecting A and B, then there n exists a component of size at least δn/12 in G (p )∪ G (ǫ). Since G has Cheeger n 1 n n constant at least h> 0 we get by Menger’s Theorem that for any such A and B there are at least hδn/12 edge disjoint paths connecting A to B. Since there are most dn/2 edges in G we have that at least a half of these paths must be of length at most 12d. n hδ The probability that all these paths are closed in G (ǫ) is at most n hδn 12d 24 h1−ǫhδ i . There are at most 2m different possibilities for choosing A and B. Hence, the proba- bility that there exists such A and B is at most hδn 2mh1−ǫ1h2δdi 24 ≤ exp(cid:16)n/R−ǫ1h2δdhδn/24(cid:17), which goes to 0 as long as R is chosen such that R−1 < ǫ1h2δdhδ. This together with (4.1) shows that δn P G (p) contains a component of size at least → 1 as n→ ∞. (cid:16) n (cid:17) 12 (cid:3) Acknowledgements: We are indebted to Mark Sapir and Oded Schramm for useful discussions. References [1] N.Alon,I.BenjaminiandA.Stacey,Percolationonfinitegraphsandisoperimetricinequalities Ann. Probab. 32 (2004), 1727–1745. [2] A.Akhmedov,ThegirthofgroupssatisfyingTitsAlternative,J. of Algebra, 287(2005), no.2, 275-282. IS THE CRITICAL PERCOLATION PROBABILITY LOCAL? 9 [3] N.Alon and J. H.Spencer, Theprobabilistic method,2nd edition, Wiley, New York,2000. [4] I. Benjamini and O. Schramm, Percolation Beyond Zd, Many Questions And a Few Answers, ECP, 1(1996), Paper no. 8. [5] I. Benjamini and O. Schramm, Recurrence of Distributional Limits of Finite Planar Graphs, Electron. J. Probab. Vol. 6, no. 23, 13 pp. [6] M.Campanino, Inequalitiesforcritical probabilities inpercolation, Particle Systems, Random Media and Large Deviations, volume 41 of Contemp. Math., pages 1-9, R. Durrett editor. Amer.Math.Soc., Providence,RI.Proceedings oftheAMSIMS-SIAMjoint summerresearch conference in themathematical sciences on mathematics of phase transitions held at Bowdoin College, Brunswick, Maine, June 24-30, (1984). [7] J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc., 284, 787-794. [8] G. R. Grimmett and J. M. Marstrand, The supercritical phase of percolation is well behaved, Proc. Roy. Soc. London Ser. A 430 (1990), no. 1879, 439–457. [9] H.Kesten, Full Banach mean valueson countable groups, Math. Scand., 7, 146-156. [10] H.Kesten, Symmetricrandom walks on groups, Trans. Amer. Math. Soc., 92, 336-354. [11] R. Lyons with Y. Peres, Probability on Trees and Networks, In preparation, http://mypage.iu.edu/∼rdlyons/prbtree/prbtree.html [12] C. McDiarmid, Concentration. Probabilistic methods for algorithmic discrete mathematics, 195–248, Algorithms Combin., 16, Springer, Berlin, (1998). [13] A. Yu. Olshanskii and M. V. Sapir, On k-free-like groups, preprint. Available at http://arxiv.org/abs/0811.1607 [14] W. Woess, Random walks on infinite graphs and groups, Cambridge Tracts in Mathematics, 138, Cambridge University Press, Cambridge. Itai Benjamini: itai.benjamini(at)weizmann.ac.il The Weizmann Institute of Science, Rehovot POB 76100, Israel. Asaf Nachmias: asafn(at)microsoft.com Microsoft Research, One Microsoft way, Redmond, WA 98052-6399, USA. Yuval Peres: peres(at)microsoft.com Microsoft Research, One Microsoft way, Redmond, WA 98052-6399, USA.