loading

Logout succeed

Logout succeed. See you again!

ebook img

Is the critical percolation probability local? PDF

file size0.14 MB
languageEnglish

Preview Is the critical percolation probability local?

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.

See more

The list of books you might like