betaFeedback

WorksMathematics

Anchored isoperimetry in percolation

Abstract

We show that, for any infinite transitive graph GG, the infinite cluster after supercritical percolation almost surely inherits the anchored isoperimetry of GG. Moreover, the probability of violating the corresponding isoperimetric inequality decays exponentially in the isoperimetric profile of the host graph. This was previously known only for nonamenable transitive graphs, Zd\mathbb{Z}^d, and very recently for transitive graphs of polynomial growth. Our proof combines the thinning-and-sprinkling technique with a novel counting algorithm.

Introduction

Percolation provides a natural way to probe the geometry of an infinite graph GG: randomly delete its edges and ask which structural properties survive. In the supercritical regime, the resulting random graph contains infinite connected components. A fundamental question is to what extent these clusters retain the large-scale geometric properties of the original graph. One particularly important aspect of this question is isoperimetry, which measures how the boundary of a vertex set grows with its size.

More precisely, let G=(V,E)G = (V, E) be an infinite, connected, locally finite, vertex-transitive graph of degree dd. In Bernoulli bond percolation, each edge of GG is retained independently with probability p∈[0,1]p \in[0, 1]. This produces a random subgraph GpG_p with distribution Pp\mathbb{P}_p, whose connected components are called clusters. The critical probability is defined as

pc=pc(G):=inf⁡{p∈[0,1]:Gp contains an infinite cluster almost surely}.p_c = p_c(G) := \inf\{p \in[0,1]: G_p \text{ contains an infinite cluster almost surely}\}.

The regimes p<pcp < p_c and p>pcp > p_c are called subcritical and supercritical, respectively. Percolation was introduced in 1957 by Broadbent and Hammersley [2], and was initially studied mainly on the hypercubic lattice Zd\mathbb{Z}^d. An important step towards a more general understanding was made by Benjamini and Schramm [4], who initiated the systematic study of percolation on arbitrary infinite transitive graphs in 1996.

An important quantitative measure of the global geometry of a graph is its isoperimetric profile. For a finite set S⊆VS \subseteq V, let ∂GS\partial_G S denote the set of edges of GG with exactly one endpoint in SS. The isoperimetric profile of GG is defined by

ΦG(n):=inf⁡{∣∂GW∣:W⊆V, n≤∣W∣<∞}.\Phi_G(n) := \inf\{|\partial_G W|: W \subseteq V,\ n \le|W| < \infty\}.

For example, ΦG(n)=Θ(n)\Phi_G(n) = \Theta(n) when GG is nonamenable, whereas ΦZd(n)=Θ(n(d−1)/d)\Phi_{\mathbb{Z}^d}(n) = \Theta(n^{(d-1)/d}) for d≥2d \ge2. In the study of percolation, one might naturally hope that infinite supercritical clusters inherit the isoperimetric profile of GG, up to multiplicative constants. However, such inequalities cannot hold uniformly over all finite subsets of a cluster. Indeed, when p∈(pc,1)p \in(p_c,1), infinite clusters contain arbitrarily long bare paths, and taking a long subpath of their internal vertices yields a large connected set with only two boundary edges (see, e.g., [11, 13]). The natural way to overcome this difficulty is to consider an anchored version of isoperimetry, where we restrict attention to connected sets containing a fixed vertex. Given an infinite connected graph HH and a vertex o∈V(H)o \in V(H), its anchored isoperimetric profile is defined by

ΦH,o(n):=inf⁡{∣∂HW∣:o∈W⊆V(H), W is connected, n≤∣W∣<∞}.\Phi_{H,o}(n) := \inf\{|\partial_H W| : o \in W \subseteq V(H),\ W\text{ is connected},\ n \le|W| < \infty\}.

Let CoC_o denote the cluster containing oo in GpG_p. When p>pcp > p_c and CoC_o is infinite, it is natural to ask whether its anchored isoperimetric profile is comparable to that of GG. More precisely, for infinite connected graphs H⊆GH \subseteq G containing oo, we say that HH has anchored isoperimetry with respect to GG if

lim inf⁡n→∞ΦH,o(n)ΦG(n)>0.\liminf_{n\to\infty} \frac{\Phi_{H,o}(n)}{\Phi_G(n)} > 0.

We say that GG has anchored isoperimetry if, for every p>pc(G)p > p_c(G), the cluster CoC_o almost surely has anchored isoperimetry with respect to GG, conditionally on being infinite. When GG is nonamenable, we have ΦG(n)=Θ(n)\Phi_G(n) = \Theta(n), and anchored isoperimetry of HH with respect to GG simply means that there exists c>0c > 0 such that every sufficiently large finite connected set W⊆V(H)W \subseteq V(H) containing oo satisfies ∣∂HW∣≥c∣W∣|\partial_H W| \ge c|W|. This property is called anchored expansion. Beyond their geometric significance, these notions have important consequences for random walks and phase transitions. In particular, anchored expansion implies positive speed of the simple random walk on bounded-degree graphs [19]; see also [10, 11, 12].

The notion of anchored expansion was introduced by Benjamini, Lyons, and Schramm [3], who asked whether it is preserved under supercritical percolation. Chen and Peres [7], with an appendix by Pete, established anchored expansion for percolation parameters sufficiently close to one. Subsequently, Pete [17], using ideas from that appendix, proved the corresponding anchored isoperimetric inequality for supercritical percolation on Zd\mathbb{Z}^d. The question for nonamenable transitive graphs was eventually resolved for every p>pcp > p_c by Hermon and Hutchcroft [11], who also formulated the general anchored isoperimetry problem for arbitrary transitive graphs (Conjecture 5.4 in [11]). More recently, Martineau and Panagiotis [16] established anchored isoperimetry for transitive graphs of polynomial growth.

Our main result settles this problem for all infinite connected transitive graphs. Moreover, it provides a quantitative strengthening: the probability that an infinite cluster violates the desired anchored isoperimetric inequality at scale nn decays exponentially in ΦG(n)\Phi_G(n).

Theorem 1. Fix any infinite connected transitive graph GG with a vertex o∈V(G)o \in V(G). For every p>pc(G)p > p_c(G), there is a constant c=c(G,p)>0c = c(G,p) > 0 such that, for every n≥1n \ge1,

Pp(∣Co∣=∞, ΦCo,o(n)<c⋅ΦG(n))≤exp⁡(−c⋅ΦG(n)).\mathbb{P}_p\bigl(|C_o| = \infty,\ \Phi_{C_o,o}(n) < c \cdot\Phi_G(n)\bigr) \le\exp\bigl(-c \cdot\Phi_G(n)\bigr).

Previous approaches to anchored isoperimetry have relied on supercritical sharpness, which provides an upper bound on the probability that a vertex belongs to a large but finite cluster. Very recently, supercritical sharpness was established for all infinite transitive graphs [8]. More precisely, it was shown that, for every p>pc(G)p > p_c(G), there exists c=c(G,p)>0c = c(G,p) > 0 such that

Pp(n≤∣Co∣<∞)≤exp⁡(−cΦG(n)),\mathbb{P}_p(n \le|C_o| < \infty) \le\exp(-c\Phi_G(n)),

for every n≥1n \ge1. This result naturally suggests deriving anchored isoperimetry directly from the decay of finite cluster sizes, as in the previously known cases [17, 11, 16]. However, the general approach to converting such tail bounds into anchored isoperimetry incurs a logarithmic loss in ΦG\Phi_G (see [13 Proposition 3.1]), and therefore does not yield the desired bound for arbitrary transitive graphs.

Our proof takes a different route. It combines the thinning-and-sprinkling method, developed in recent papers [9, 1 CDLS26, 6], with a novel counting algorithm. The key idea is to count the possible ways in which connected sets can touch infinite clusters, rather than counting the sets themselves. This ‘reduction in entropy’ allows us to avoid the logarithmic loss and obtain a short, unified proof of anchored isoperimetry for all transitive graphs. Moreover, the argument uses transitivity only through a probabilistic estimate from [8 Proposition 2.1], without requiring any detailed structural information about the underlying graph.

The rest of this paper is organised as follows. We present a high-level overview of the proof in § 2, and give the full details in § 3.

Proof outline

Rather than invoking supercritical sharpness directly, our proof relies on the following key estimate from [8], which concerns the number of edges leaving a finite set that can connect to infinity without returning to the set.

For a finite set S⊆VS \subseteq V, let ΦG(S):=min⁡{∣∂GW∣:S⊆W, ∣W∣<∞}\Phi_G(S) := \min\{|\partial_G W| : S \subseteq W,\ |W| < \infty\} denote the minimum size of an edge cutset separating SS from infinity. Given q>pc(G)q > p_c(G), we also write

tq(S):=∣{uv∈E(G):u∈S, v↔Gq∖S∞}∣.t_q(S) := |\{uv \in E(G) : u \in S,\ v \xleftrightarrow[G_q \setminus S]{} \infty\}|.

The following is a convenient consequence of [8 Proposition 2.1].

Proposition 2.1. Fix an infinite connected transitive graph GG of degree dd. For every q∈(pc(G),1]q \in(p_c(G),1] and every ε∈(0,1)\varepsilon\in(0,1), there exists c>0c > 0 such that, for every finite S⊆VS \subseteq V and every positive integer t≤cΦG(S)t \leq c\Phi_G(S),

Pq(tq(S)≥t)≥(1−ε)t.\mathbb{P}_q(t_q(S) \geq t) \geq(1-\varepsilon)^t.

The relation between this notion of “touches” (that is, edges between SS and the infinite clusters in GqG_q) and anchored isoperimetry goes back to Pete [17]. Roughly speaking, Pete conjectured [18 Conjecture 12.32] that the probability under qq-percolation that the cluster CoC_o is finite and satisfies tq(Co)≥tt_q(C_o) \geq t should decay exponentially in tt (note that this is, morally, the opposite direction of Proposition 2.1 for a special random set SS). This conjecture, combined with supercritical sharpness and the surgery approach of [7 Appendix A], would imply Theorem 1; indeed, this was the approach taken in [17, 16] for G=ZdG = \mathbb{Z}^d and for transitive graphs of polynomial growth. However, for arbitrary transitive graphs, the conjecture of Pete remains open; we take a different path instead.

Call a connected set S⊆CoS \subseteq C_o boundary-minimiser if there is no finite connected superset W⊃SW \supset S with ∣∂CoW∣≤∣∂CoS∣|\partial_{C_o} W| \leq|\partial_{C_o} S|. (Formally, we will work inside a large finite ball, and this notion will be restricted to this ball.) Note that ΦG(S)\Phi_G(S) is nondecreasing under inclusion and therefore, for Theorem 1 to fail, there must be a boundary-minimiser set in GpG_p containing oo with rather large boundary in GG but rather small boundary in GpG_p.

To analyse this event, we will use a variant of the thinning-and-sprinkling method. Fix q∈(pc,p)q \in(p_c,p). Since we are interested in sets SS with few boundary edges in GpG_p, requiring that SS also has no open boundary edges in GqG_q costs, for a fixed pp-configuration, a factor of (1−q/p)∣∂GpS∣(1-q/p)^{|\partial_{G_p}S|}. We further restrict our attention to sets with many qq-touches; by Proposition 2.1 and FKG, this costs a factor of at most (1−ε)−t(1-\varepsilon)^{-t} when t≤cΦG(S)t \leq c\Phi_G(S). Moreover, it follows from [15] that the number of boundary-minimisers with at most kk boundary edges is at most 4k4^k. Our goal will thus be to show that it is very unlikely that CoC_o contains a boundary-minimiser set SS (in GpG_p) with many qq-touches, no boundary edges in GqG_q and too few boundary edges in GpG_p.

Fix n≥1n \ge1, and consider the following setup. First, reveal the entire qq-configuration and let KqK_q be the union of its infinite clusters. If o∈Kqo \in K_q, the obstruction we seek is impossible. Otherwise, reveal the pp-edges within G∖KqG \setminus K_q, and let HH be the component of oo in the resulting graph restricted to a large finite ball. Let M⊆V(H)∖{o}M \subseteq V(H) \setminus\{o\} be the vertices with a neighbour in KqK_q. For a connected set S⊆V(H)S \subseteq V(H) containing oo, its fingerprint U=S∩MU = S \cap M, together with the possible touches at oo, determines all its touch edges. We want to bound the probability that there is such a set SS with no qq-open boundary edges, tq(S)≥tt_q(S) \ge t and ∣∂GpS∣≤k|\partial_{G_p} S| \le k, where t=Θ(ΦG(n))t = \Theta(\Phi_G(n)) and k≤ctk \le ct for a sufficiently small constant cc. (We note that the upper bound provided here will hold not only for boundary-minimiser sets, but more generally.)

A natural first attempt is to union bound over all possible sets SS; however, this approach leads to a severe overcounting. The first key observation is that we can “reduce the entropy” by counting instead the possible fingerprints UU, rather than the sets themselves (see Figure 1).

Figure 1. Two different connected sets S1S_1 (blue) and S2S_2 (green) meeting the same touches, drawn in red.

Indeed, once the qq-configuration has been revealed, each edge between KqK_q and its complement becomes pp-open independently with probability (p−q)/(1−q)(p-q)/(1-q). Thus, for every fixed choice of tt such edges, the probability that at most kk of them are in GpG_p is

P(Bin⁡(t,p−q1−q)≤k)≤exp⁡(−c′t)(1)\mathbb{P}\left(\operatorname{Bin}\left(t,\frac{p-q}{1-q}\right) \le k\right) \le\exp(-c't) \tag*{(1)}

for some c′>0c' > 0 by Chernoff’s bound, provided k≪tk \ll t. This point justifies why we require that tq(S)≥t≫kt_q(S) \ge t \gg k: while we only “paid” for closing kk edges in the thinning stage of the argument, the “price” for opening at most kk edges among tt upon sprinkling is much more significant. Now, we would like to conclude by a union bound argument. Say that U⊆MU \subseteq M is kk-feasible if U=W∩MU = W \cap M for some connected set W⊆V(H)W \subseteq V(H) containing oo with ∣∂HW∣≤k|\partial_H W| \le k. It suffices to control the number of such fingerprints of each size u=∣U∣≥t/du = |U| \ge t/d: indeed, the number of edges from KqK_q touching UU lies in the interval [u,du][u,du], and the sprinkling probability (1) decays exponentially with this number.

To do so, we develop a novel counting algorithm specialised for counting sets with small boundary. Roughly speaking, given a witness WW for a feasible set UU, the algorithm grows an explored region CC from oo. The region CC stays connected in GpG_p and is maximised conditionally on keeping the edge cut separating it from M∖V(C)M \setminus V(C) of minimum size. Then, the algorithm examines a prescribed edge leaving that side. It writes a 1 and enlarges the region if the other endpoint belongs to WW; otherwise it writes a 0 and deletes the edge. The crucial feature is that the resulting binary word determines U=W∩MU = W \cap M, though not necessarily WW itself (Lemma 3.4). Submodularity shows that the word has at most kk zeroes, and the estimate ∣∂HW∣≤k|\partial_H W| \le k allows to bound its length by 3k+(d+1)∣U∣3k + (d+1)|U| (Proposition 3.3). Counting these words gives the required entropy bound; combined with the exponential sprinkling estimate (1) and a union bound over the possible sizes u=∣U∣u = |U|, this completes the argument.

Anchored isoperimetry via thinning and sprinkling

Fix p>pc(G)p > p_{\mathrm{c}}(G), choose q∈(pc(G),p)q \in(p_{\mathrm{c}}(G),p), and consider the natural coupling Gq⊆GpG_q \subseteq G_p. We write ∂p\partial_p and ∂q\partial_q for the corresponding edge boundaries, and use P\mathbb{P} for the joint law of the coupled configurations. Choose ε=ε(p,q)>0\varepsilon= \varepsilon(p,q) > 0 sufficiently small (its precise choice will be determined by comparing the thinning and sprinkling estimates at the end of the proof). By Proposition 2.1, there exists c0=c0(G,q,ε)>0c_0 = c_0(G,q,\varepsilon) > 0 such that Pq(tq(S)≥t′)≥(1−ε)t′\mathbb{P}_q(t_q(S) \ge t') \ge(1-\varepsilon)^{t'} whenever t′≤c0ΦG(S)t' \le c_0 \Phi_G(S). Fix m≥1m \ge1 and set t=c0mt = c_0m. Let α=α(G,p,q,c0)>0\alpha= \alpha(G,p,q,c_0) > 0 be sufficiently small (with its precise value to be chosen later) and set k=αmk = \alpha m.

Recall that BmB_m is the event that there exists a GpG_p-connected set SS containing oo with ΦG(S)≥m\Phi_G(S) \ge m and ∣∂pS∣≤k|\partial_p S| \le k. To work in a finite graph, fix r≥1r \ge1, put B=Br(o)B = B_r(o), and let Bm,rB_{m,r} be the same event with the additional restriction S⊆BS \subseteq B. Since Bm,rB_{m,r} increases to BmB_m as r→∞r \to\infty, it suffices to obtain a bound on Pp(Bm,r)\mathbb{P}_p(B_{m,r}) which is independent of rr.

We compare Bm,rB_{m,r} with the (simpler to analyse) event Et,k,rE_{t,k,r} that there exists a GpG_p-connected set o∈S⊆Bo \in S \subseteq B satisfying ∣∂pS∣≤k|\partial_p S| \le k, ∂qS=∅\partial_q S = \varnothing, and tq(S)≥tt_q(S) \ge t. Thus, Et,k,rE_{t,k,r} describes a set with few pp-open boundary edges, none of them qq-open, but many potential connections to infinity. We first show that thinning from pp to qq transforms a bad anchored set into a configuration satisfying each of these properties at a controlled probability cost.

Lemma 3.1. We have

Pp(Bm,r)≤(1−ε)−t(4pp−q)kP(Et,k,r).\mathbb{P}_p(B_{m,r}) \le(1-\varepsilon)^{-t}\left(\frac{4p}{p-q}\right)^k \mathbb{P}(E_{t,k,r}).

Proof. Call a GpG_p-connected set S⊆BS \subseteq B containing oo a BB-boundary-minimiser if every proper GpG_p-connected superset W⊆BW \subseteq B of SS satisfies ∣∂pW∣>∣∂pS∣|\partial_p W| > |\partial_p S|. In other words, SS cannot be enlarged within BB without increasing its boundary. Since ΦG\Phi_G is increasing under inclusion, whenever Bm,rB_{m,r} occurs, it has a BB-boundary-minimiser witnessing it. (Let us note here that this property is the reason to restrict our graph to the large ball BB.)

To exploit thinning, we count the number of such witnesses that also have many touches and whose boundaries become entirely qq-closed. We first bound from below their expected number, and then use a standard counting result for small edge cuts to turn this into a probability estimate.

Let ZZ denote this number, namely

Z=∑o∈S⊆BΦG(S)≥m1{S is a B-boundary-minimiser, ∣∂pS∣≤k}1{∂qS=∅}1{tq(S)≥t}.Z = \sum_{\substack{o \in S \subseteq B\\ \Phi_G(S) \ge m}} \mathbf{1}_{\{S\text{ is a }B\text{-boundary-minimiser},\,|\partial_pS|\le k\}}\mathbf{1}_{\{\partial_qS=\varnothing\}}\mathbf{1}_{\{t_q(S)\ge t\}}.

Fix a deterministic set SS appearing in this sum, and reveal only the pp- and qq-states of the edges with at least one endpoint in SS. Conditional on this exposure and the connectivity of Gp[S]G_p[S], the event that SS is a BB-boundary-minimiser with ∣∂pS∣≤k|\partial_pS| \le k is increasing in the remaining pp-edges. Indeed, suppose that adding edges outside SS creates a connected superset W⊋SW \supsetneq S whose boundary is no larger than that of SS. Let TT be the component containing SS in the subgraph induced by WW before these edges were added. Since no edge incident to SS has changed, T⊇ST \supseteq S. Moreover, every previously open edge leaving TT also leaves WW, since otherwise its other endpoint would belong to TT. Thus, the original boundary of TT is no larger than the new boundary of WW, contradicting the boundary-minimality of SS. Furthermore, the event {tq(S)≥t}\{t_q(S) \ge t\} is increasing in the qq-edges outside SS. Since the event {tq(S)≥t}\{t_q(S) \ge t\} depends only on these unrevealed edges, FKG and Proposition 2.1 give

P(S is a B-boundary-minimiser, ∣∂pS∣≤k, ∂qS=∅, tq(S)≥t)≥(1−ε)tP(S is a B-boundary-minimiser, ∣∂pS∣≤k, ∂qS=∅).(2)\mathbb{P}(S\text{ is a }B\text{-boundary-minimiser},\ |\partial_p S| \le k,\ \partial_q S = \varnothing,\ t_q(S) \ge t) \ge(1-\varepsilon)^t\mathbb{P}(S\text{ is a }B\text{-boundary-minimiser},\ |\partial_p S| \le k,\ \partial_q S = \varnothing). \tag*{(2)}

Now, reveal the entire pp-configuration and thin each pp-open edge independently with retention probability q/pq/p. For every BB-boundary-minimiser with ∣∂pS∣≤k|\partial_p S| \le k, the probability that its entire boundary becomes qq-closed is at least (1−q/p)k(1-q/p)^k. This allows us to bound the right-hand side of (2) from below and deduce that

P(S is a B-boundary-minimiser, ∣∂pS∣≤k, ∂qS=∅, tq(S)≥t)≥(1−ε)t(1−q/p)kP(S is a B-boundary-minimiser, ∣∂pS∣≤k).\mathbb{P}(S\text{ is a }B\text{-boundary-minimiser},\ |\partial_p S| \le k,\ \partial_q S = \varnothing,\ t_q(S) \ge t) \ge(1-\varepsilon)^t(1-q/p)^k\mathbb{P}(S\text{ is a }B\text{-boundary-minimiser},\ |\partial_p S| \le k).

By summing over all such possible sets SS, and using that Bm,r\mathcal{B}_{m,r} guarantees at least one such boundary-minimiser, we obtain EZ≥(1−ε)t(1−q/p)kPp(Bm,r)\mathbb{E}Z \ge(1-\varepsilon)^t(1-q/p)^k\mathbb{P}_p(\mathcal{B}_{m,r}).

It remains to relate EZ\mathbb{E}Z to the probability of Et,k,r\mathcal{E}_{t,k,r}. Here we use the notion of important separators from [15]. An important edge separator between a vertex oo and a target set is an inclusion-minimal cut which cannot be replaced by a cut of at most the same size that leaves a strictly larger connected component containing oo. Marx [15 Theorem 2] proved that there are at most 4k4^k important separators of size at most kk. (See also Remark 3.5, where we recover this result using the algorithm we present in the next subsection.) We apply this result in the finite graph Gp[B∪NG(B)]G_p[B \cup N_G(B)], taking oo as the ‘source’ and the exterior neighbourhood of BB as the ‘target’. By the maximality property of a BB-boundary-minimiser, its boundary is precisely such an important separator. Consequently, in every pp-configuration, there are at most 4k4^k possible BB-boundary-minimisers with boundary at most kk. Thus, Z≤4kZ \le4^k pointwise. Furthermore, ZZ can be positive only if Et,k,r\mathcal{E}_{t,k,r} occurs. Hence EZ≤4kP(Et,k,r)\mathbb{E}Z \le4^k\mathbb{P}(\mathcal{E}_{t,k,r}). Combining this with the lower bound on EZ\mathbb{E}Z proves the lemma. □

We now bound the probability of the same obstruction from the sprinkling viewpoint. The only additional input is Proposition 3.3, which counts the possible fingerprints of connected sets with small boundary on a prescribed set of marked vertices. Its proof is postponed to Subsection 3.1.

Lemma 3.2. There exists a constant C=C(d,p,q)>1C = C(d,p,q) > 1 such that

P(Et,k,r)≤Cexp⁡{−(p−q)t/20}.\mathbb{P}(\mathcal{E}_{t,k,r}) \le C\exp\{-(p-q)t/20\}.

Proof. Reveal the entire qq-configuration, and let KqK_q be the union of its infinite clusters. Next, reveal the pp-states of all edges with both endpoints in G∖KqG \setminus K_q. Denote by F\mathcal{F} the configuration revealed so far. If o∈Kqo \in K_q, then Et,k,r\mathcal{E}_{t,k,r} is impossible: a finite set containing oo cannot have qq-closed boundary. Otherwise, let HH be the component of oo in the subgraph of (G∖Kq)p(G \setminus K_q)_p induced by BB, and mark the vertices M={u∈V(H)∖{o}:u has a neighbour in Kq}M = \{u \in V(H) \setminus\{o\}: u\text{ has a neighbour in }K_q\}.

Say that U⊆MU \subseteq M is kk-feasible if U=S∩MU = S \cap M for some HH-connected set S⊆V(H)S \subseteq V(H) containing oo with ∣∂HS∣≤k|\partial_H S| \le k. For such a set UU, write b(U)=∣EG(U∪{o},Kq)∣b(U) = |E_G(U \cup\{o\}, K_q)|. Every witness SS to Et,k,r\mathcal{E}_{t,k,r} lies in HH, since its qq-boundary is closed. Hence U=S∩MU = S \cap M is kk-feasible, b(U)=tq(S)≥tb(U) = t_q(S) \ge t, and at most kk of these b(U)b(U) edges are pp-open.

Conditioned on the revealed configuration F\mathcal{F}, all edges between G∖KqG \setminus K_q and KqK_q are qq-closed, and they become pp-open independently with probability θ=(p−q)/(1−q)\theta= (p-q)/(1-q). Assuming k≤θt/2k \le\theta t/2, a Chernoff bound and the relation θ≥p−q\theta\ge p-q ensure that, for every fixed feasible UU with b(U)≥tb(U) \ge t,

P(Bin⁡(b(U),θ)≤k)≤exp⁡(−θb(U)/16)≤exp⁡{−(p−q)b(U)/16}.\mathbb{P}\bigl(\operatorname{Bin}(b(U),\theta) \le k\bigr) \le\exp\bigl(-\theta b(U)/16\bigr) \le\exp\bigl\{-(p-q)b(U)/16\bigr\}.

We will now union-bound over the possible choices of a kk-feasible set UU, rather than over all possible witnesses SS. For this, we use the following counting proposition; its proof is delayed to the next subsection.

Proposition 3.3. Given a finite graph HH with maximum degree at most dd containing a vertex oo and a vertex set M⊆V(H)∖{o}M \subseteq V(H) \setminus\{o\}, the number of kk-feasible vertex subsets of MM of size uu is at most

∑i=0k(3k+(d+1)ui).\sum_{i=0}^{k} \binom{3k+(d+1)u}{i}.

We apply the proposition to the exposed graph HH and the marked set MM. Note that, by excluding oo from MM and including it automatically in b(U)b(U), we avoid any restriction on whether oo has neighbours in KqK_q. Notice that u=∣U∣≤b(U)≤d(u+1)u=|U| \le b(U) \le d(u+1). Thus, b(U)≥tb(U) \ge t implies u≥t/d−1u \ge t/d-1, and b(U)≥max⁡{t,u}b(U) \ge\max\{t,u\} for every relevant UU. Conditioning on F\mathcal{F}, the proposition and a union bound give

P(Et,k,r∣F)≤∑u≥t/d−1(∑i=0k(3k+(d+1)ui))exp⁡{−(p−q)max⁡{t,u}16}.(3)\mathbb{P}(\mathcal{E}_{t,k,r}\mid\mathcal{F}) \le\sum_{u\ge t/d-1}\left(\sum_{i=0}^{k}\binom{3k+(d+1)u}{i}\right)\exp\left\{-(p-q)\frac{\max\{t,u\}}{16}\right\}. \tag*{(3)}

Using that the binomial expression in the term corresponding to uu in the above sum is bounded from above by (3e(du+k)/k)k(3e(du+k)/k)^k, and choosing α\alpha sufficiently small with respect to c0c_0 and dd shows that the right-hand side of (3) is at most

∑u≥t/d−1(3e(du+k)k)kexp⁡{−(p−q)max⁡{t,u}16}≤∑u≥t/d−1exp⁡{−(p−q)max⁡{t,u}18}≤Ce−(p−q)t/20.\sum_{u\ge t/d-1}\left(\frac{3e(du+k)}{k}\right)^k\exp\left\{-(p-q)\frac{\max\{t,u\}}{16}\right\} \le\sum_{u\ge t/d-1}\exp\left\{-(p-q)\frac{\max\{t,u\}}{18}\right\} \le Ce^{-(p-q)t/20}.

for a suitably large constant C=C(d,p,q)>1C=C(d,p,q)>1. Since the bound is uniform in F\mathcal{F}, averaging completes the proof. □\square

Combining the two lemmas, and recalling that t=c0mt=c_0m and k=αmk=\alpha m, we choose ε>0\varepsilon>0 sufficiently small with respect to p,qp,q, and α>0\alpha>0 sufficiently small compared with c0c_0, so that

Pp(Bm,r)≤C(1−ε)−t(4pp−q)kexp⁡{−(p−q)t/20}≤Cexp⁡{−γm}\mathbb{P}_p(\mathcal{B}_{m,r}) \le C(1-\varepsilon)^{-t}\left(\frac{4p}{p-q}\right)^k\exp\{-(p-q)t/20\} \le C\exp\{-\gamma m\}

for some γ=γ(G,p,q)>0\gamma=\gamma(G,p,q)>0, and note that this bound holds uniformly in rr.

Finally, we choose c≤min⁡{γ,α}c\le\min\{\gamma,\alpha\} in the exponent such that the factor CC can be absorbed into it. This is indeed possible: note that, for small mm, taking the constant cc in Theorem 1 sufficiently small produces a trivial bound on the event that ∣Co∣=∞|C_o|=\infty. Letting r→∞r\to\infty and taking m=ΦG(n)m=\Phi_G(n) completes the proof. □\square

The algorithm and proof of Proposition 3.3

In this section, we prove the aforementioned Proposition 3.3. To prove this statement, we develop an algorithm that encodes each kk-feasible set U⊆MU\subseteq M by a short binary word. Given a connected set WW witnessing the feasibility of UU, the algorithm produces a binary word from which U=W∩MU=W\cap M can be uniquely recovered. The key properties of this encoding are that the word contains at most kk zeroes and has length at most 3k+(d+1)∣U∣3k+(d+1)|U|. Counting such words then gives the desired bound on the number of feasible sets.

We now describe the algorithm and then establish these properties. In this description, parameters called dynamic are going to evolve during the algorithm; we denote these by bold letters and we use the symbol ←\leftarrow to update their values.

Algorithm 1. Input: a finite connected graph H0H_0 containing a vertex oo with an ordering σ\sigma of its edge set E(H0)E(H_0), an H0H_0-connected vertex set W⊆V(H0)W \subseteq V(H_0) containing oo, and a set of marked vertices M⊆V(H0)∖{o}M \subseteq V(H_0) \setminus\{o\}. Initiate a dynamic graph H←H0\mathbf{H} \leftarrow H_0, dynamic vertex sets C←{o}\mathbf{C} \leftarrow\{o\}, C′←∅\mathbf{C}' \leftarrow\varnothing and T←∅\mathbf{T} \leftarrow\varnothing, a dynamic edge set F←∅\mathbf{F} \leftarrow\varnothing, and a dynamic integer r←0\mathbf{r} \leftarrow0.

Output: we construct a binary word w\mathbf{w} initially set to ∅\varnothing.

Procedure: at every iteration, first check whether T=W∩M\mathbf{T} = W \cap M. If this is the case, terminate the algorithm and output the word w\mathbf{w}. Otherwise, update r\mathbf{r} to be the size of a minimum edge-cutset in H\mathbf{H} between C\mathbf{C} and M∖TM \setminus\mathbf{T}. Next, update C′\mathbf{C}' to be the connected vertex set in H\mathbf{H} which:

  • contains C\mathbf{C} but is disjoint from the set M∖TM \setminus\mathbf{T},

  • satisfies ∣∂HC′∣=r|\partial_{\mathbf{H}}\mathbf{C}'| = \mathbf{r},

  • has maximum size given the previous two conditions, and

  • if more than one set satisfies the conditions above, C′\mathbf{C}' is chosen so that ∂HC′\partial_{\mathbf{H}}\mathbf{C}' is minimal with respect to the lexicographic ordering on the edge subsets of E(H0)E(H_0) induced by σ\sigma.

Set F←∂HC′\mathbf{F} \leftarrow\partial_{\mathbf{H}}\mathbf{C}' and let e=uve = uv be the first edge of F\mathbf{F} in the ordering σ\sigma, with u∈C′u \in\mathbf{C}'.

(a) If v∉Wv \notin W, append a 0 to w\mathbf{w}, update H←H∖{e}\mathbf{H} \leftarrow\mathbf{H} \setminus\{e\} and C←C′\mathbf{C} \leftarrow\mathbf{C}'.

(b) If v∈W∖Mv \in W \setminus M, append a 1 to w\mathbf{w} and update C←C′∪{v}\mathbf{C} \leftarrow\mathbf{C}' \cup\{v\}.

(c) If v∈W∩Mv \in W \cap M, append a 1 to w\mathbf{w} and update C←C′∪{v}\mathbf{C} \leftarrow\mathbf{C}' \cup\{v\} and T←T∪{v}\mathbf{T} \leftarrow\mathbf{T} \cup\{v\}.

Finally, proceed to the next iteration.

Initial state and state after one iteration of Algorithm 1

Figure 2. Initial state (left) and state after one iteration (right) of Algorithm 1. The fixed witness W={o,a,b,u,v,m1}W = \{o, a, b, u, v, m_1\} is shaded grey; squares indicate the marked vertices M={m1,m2}M = \{m_1, m_2\}. The boundary of C′\mathbf{C}' on the left is F={e}\mathbf{F} = \{e\}. Since v∈W∖Mv \in W \setminus M, case (b) gives C←C′∪{v}\mathbf{C} \leftarrow\mathbf{C}' \cup\{v\} (coloured in teal) and w\mathbf{w} becomes 1.

Observe that the algorithm is well-defined and terminates. Indeed, only edges with an endpoint outside WW are deleted, so any vertex v∈(W∩M)∖Tv \in(W \cap M) \setminus\mathbf{T} remains connected to oo in H\mathbf{H}; hence, as long as the algorithm is still running, the next edge ee always exists. Moreover, each iteration either deletes an edge or enlarges C\mathbf{C}. Let us note here that the choice of a largest boundary-minimising set C′\mathbf{C}' is crucial for controlling the length of the word: case (b) forces the minimum-cut size to increase, while the possible decreases in cases (a) and (c) will be shown to be controlled by kk and ∣U∣|U|, respectively.

We first establish that the output word determines W∩MW \cap M.

Lemma 3.4. Given the input H0H_0, MM, oo, σ\sigma and the output ww of the algorithm upon termination, the set W∩MW \cap M can be uniquely determined.

Proof. Starting from the known initial state, we reconstruct the algorithm one bit at a time. The current values of H,C,T\mathbf{H}, \mathbf{C}, \mathbf{T}, together with σ\sigma, determine C′\mathbf{C}', F\mathbf{F}, and the next edge e=uve=uv. If the next bit is 0, we follow case (a). If it is 1, we follow case (b) or (c), according to whether v∉Mv \notin M or v∈Mv \in M. Thus, each bit uniquely determines how to update each of H,C,T\mathbf{H}, \mathbf{C}, \mathbf{T}. After reading the entire word, the recovered set T\mathbf{T} equals W∩MW \cap M, as required. □

We emphasise that the purpose of the algorithm and the decoding Lemma 3.4 is not to recover the set WW itself, but only the set U=W∩MU=W \cap M. Indeed, many different sets WW may have the same intersection with MM, and distinguishing between them would lead to a substantial overcounting. The key feature of our algorithm is precisely that it encodes only the information needed to recover UU. Thus, for fixed H0H_0, MM, oo, σ\sigma, each output word determines at most one subset of MM.

Recall that a set U⊆MU \subseteq M is kk-feasible if there exists an H0H_0-connected set WW containing oo such that W∩M=UW \cap M=U and ∣∂H0W∣≤k\lvert\partial_{H_0} W\rvert\leq k. Call any such WW a witness for UU. We can now prove Proposition 3.3.

Proof of Proposition 3.3. Fix an arbitrary ordering σ\sigma of the edges of H0H_0. Given a kk-feasible set U⊆MU \subseteq M of size tt, choose an arbitrary witness WW and let ww be the binary word produced by Algorithm 1. By Lemma 3.4, different feasible sets UU give different words. Thus, it suffices to count the possible output words.

First, we show that ww contains at most kk zeroes. Crucially, note that an edge deleted when writing a zero need not belong to ∂H0W\partial_{H_0} W since the boundary-minimising set C′\mathbf{C}' may contain vertices outside WW; we therefore track the boundary of an enlarged witness W∪C′W \cup\mathbf{C}'. Let Hi−1H_{i-1}, Ci−1C_{i-1}, Ti−1T_{i-1} denote the values of H\mathbf{H}, C\mathbf{C}, T\mathbf{T} before iteration ii, and let Ci′C'_i, FiF_i be the values of C′\mathbf{C}', F\mathbf{F} during that iteration. Set W0=WW_0=W and Wi=W∪Ci′W_i=W \cup C'_i for i≥1i \geq1 (the WiW_i will play the role of the enlarged witness that we track). As the sets Ci′C'_i are nested, we have Wi=Wi−1∪Ci′W_i=W_{i-1}\cup C'_i. Also, Ci−1⊆Wi−1C_{i-1}\subseteq W_{i-1} (since Ci−1∖Ci′C_{i-1}\setminus C'_{i} is either a single vertex in WW or empty), while Ci′C'_i is disjoint from M∖Ti−1M\setminus T_{i-1}. Hence, ∂Hi−1(Wi−1∩Ci′)\partial_{H_{i-1}}(W_{i-1}\cap C'_i) separates Ci−1C_{i-1} from M∖Ti−1M\setminus T_{i-1}, and the minimality of FiF_i gives ∣∂Hi−1(Wi−1∩Ci′)∣≥∣Fi∣\lvert\partial_{H_{i-1}}(W_{i-1}\cap C'_i)\rvert\geq\lvert F_i\rvert. By submodularity of the edge boundary (see e.g. [14 Section 1.1]),

∣∂HiWi∣≤∣∂Hi−1Wi∣≤∣∂Hi−1Wi−1∣+∣Fi∣−∣∂Hi−1(Wi−1∩Ci′)∣≤∣∂Hi−1Wi−1∣.\lvert\partial_{H_i}W_i\rvert\leq\lvert\partial_{H_{i-1}}W_i\rvert\leq\lvert\partial_{H_{i-1}}W_{i-1}\rvert+\lvert F_i\rvert-\lvert\partial_{H_{i-1}}(W_{i-1}\cap C'_i)\rvert \leq\lvert\partial_{H_{i-1}}W_{i-1}\rvert.

The first inequality is strict in case (a), since the deleted edge e=uve=uv crosses the boundary of WiW_i: indeed, u∈Ci′⊆Wiu\in C'_i\subseteq W_i and v∉W∪Ci′=Wiv\notin W\cup C'_i=W_i. Thus, the boundary of the enlarged witness WiW_i never increases and decreases by at least one whenever we write a zero. Since ∣∂H0W0∣≤k\lvert\partial_{H_0}W_0\rvert\leq k, the word has at most kk zeroes.

Next, we bound the length of ww. If t=0t=0, there is only one possible set U=∅U=\varnothing, so the proposition is immediate. Thus assume t≥1t\geq1. In case (a), deleting one edge decreases the minimum-cut value by at most one, so ∣Fi+1∣−∣Fi∣≥−1\lvert F_{i+1}\rvert-\lvert F_i\rvert\geq-1. In case (c), we have ∣Fi+1∣−∣Fi∣≥−d\lvert F_{i+1}\rvert-\lvert F_i\rvert\geq-d: adding the at most dd edges incident to the newly recorded marked vertex vv to any cut for the next step gives a cut for the preceding step. Crucially, in case (b), ∣Fi+1∣−∣Fi∣≥1\lvert F_{i+1}\rvert-\lvert F_i\rvert\geq1. Indeed, the graph HiH_i and target set M∖TiM\setminus T_i are unchanged, so the minimum-cut value cannot decrease; if it stayed unchanged, there would be an HiH_i-connected set with minimum boundary containing Ci′∪{v}C'_i\cup\{v\}, contradicting the maximality of Ci′C'_i.

Let τ\tau be the number of iterations, so that Tτ=UT_\tau=U. Recall that the submodularity argument gives ∣∂HiWi∣≤k\lvert\partial_{H_i}W_i\rvert\leq k throughout the algorithm. At intermediate stages, the boundary of WiW_i, together with the edges incident to the vertices in U∖(Ti∪Ci)U\setminus(T_i\cup C_i), separates CiC_i from M∖TiM\setminus T_i. At termination, however, we have that U⊆CτU \subseteq C_{\tau}. Since Cτ⊆WτC_{\tau} \subseteq W_{\tau} and Wτ∩M=UW_{\tau} \cap M = U, the boundary of WτW_{\tau} itself separates CτC_{\tau} from M∖UM \setminus U. Thus, letting Fτ+1F_{\tau+1} be a minimum cut between these sets in HτH_{\tau}, we obtain

∣Fτ+1∣≤∣∂HτWτ∣≤∣∂H0W∣≤k.|F_{\tau+1}| \leq|\partial_{H_{\tau}} W_{\tau}| \leq|\partial_{H_0} W| \leq k.

Writing α,β,γ\alpha, \beta, \gamma for the numbers of iterations of types (a), (b), (c), respectively, we have α≤k\alpha\leq k and γ=t\gamma= t. The preceding bounds imply β−α−dγ≤∣Fτ+1∣−∣F1∣≤k\beta- \alpha- d\gamma\leq|F_{\tau+1}| - |F_1| \leq k, and consequently τ=α+β+γ≤3k+(d+1)t\tau= \alpha+ \beta+ \gamma\leq3k + (d+1)t.

Finally, pad every output word with 1-bits to length L=3k+(d+1)tL = 3k + (d+1)t. Since we are counting feasible sets UU of fixed size tt, the padded word still determines UU: we run the same procedure described above until exactly tt marked vertices have been recovered. Thus, padding preserves injectivity, and the number of possible words is at most

∑i=0k(3k+(d+1)ti),\sum_{i=0}^{k} \binom{3k+(d+1)t}{i},

as desired. □

Remark 3.5. Our algorithm also allows us to recover the bound on important separators from [15 Theorem 2], used earlier in the proof.

Let HH be a locally finite graph containing a vertex oo, and let B∋oB \ni o be a finite vertex set. Recall that a connected set W⊆BW \subseteq B containing oo is a BB-minimiser if there is no proper connected superset S⊋WS \supsetneq W, S⊆BS \subseteq B, with ∣∂HS∣≤∣∂HW∣|\partial_H S| \leq|\partial_H W|. We apply Algorithm 1 with H0H_0 being the component of oo in H[B∪NH(B)]H[B \cup N_H(B)] and M=NH(B)∩V(H0)M = N_H(B) \cap V(H_0), replacing the stopping condition by the requirement that the minimum cut-value becomes zero.

For a BB-boundary-minimiser WW, induction shows that every value of C′C' throughout the algorithm is contained in WW, and every deleted edge belongs to ∂HW\partial_H W. Indeed, assuming this for previously deleted edges, the minimum-cut property and submodularity imply that adding the chosen boundary-minimiser to WW cannot increase its boundary. By BB-boundary-minimality, this side must therefore be contained in WW, and any subsequently deleted edge belongs to ∂HW\partial_H W. Consequently, upon termination, the component of oo in the remaining graph contains WW, is contained in BB, and has all its boundary edges among those deleted. By BB-boundary-minimality, this component must equal WW, which can therefore be recovered from the output word.

Moreover, since W∩M=∅W \cap M = \varnothing, case (c) never occurs. If ∣∂HW∣≤k|\partial_H W| \leq k, the word contains at most kk zeroes, since each zero deletes a distinct edge of ∂HW\partial_H W. Each one increases the minimum cut-value by at least one, while each zero decreases it by at most one. Since the final cut-value is zero, the number of ones is at most the number of zeroes. Thus, the word has length at most 2k2k. As before, padding shorter words with ones preserves injectivity. This gives at most ∑i=0k(2ki)≤4k\sum_{i=0}^{k} \binom{2k}{i} \leq4^k such minimisers.

Acknowledgements The authors are grateful to Vincent Tassion and Philip Easo for fruitful discussions. BS was supported in part by SNSF grant 20021-228014.

Use of AI: AI models were used only to generate the figures from photos of hand-drawn ones, as well as to assist with proofreading of the paper.

References

References

  1. [1][ADLZ25] Michael Anastos, Sahar Diskin, Lyuben Lichev, and Maksim Zhukovskii. Diameter and mixing time of the giant component in the percolated hypercube. Preprint, arXiv:2510.13348, 2025.arxiv.org/abs/2510.13348
  2. [2][BH57] Simon R. Broadbent and John M. Hammersley. Percolation processes. I. Crystals and mazes. Proceedings of the Cambridge Philosophical Society, 53:629–641, 1957.
  3. [3]Itai Benjamini, Russell Lyons, and Oded Schramm. Percolation perturbations in potential theory and random walks. In Massimo A. Picardello and Wolfgang Woess, editors, Random Walks and Discrete Potential Theory, volume XXXIX of Symposia Mathematica, pages 56–84. Cambridge University Press, Cambridge, 1999. Proceedings of the conference held in Cortona, June 1997.DOI
  4. [4]Itai Benjamini and Oded Schramm. Percolation beyond ℤᵈ, many questions and a few answers. Electronic Communications in Probability, 1:71–82, 1996.
  5. [6]Micha Christoph, Zach Hunter, and Benny Sudakov. Thinning and sprinkling: from robust sampling to almost Hamiltonicity. Preprint, arXiv:2609.30165, 2026.arxiv.org/abs/2609.30165
  6. [7]Dayue Chen and Yuval Peres. Anchored expansion, percolation and speed. The Annals of Probability, 32(4):2978–2995, 2004. With an appendix by Gábor Pete.
  7. [8]Sahar Diskin, Philip Easo, Ritvik Ramanan Radhakrishnan, Benny Sudakov, and Vincent Tassion. Supercritical sharpness of percolation. Preprint, arXiv:2603.03257, 2026.arxiv.org/abs/2603.03257
  8. [9]Sahar Diskin and Michael Krivelevich. Expansion in supercritical random subgraphs of expanders and its consequences. Random Structures & Algorithms, 65(3):576–600, 2024.arxiv.org/abs/2205.04852
  9. [10]Thierry Delmotte and Clément Rau. Exit time for anchored expansion. Preprint, arXiv:0903.3892v2, 2015. Version 2, 2 July 2015; first posted 23 March 2009.
  10. [11]Jonathan Hermon and Tom Hutchcroft. Supercritical percolation on nonamenable graphs: isoperimetry, analyticity, and exponential decay of the cluster size distribution. Inventiones Mathematicae, 224(2):445–486, 2021.arxiv.org/abs/1904.10448
  11. [12]Olle Häggström, Roberto H. Schonmann, and Jeffrey E. Steif. The Ising model on diluted graphs and strong amenability. The Annals of Probability, 28(3):1111–1137, 2000.DOI
  12. [13]Tom Hutchcroft. Transience and anchored isoperimetric dimension of supercritical percolation clusters. Electronic Journal of Probability, 28:Paper No. 14, 2023. 15 pp.arxiv.org/abs/2207.05226
  13. [14]Andreas Krause and Daniel Golovin. Submodular function maximization. In Lucas Bordeaux, Youssef Hamadi, and Pushmeet Kohli, editors, Tractability: Practical Approaches to Hard Problems, chapter 3, pages 71–104. Cambridge University Press, Cambridge, 2014.
  14. [15]Dániel Marx. Important separators and parameterized algorithms. In Petr Kolman and Jan Kratochvíl, editors, Graph-Theoretic Concepts in Computer Science, volume 6986 of Lecture Notes in Computer Science, pages 5–10, Berlin, Heidelberg, 2011. Springer.DOI
  15. [16]Sébastien Martineau and Christoforos Panagiotis. Percolation on graphs of polynomial growth is local: analyticity, supercritical sharpness, isoperimetry. Preprint, arXiv:2511.01851v2, 2025. Version 2, revised 1 March 2026.arxiv.org/abs/2511.01851
  16. [17]Gábor Pete. A note on percolation on ℤᵈ: isoperimetric profile via exponential cluster repulsion. Electronic Communications in Probability, 13:377–392, 2008.arxiv.org/abs/math/0702474
  17. [18]Gábor Pete. Probability and geometry on groups. Lecture notes for a graduate course, https://math.bme.hu/~gabor/PGG.pdf, 2024. Version of 3 April 2024.
  18. [19]Bálint Virág. Anchored expansion and random walk. Geometric and Functional Analysis, 10(6):1588–1605, 2000.DOI

Paper details

vlnc:W_mx2nyjks
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents