Concentration estimates for the isoperimetric constant of the supercritical percolation cluster

ISSN:1083-589X in PROBABILITY

Concentration estimates for the isoperimetric constant of the supercritical percolation cluster

Eviatar B. Procaccia

Ron Rosenthal

Abstract

We consider the Cheeger constantφ(n)of the giant component of supercritical bond percolation onZ^d/nZ^d. We show that the variance ofφ(n)is bounded by _n^ξd, where ξ is a positive constant that depends only on the dimension d and the percolation parameter.

Keywords:Isoperimetric constant ; Percolation, concentration.

AMS MSC 2010:60K35;82B43.

Submitted to ECP on January 12, 2012, final version accepted on July 19, 2012.

SupersedesarXiv:1110.6006v2.

1 Introduction

Let T^d(n) be thed dimensional torus with side lengthn, i.e. Z^d/nZ^d, and denote by E^d(n) the set of edges of the graph T^d(n). Let pc(Z^d) denote the critical value for bond percolation onZ^d, and fix somepc(Z^d)< p≤1. We apply a p-bond Bernoulli percolation process on the torusT^d(n)and denote byCd(n)the largest open component of the percolated graph (In case of two or more identically sized largest components, choose one by some arbitrary but fixed method). LetΩ = Ω_n ={0,1}^Ed(n)be the space of configurations for the percolation process and denote by P = P_p the probability measure associated with the percolation process. For a subsetA⊂Cd(n)(ω)we denote by∂_Cd(n)Athe boundary of the setAinCd(n), i.e. the set of edges(x, y)∈E^d(n)such that ω((x, y)) = 1 and with eitherx∈ A and y /∈ A orx /∈ A and y ∈ A. Throughout this paper c, C and c_i for i ∈ N denote positive constants which may depend on the dimensiondand the percolation parameterpbut not onn. The value of the constants may change from one line to the next.

Next we define the Cheeger constant

Definition 1.1. For a set∅ 6=A⊂C_d(n), we denote ψA=|∂C_d(n)A|

|A| .

where| · |denotes the cardinality of a set. The Cheeger constant ofC_d(n)is defined by:

φ=φ(n) := min

∅6=A⊂Cd(n)

|A|≤|Cd(n)|/2

ψA.

∗Weizmann Institute of Science. E-mail:[email protected]

†Hebrew University of Jerusalem. E-mail:[email protected]

In [5] Benjamini and Mossel studied the robustness of the mixing time and Cheeger constant ofZ^d under a percolation perturbation. They showed that forp_c(Z^d)< p <1 large enough nφ(n)is bounded between two constants with high probability. In [7], Mathieu and Remy improved the result and proved the following on the Cheeger con- stant

Theorem 1.2. For everyp > p_c(Z^d), there exist constantsc₂(p), c₃(p), c(p)>0such that for everyn∈N

Pc2

n ≤φ(n)≤c3

n

≥1−e^−clog

3 2n.

Recently, Marek Biskup and Gábor Pete brought to our attention that better bounds on the Cheeger constant exist in both [8] and [3]. The following theorem is stated in [8] Corollary 1.4 without asymptotic rate, however going over the proof one obtains the following statement:

Theorem 1.3. [8] Ford≥2and p > p_c(Z^d)and for every C >0, there are constants α(d, p)>0andβ(d, p)>0such that

P ∀S⊂ Cd(n)connected, ifCn≤ |S|<^|Cd₂^(n)| then ^|∂CS|

|S|^(d−1)/d ≥α

!

≥1−exp

−βn^(d−1)/d .

Our result can be obtained with the use of [7] however we use Theorem 1.3 as it simplifies the proofs.

In 2011 Itai Benjamini gave the following conjecture as an extension to the known results about the Cheeger constant:

Conjecture 1.4. The limitlimn→∞nφ(n)exists.

Even though the last conjecture is still open, and the expectation of the Cheeger con- stant is quite evasive, we managed to give a good bound on the variance of the Cheeger constant. This is given in the main Theorem of this paper (The proof is presented in page9):

Theorem 1.5. There exists a constantξ=ξ(p, d)>0such that

Var(φ)≤ ξ n^d.

A major ingredient of the proof is Talagrand’s inequality for concentration of mea- sure on product spaces. Talagrand’s inequality requires control over the influence of a single edge on the Cheeger constant. Such a bound can be achieved using results on the isoperimetric profile of the giant component and the fact that with high probability edges outside the giant component have little effect over the Cheeger constant. This inequality is used by Benjamini, Kalai and Schramm in [4] to prove concentration of first passage percolation distance. A related study that uses another inequality by Talagrand is [1], where Alon, Krivelevich and Vu prove a concentration result for eigenvalues of random symmetric matrices.

2 The Cheeger constant

Before turning to the proof of Theorem 1.5, we give the following definitions:

Definition 2.1. For a functionf : Ω→Rand an edgee∈E^d(n)we define∇ef : Ω→R by

∇ef(ω) =f(ω)−f(ω^e)

where

ω^e(e⁰) =

(ω(e⁰) e⁰6=e 1−ω(e⁰) e⁰=e.

In addition, for a configurationω ∈Ωand an edgee∈ E^d(n), let ωˆ^e = min{ω, ω^e} and ˇ

ω^e= max{ω, ω^e}.

Definition 2.2. Forn∈Nwe define the following events:

H_n¹(c1) =

ω∈Ω : |Cd(n)(ω)|> c1n^d H_n²(c₂, c₃) =n

ω∈Ω : c₂

n < φ(n)(ω)<c₃ n o

H_n³=

ω∈Ω : ∀e∈E^d(n) |Cd(n)(ω)4Cd(n)(ω^e)| ≤√ n H_n⁴(c4) ={ω∈Ω : ∃A:|A|> c4n^d, ψA(ω) =φ(n)(ω)}

H_n⁵(c5) ={ω∈Ω :∀e∈E^d(n)∃A:|A|> c5n^d, ψA(ω^e) =φ(n)(ω^e)}

, (2.1)

and

H_n=H_n(c₁, c₂, c₃, c₄, c₅) =H_n¹(c₁)∩H_n²(c₂, c₃)∩H_n³∩H_n⁴(c₄)∩H_n⁵(c₅). (2.2) We start with the following deterministic claim:

Claim 2.3.Givenc₁, c₂, c₃, c₄, c₅>0, there exists a constantC=C(c₁, c₂, c₃, c₄, c₅, d, p)>

0such that ifω∈Hn(c1, c2, c3, c4, c5)then for everye∈E^d(n)

|∇eφ(ω)| ≤ C n^d.

In order to prove Claim 2.3 we will need the following two lemmas:

Lemma 2.4. Fix a configurationω∈Ωand an edgee∈E^d(n). LetA⊂Cd(n)(ˆω^e)be a subset such that|A|=αn^d. Then

|∇eψA| ≤ 1 αn^d.

Proof. SinceAis a subset ofCd(n)(ˆω^e)it follows thatA is also contained inCd(n)(ˇω^e) and the size of∂_Cd(n)Ais changed by at most1by adding an edgee. It therefore follows that

|∇eψ(A)|=|ψA(ω)−ψA(ω^e)|=|ψA(ˆω^e)−ψA(ˇω^e)|

≤

|∂A|

|A| −|∂A|+ 1

|A|

= 1

|A|. ^(2.3)

Lemma 2.5. LetGbe a finite graph, and letA, B⊂Gbe disjoint such that there exists a unique edgee= (x, y), such thatx∈Aandy∈B, then

ψA∪B≥min{ψA, ψB} − 2

|A|+|B|. Proof. From the assumptions onAandBit follows that

ψ_A∪B= |∂(A∪B)|

|A∪B| = |∂A|+|∂B| −2

|A|+|B| ≥min |∂A|

|A| ,|∂B|

|B|

− 2

|A|+|B|, (2.4) and so the lemma follows.

Proof of Claim 2.3. We separate the proof into six different cases according to the fol- lowing table:

e= (x, y) ω(e) = 0 (ω= ˆω^e)

ω(e) = 1 (ω= ˇω^e)

x, y /∈C_d(n) 1 2

x, y∈Cd(n) 3 4

x∈C_d(n), y /∈C_d(n) or

y∈Cd(n), x /∈Cd(n)

5 6

• Cases 1 and 2: In those cases the setC_d(n)and the edges available from it are the same for both configurationsω and ω^e. It therefore follows that∇_eφ(ω) = 0. See Figure 1a, and 1b.

• Case 3: In this case the setCd(n)is the same for both configurationsω and ω^e, however the set of edges available inC_d(n)is increased by one when moving to the configurationω^e, see figure 1c. Fix a setA⊂C_d(n)(ω)of size bigger thanc₄n^d which realizes the Cheeger constant. It follows that

ψA(ω) =φ(ω)≤φ(ω^e)≤ψA(ω^e), and therefore by Lemma 2.4 we have

|φ(ω^e)−φ(ω)| ≤ψA(ω^e)−ψA(ω)≤ 1 c4n^d, as required.

• Case 4: We separate this case into two subcases according to wether the set C_d(n)(ω)\C_d(n)(ω^e)is an empty set or not. IfC_d(n)(ω)\C_d(n)(ω^e) =∅then we are in the same situation as inCase 3, see Figure 1d, and so the same argument gives the desired result. So, let us assume thatCd(n)(ω)\Cd(n)(ω^e)6=∅, see Figure 1e.

Sinceω∈H_n³, we know that

|Cd(n)(ω)\Cd(n)(ω^e)| ≤√

n, (2.5)

and sinceω ∈H_n¹, C_d(n)(ω)andC_d(n)(ω^e)are not disjoint. Sinceω ∈H_n⁴, there exists a set A ⊂ Cd(n)(ω) of size bigger than c4n^d realizing the Cheeger con- stant in the configuration ω. We denote A1 = A∩ Cd(n)(ω^e) and A2 = A∩ (Cd(n)(ω)\Cd(n)(ω^e)). Applying Lemma 2.5 toA1andA2we see that

ψA(ω) =ψA₁∪A₂(ω)≥min{ψA₁(ω), ψA₂(ω)} − 2

|A|. (2.6)

From (2.5) it follows that |A2| ≤ √

nand therefore ψA₂(ω)≥ ^√1_n which gives us thatmin{ψA1(ω), ψA2(ω)}=ψA1(ω). Indeed, if the last equality doesn’t hold then

c₂

n ≥ψ_A(ω)≥ψ_A2(ω)− 2

|A| ≥ 1

√n− 2 c4n^d,

which for large enoughnyields a contradiction. Consequently from (2.6) we get that

ψ_A1(ω)− 2

c4n^d ≤φ(ω)≤ψ_A1(ω), and so

φ(ω^e)− 2

c4n^d ≤ψA₁(ω^e)− 2

c4n^d ≤ψA₁(ω)− 2

c4n^d ≤φ(ω),

(a) Case 1 (b) Case 2

e

(c) Case 3

e

(d) Case 4a

(e) Case 4b

e

(f) Case 5

Figure 1: Illustrations of the different cases

i.e.φ(ω^e)−φ(ω)≤_c²

4n^d.

For the other direction, since ω ∈ H_n⁵, there exists a set B ⊂ Cd(n)(ω^e) of size bigger thanc₅n^drealizing the Cheeger constant inω^e, then

φ(ω)≤ψ_B(ω)≤ψ_B(ω^e) + 1

|B| =φ(ω^e) + 1

|B| ≤φ(ω^e) + 1 c₅n^d.

Consequently,

|φ(ω)−φ(ω^e)| ≤max 2

c4n^d, 1 c5n^d

,

as required.

• Case 5: The proof of this case follows the proof ofcase 4above, see Figure 1f.

• Case 6: This case is impossible by the definition of the setCd(n)(ω).

Next we turn to estimate the probability of the eventHn.

Claim 2.6. There exist constantsc₁, c₂, c₃, c₄, c₅>0and a constantc >0such that for large enoughn∈N^{we have}

P(H_n^c)≤e^−clog

3

2n. ^(2.7)

Proof. Since P(H_n^c)≤P5

i=1 P((H_nⁱ)^c), it’s enough to bound each of the last probabili- ties separately. The proof of the exponential decay of P((H_n¹)^c)for appropriate constant is presented in the Appendix.

By [7] Theorem 3.1 and section 3.4, there exists a constant c > 0 such that for n large enough, P((H_n²)^c)≤e^−clog3/2nfor some constantsc₂, c₃>0.

Turning to bound P((H_n³)^c), we notice that the setCd(n)(ω)4Cd(n)(ω^e)is indepen- dent of the status of the edgeeand therefore

P((H_n³)^c) = 1 1−p ^P

ω∈Ω : ∃e∈E^d(n) |Cd(n)(ω)4Cd(n)(ω^e)| ≥√

n , eis closed

≤ 1 1−p ^P

ω∈Ω : ∃e∈E^d(n) |Cd(n)(ω)4Cd(n)(ω^e)| ≥√

n , eis closed ∩H_n¹

+ 1

1−p^P((H_n¹)^c).

(2.8) We already gave appropriate bound for the last term and therefore we are left to bound the probability of{ω∈Ω : ∃e∈Ed(n) |Cd(n)(ω)4Cd(n)(ω^e)| ≥√

n , eis closed} ∩H_n¹. Notice that the occurrence of this event implies the existence of an open cluster of size bigger than√

nwhich is not connected toCd(n). An appropriate bound for this event can be found in Lemma 3.2.

In order to deal with the event(H_n⁴)^cwe denoteG_nthe event in Theorem 1.3, Gn=

∀S ⊂ Cd(n)connected :Cn≤ |S|< |Cd(n)|

2 , |∂CS|

|S|^(d−1)/d ≥α

.

By [8] there exists a constantβ >0such that P(G^c_n)< e^−βn(^d−1d )

for large enough n∈N. As before we write

P((H_n⁴)^c)≤ P((H_n⁴)^c∩H_n¹∩H_n²∩G_n) + P((H_n¹)^c∪(H_n²)^c∪G^c_n),

and by the probability bound mentioned so far it’s enough to bound the probability of the first event(H_n⁴)^c∩H_n¹∩H_n²∩Gn. What we will actually show is that for appropriate

choice of0< c₄< ¹₂ we have(H_n⁴)^c∩H_n¹∩H_n²∩G_n =∅. Indeed, since we assumed the eventG_n occurs we have that for large enoughn ∈ Nand every setA ⊂C_d(n)(ω)of size smaller thanc4n^d,

|∂_Cd(n)A| ≥α|A|^d−1d . It follows that

ψA≥α 1

|A|^1/d ≥ α c^1/d₄ n

. _(2.9)

Choosingc4 >0 such that for large enoughn∈N^{we have} _c1/d^α 4

> c3, we get a contra- diction to the event H_n², which proves that the event (H_n⁴)^c∩H_n¹∩H_n²∩Gn is indeed empty.

Finally we turn to deal with the event (H_n⁵)^c. As before it’s enough to bound the probability of the event(H_n⁵)^c∩H_n¹∩H_n²∩H_n³∩H_n⁴∩Gn. We divide the last event into two disjoint events according to the status of the edgee, namely

V_n⁰: = (H_n⁵)^c∩H_n¹∩H_n²∩H_n³∩H_n⁴∩Gn∩ {ω(e) = 0}

V_n¹: = (H_n⁵)^c∩H_n¹∩H_n²∩H_n³∩H_n⁴∩G_n∩ {ω(e) = 1}, ^(2.10) and will show that for right choice ofc5>0bothV_n⁰andV_n¹are empty events.

Let us start withV_n⁰. Going back to the proof of Claim 2.3 one can see that under the eventH_n¹∩H_n²∩H_n³∩H_n⁴there exists a constantc >0such that

φ(ω^e)≤φ(ω) + c n^d ≤ c₃

n + c

n^d, (2.11)

and thereforeφ(ω^e)≤ ^c˜_n³ for anyc˜3> c3andn∈Nlarge enough. If∅ 6=A⊂Cd(n)(ω^e) is a set of size smaller than _˜cⁿ

3 then

ψ_A(ω^e)≥ 1

|A| > ˜c3

n, (2.12)

and therefore A cannot realize the Cheeger constant. On the other hand, if A ⊂ Cd(n)(ω^e)satisfy _c˜ⁿ

3 ≤ |A| ≤c5n^dthen

|∂_Cd(n)(ωe)A| ≥ |∂_Cd(n)(ωe)(A∩C_d(n)(ω))| −1≥ |∂_Cd(n)(ω)(A∩C_d(n)(ω)| −2, and therefore (Since we assumed the eventG_n occurs)

ψA(ω^e)≥|∂_Cd(n)(ω)(A∩Cd(n)(ω))|

|A| − 2

|A|

=|∂_Cd(n)(ω)(A∩Cd(n)(ω))|

|A∩Cd(n)(ω)|

|A∩C_d(n)(ω)|

|A| − 2

|A|

≥ α

|A∩Cd(n)(ω)|^1d · |A| −√ n

|A| −2˜c₃ n

≥ α 2c₅^1dn

−2˜c₃ n ,

(2.13)

where the last inequality holds for large enoughn, since lim_n→∞^|A|−

√n

|A| = 1. Taking c5>0small enough such that ^α

2c

1 d 5

−2˜c3> c3we get a contradiction to (2.11). It follows that no set A ⊂ Cd(n)(ω^e)of size smaller than c5n^d can realize the Cheeger constant which contradicts(H_n⁵)^c, i.e,V_n⁰=∅.

Finally, for V_n¹. The caseA ⊂C_d(n)(ω^e)such that|A| < _˜cⁿ

3 is the same as for the eventV_n⁰. IfA⊂C_d(n)(ω^e)satisfy _c˜ⁿ

3 ≤ |A| ≤c₅n^dthen

|∂_Cd(n)(ωe)A| ≥ |∂_Cd(n)(ω)A| −1.

and therefore as in the case ofV_n⁰

ψ_A(ω^e)≥|∂_Cd(n)(ω)A| −1

|A|

≥α|A|^d−1d

|A| − 1

|A| ≥ c6

2c^1/d₅ n

−˜c3

n,

(2.14)

where again the last inequality holds only for large enoughn. Choosingc5small enough, we again get a contradiction to (2.11), and as before this yields thatV_n¹=∅.

Proof of theorem 1.5. By [10] (Theorem 1.5) the following inequality holds for some K=K(p),

Var(φ)≤K· X

e∈Ed(n)

k∇eφk²₂

1 + log (k∇eφk2/k∇eφk1), _(2.15) wherek∇eφk²₂=E[(∇eφ)²]andk∇eφk1=E[|∇eφ|]. Observe that

k∇eφk1=k∇eφ1{∇eφ6=0}k1≤ k∇eφk2k1{∇eφ6=0}k2, and therefore

k∇eφk2

k∇_eφk₁ ≥ 1

pP(∇eφ6= 0) ≥1.

Consequently, if we fix some edgee0∈E^d(n), Var(φ)≤K X

e∈Ed(n)

k∇_eφk²₂=K|Ed(n)| · k∇_e0φk²₂=Kdn^d· k∇_e0φk²₂, _(2.16)

where the first equality follows from the symmetry ofTd(n).

k∇e₀φk²₂=E[|∇e₀φ|²1^Hn] +E[|∇e₀φ|²1^Hn^c]. (2.17) Notice that since|∇e₀φ| ≤2dwe haveE[|∇e₀φ|²1^Hc_n]≤4d²P(H_n^c). Thus applying Lemma 2.6,

E[|∇e₀φ|²1^Hn^c]≤4d²e^−clog

3

2(n), ^(2.18)

and by Lemma 2.3

E[|∇e₀φ|²1^Hn]≤ C²

n^2d. ^(2.19)

Thus combing equations (2.18) and (2.19) with equation (2.16) the result follows.

3 Appendix

In this Appendix for completeness and future reference, we sketch a proof of the exponential decay of P((H_n¹)^c)and the decay of probability for the size of the second largest component of percolation in a box.

The proof of the first estimate follows directly from two papers [6] by Deuschel and Pisztora and [2] by Antal Pisztora, which together gives a proof by a renormalization argument. We borrow the terminology of [2] without giving here the definitions.

Lemma 3.1. Letp > p_c(Z^d). There existc₁, c >0such that fornlarge enough Pp(|Cd(n)(ω)|< c1n^d)< e^−cn.

Proof. By [6] Theorem 1.2, for every >0there exists ap_c(Z^d)< p^∗ <1such that for everyp > p^∗there exists a constantc >0for whom, P_p(|C_d(n)(ω)|<(1−)n^d)< e^−cn. Since{|Cd(n)(ω)| <˜c1n^d}^c is an increasing event, by Proposition 2.1 of [2] for N ∈ N large enough, i.e., such thatp(N¯ )> p^∗,

P^N(|Cd(n)(ω)|<˜c1n^d)≤P^∗p(N)¯ (|Cd(n)(ω)|<˜c1n^d)< e^−cn, (3.1) whereP^Nis the probability measure of the renormalized dependent percolation process andP^∗p(N¯ )is the probability measure of standard bond percolation with parameterp(N¯ ). From the definition of the eventR^(N)_i , the crossing clusters of all the boxesB⁰_ithat admit R^(N_i ⁾are connected to each other, thus

P_p |C_d(nN)(ω)|<c˜₁(nN)^d

< e^−cn.

Next, for completeness, we turn to prove that all components outside the giant one are small.

Lemma 3.2. Let p > pc(Z^d) and denote by K ⊂ T^d(n)\Cd(n) the largest connected component of the graphT^d(n)\Cd(n). Then there exist constantsc, C >0such that

Pp |K|> C√ n

≤e^−cn

14

.

Proof. We separate the proof into two parts: First, following ideas from Section 4 of [9], we prove the theorem forpc(Z)< p <1 close enough to one. Secondly, we use a renormalization argument to show that the argument for large enoughpcan be used to prove the lemma for anypc(Z^d)< p <1in the cost of changing the value of the constant c.

Since there existsc >0such that ]

∗-connected edge sets of sizekinT^d(n) ≤n^d·c^k, we get by a union bound that¹

Pp

∃A⊂E^d(n) : Ais ∗- connected, |A|> n¹⁴ , ∀e∈A , ω(e) = 0

≤

∞

X

k=bn¹4c

n^d·c^k(1−p)^k.

Ifp^∗ < p <1, where p^∗ solve the equationc(1−p) = 1, we get that there exists some constantc=c(p)>0such that

Pp

∃A⊂E^d(n) : Ais ∗- connected, |A|> n¹⁴ , ∀e∈A , ω(e) = 0

≤e^−cn

1 4.

Using the proof of Lemma 3.1 for large values ofpwe see in the cost of increasing the value ofp^∗we can ensure that for everyp^∗< p <1there existsc >˜ 0such that for large enoughn∈N^{we have Pp} |K| ≥ |T^d(n)|/2

≤e^−˜cn. Thus we only need to deal with the

1The choice ofn¹⁴ is arbitrary and the only requirement it islog(n)and smaller than√ n.

case√

n <|K|<|T^d(n)|/2. If√

n <|K|<|T^d(n)|/2, by the isoperimetric inequality for T^d(n)there exists someδ > 0 such that|∂K| ≥ δ|K|^d−1d ≥δ|K|¹² ≥ δn¹⁴. SinceK is a maximal connected set inT^d(n)\Cd(n)we get thatω(e) = 0for everye∈∂K. Recalling that∂Kis∗-connected (see [6] Lemma 2.1 or [11]) we can conclude that

Pp

√n <|K|<|T^d(n)|/2

≤ Pp

|∂K| ≥δn¹⁴ , ∂Kis ∗- connected,

∀e∈∂K, ω(e) = 0

≤e^−cn

14

Next we turn to the renormalization argument. Notice that the by the definition of Kwhich ignores the percolation structure outside ofT^d(n)\Cd(n)we have that{|K|>

√

N}is a decreasing event. By Proposition 2.1 of [2] forN ∈Nlarge enough, i.e., such thatp(N¯ )> p^∗, we have

PN(|K|>√

n)≤P^∗p(N¯ )(|K|>√

n)< e^−cn

1

4, ^(3.2)

whereP^Nis the probability measure of the renormalized dependent percolation process andP^∗p(N¯ )is the probability measure of standard bond percolation with parameterp(N¯ ). Assume thatK ⊂ T^d(n)\C_d(n)is a connected component under the law of P_p. By the definition of good boxesKN contain a cluster that is contained inCd(n)under Pp and this cluster intersect every connected set of size N/10 (see [2]) thus there exists a connected componentKN ⊂T^d(n)\Cd(n)under the law ofP^{N such that}

K ⊂ [

x∈KN∪∂KN

B(x, N),

where B(x, N) is the box of size N centered around x. Consequently we have the following estimate for the size ofK

|K| ≤N^d(|K_N|+|∂K_N|)≤(2d+ 1)N^d|K_N|. (3.3) Thus, using (3.3) and (3.2) we get that

P_p |K| ≥√ n

≤PN |K_N| ≥

pn/N (2d+ 1)N^d

!

≤P^∗p(N)

|KN| ≥

√n (2d+ 1)N^(d+12)

≤e

− ^c

((2d+1)N(d+ 12) )

1 4

n¹4

,

(3.4)

as required.

References

[1] N. Alon, M. Krivelevich, and V.H. Vu. On the concentration of eigenvalues of random sym- metric matrices.Israel Journal of Mathematics, 131(1):259–267, 2002. MR-1942311 [2] P. Antal and A. Pisztora. On the chemical distance for supercritical Bernoulli percolation.

The Annals of Probability, 24:1036–1048, 1996. MR-1404543

[3] N. Berger, M. Biskup, C.E. Hoffman, and G. Kozma. Anomalous heat-kernel decay for random walk among bounded random conductances. 44(2):374–392, 2008. MR-2446329

[4] I. Benjamini, G. Kalai, and O. Schramm. First passage percolation has sublinear distance variance.Annals of Probability, 31(4):1970–1978, 2003. MR-2016607

[5] I. Benjamini and E. Mossel. On the mixing time of a simple random walk on the super critical percolation cluster. Probability Theory and Related Fields, 125(3):408–420, 2003.

MR-1967022

[6] J.D. Deuschel and A. Pisztora. Surface order large deviations for high-density percolation.

Probability Theory and Related Fields, 104(4):467–482, 1996. MR-1384041

[7] P. Mathieu and E. Remy. Isoperimetry and heat kernel decay on percolation clusters. The Annals of Probability, 32(1):100–128, 2004. MR-2040777

[8] Gabor Pete. A note on percolation onz^d: isoperimetric profile via exponential cluster repul- sion.Electron. Commun. Probab., 13:no. 37, 377–392, 2008. MR-2415145

[9] E.B. Procaccia and E. Shellef. On the range of a random walk in a torus and random inter- lacements. Arxiv preprint arXiv:1007.1401, 2010.

[10] M. Talagrand. On Russo’s approximate zero-one law. The Annals of Probability, 22:1576–

1587, 1994. MR-1303654

[11] A. Timar. Bondary-connectivity via graph theory.To appear in Proceedings of the American Mathematical Scociety, 2007.

Acknowledgments.The authors would like to thank Itai Benjamini for suggesting the problem. We would also like to thank the detailed comments of an anonymous referee.

The research of R.R was partially supported by ERC StG Number 239990