Critical bond and site percolation on the cubic lattice

Proof. Closing every hyperedge incident to x_k proves d_k>0. The matrix H is unit lower triangular: its kth column vanishes above row k and has entry one in row k. We prove (2.2) by descending induction on k. For k=n, both v_n^F and \mu_n(F)h_n equal \mu_n(F)e_n, where e_n is the nth coordinate vector.

Fix k<n and assume the assertion for every later column. Write s=x_k, S=S_k, and W=C(S). For a set w\supseteq S avoiding s, put

where the expectation uses the original product law on the undeleted hyperedges. Restriction of the same configuration shows that c(w) is nonincreasing in w.

A first-listed-node decomposition. Fix a row i. For j>k, let L_{ij} be the event that the first listed node of C(x_i) is x_j. Condition on an exact value W=w avoiding s. Then the mean of F(C(s)) is c(w). If x_i\notin w, its cluster contains the listed node x_i and avoids all listed nodes preceding s, which belong to w. Its first listed node is therefore s precisely when x_i\in C(s); otherwise exactly one of the events L_{ij} occurs. On L_{ij}, condition further on C(x_j)=U. The set U avoids s, and the specification of L_{ij} adds only membership and avoidance conditions on U. Exact-cluster conditioning therefore leaves the mean of F(C(s)) equal to c(w\cup U). Partitioning the expectation c(w) and subtracting c(w) times the corresponding partition of total probability gives

The expressions involving c(w\cup C(x_j)) are evaluated only on L_{ij}. If x_i\in w, all L_{ij} are empty under the conditioning, and both sides vanish.

For U disjoint from S, let W_U=C^{G\setminus U}(S). Define, for U\in\mathcal D_k,

and, for U disjoint from S\cup\{s\}, define

with zero integrand when s\in W_U. The operator P preserves nonnegativity and monotonicity: enlarging U shrinks W_U, whereas c is nonincreasing.

We now average (2.3) conditional on E_k. Given C(s)=U avoiding S, the conditional law of W is that of W_U. Thus the first term on the right averages to

For a residual term, the exact event identity is

Indeed, a cluster avoiding the earlier listed nodes also avoids their entire clusters. Given C(x_j)=U under E_j, the conditional law of W is again that of W_U, and the remaining restriction E_k is s\notin W_U. Consequently the unnormalized residual expectation is

where the expression on the left is evaluated only when its indicator is one. Dividing by d_k and summing over j>k proves the column identity

Here and below R_F is restricted to \mathcal D_j in the jth column. To complete the induction, we show that R_F is nonnegative and increasing and that P^tF converges uniformly to \mu_k(F).

The residual is increasing. Sample all hyperedge bits once, and use their restrictions after every deletion. For deterministic U disjoint from S\cup\{s\}, the event W_U=w tests only bits of hyperedges disjoint from U and meeting w. Every full-graph hyperedge disjoint from w therefore retains its independent original law after this conditioning, including hyperedges that meet U. When s\notin w, the two clusters in the following difference consequently have the marginal laws defining c(w) and c(w\cup U). Hence R_F(U)=\mathbb E[D_U], where

again interpreted as zero on the excluded event. All clusters at which F is evaluated contain s and avoid S.

The first cluster contains the second, so D_U\ge0. To compare two sets U\subseteq U', first note that W_{U'}\subseteq W_U. On \{s\notin W_U\}, deleting the smaller set W_{U'} makes the first cluster larger. The second cluster has a different monotonicity:

Indeed, in G\setminus U the source cluster is disjoint from the union W_U of the S-clusters, so deleting W_U removes none of its open connections. The same equality holds for U', because s\notin W_{U'}. Thus the second cluster becomes smaller when U is replaced by U'. Both changes increase the difference of the two values of F, giving D_{U'}\ge D_U. On \{s\in W_U\}, this inequality follows instead from D_U=0 and D_{U'}\ge0. Taking expectations proves that R_F is nonnegative and increasing.

Conditional resampling and the limit. The operator P is a Markov transition: from U, first sample W_U, then independently sample C^{G\setminus W_U}(s). Under the joint law of (C(s),W) conditional on E_k, these are the successive conditional laws of W given C(s) and of C(s) given W. Hence \mu_k is stationary for P. Alternating conditional cluster resampling under a separation condition is the method used by van den Berg, Häggström, and Kahn [15, Section 2.1, proof of Theorem 2.1]; the cone conclusion here is proved by the following iteration.

Every transition assigns probability at least

to the singleton \{s\}, since closing every incident hyperedge suffices to isolate s in any deletion graph. Thus, for every real function g on the finite state space \mathcal D_k, subtracting this common mass gives

Iteration makes the oscillation of P^tF tend to zero. Its \mu_k-mean remains \mu_k(F) by stationarity, so

This proves the required uniform convergence, including at states of \mathcal D_k with zero \mu_k-mass.

By the induction hypothesis, each v_j^{R_F} is a nonnegative combination of h_j,\ldots,h_n. Equation (2.5) therefore puts v_k^F-v_k^{PF} in the cone on the right of (2.2). All iterates P^tF remain nonnegative increasing, so iteration puts v_k^F-v_k^{P^tF} in that cone as well. The cone is closed, because its generators belong to the basis given by the columns of H. Taking the uniform limit proves (2.2). Finally, adding \mu_k(F)h_k expresses v_k^F as a nonnegative combination of columns of H, proving the last assertion.□

Proof of Proposition 2.1. First suppose all probabilities are below one. Use the notation of Lemma 2.2. For F(U)=\mathbf 1_{\{x_j\in U\text{ for some }j>k\}}, isolation of x_k gives \mu_k(F)<1, and direct inspection of the rows gives

where e_k is the kth coordinate vector. Lemma 2.2 yields nonnegative coefficients \Gamma_{jk} such that

With \Gamma zero on and above the diagonal, these column identities say H=I+H\Gamma, or H^{-1}=I-\Gamma. Also, for d=(d_1,\ldots,d_n)^\mathsf T,

Indeed, the cluster of x_i has first listed node x_k with probability d_kh_k(i), and these events partition the sample space.

If o\in A, (2.1) is immediate. Otherwise take the list to consist exactly of the nodes of A, in any order, followed by x_n=o. Set

Partitioning by the first listed node gives y=\sum_k d_kv_k^F, where F is restricted to \mathcal D_k in each summand. Every restriction is nonnegative increasing, so Lemma 2.2 gives (I-\Gamma)y\ge0 coordinatewise. In the last row,

For i<n, y_i=\mathbb P(x_i\leftrightarrow T), while y_n=\mathbb P(o\leftrightarrow A,\ o\leftrightarrow T). By (2.7), the nonnegative weights in this row sum to

This proves (2.1). Finally, finite event probabilities are polynomials in the hyperedge parameters, and the minimum in (2.1) is finite. Continuity therefore allows probabilities equal to one as well.□

Proof. The empty-set case A=\varnothing is immediate. For bonds, Proposition 2.1 and subtraction give the stronger upper bound b\mathbb P(o\leftrightarrow A)\le b.

For sites, use the incidence construction described in [3, “One inequality for both models”]. Create a node x^* for every graph vertex x and a connector node for every graph edge. For each site x, form a hyperedge consisting of x^* and all connector nodes corresponding to edges incident to x; its independent open bit is the bit of site x. For distinct vertices x,z, connection of x^* to z^* is equivalent to an open site path from x to z. Hypergraph self-connection, however, always holds. Writing A^*,T^* for the starred images, we consequently have

On the site event in (2.8), the origin o is open. Its hypergraph connections to starred vertices therefore agree with its site connections, including a possible zero-edge path to itself. This gives the event inclusion

Applying Proposition 2.1 and subtraction to the hypergraph bounds the latter event by b, proving the site assertion. Fixed bits are exactly parameters equal to zero or one, already allowed in the statement.□

Proof. At a dual vertex, the boundary degree counts the membership changes around a primal square, and is therefore even. The finite dual boundary consequently decomposes into edge-disjoint simple cycles: extract a simple cycle whenever an edge remains, and remove its edges, preserving even degrees.

Along the positive horizontal ray from 0, the total number of boundary crossings is odd, since membership in X starts at one and eventually becomes zero. At least one cycle in the decomposition has an odd number of positive-ray crossings. The total number of crossings of a closed dual cycle with the whole horizontal line is even, by counting changes of the sign of the height. The selected cycle therefore also crosses the negative ray.

If its length is n, a positive crossing has horizontal coordinate t+1/2 for some integer 0\le t<n: the horizontal distance to a negative crossing is less than n. Define \mathcal C_n to be all simple length-n cycles having such an anchored crossing and an odd number of positive-ray crossings. There are at most n choices for the anchored edge, two orientations, and at most 3^n nonbacktracking continuations. This proves the asserted overcount. Finally, greedily select crossed primal edges in a fixed order, discarding all edges incident to either endpoint of each selection. Each selection discards at most seven edges, including itself, because the primal degree is four. The selected edges have disjoint endpoints and number at least n/7.□

Proof. It suffices to percolate on a coordinate copy of \mathbb Z^2. In the bond model, if the origin cluster there is finite, all primal edges crossed by its dual boundary are closed. Lemma 3.1 and a union bound give

for p<1 sufficiently close to one.

For sites, first separate the event that 0 is closed. If its open planar cluster is finite, each edge crossed by the boundary cycle has a closed endpoint. For a fixed candidate cycle, select k\ge n/7 edges with disjoint endpoints as in Lemma 3.1. The union over choices of one closed endpoint of each edge has probability at most [2(1-p)]^k. For p close to one, 2(1-p)<1, so

Indeed both displayed series are convergent geometric-power series tending to zero as p\uparrow1. This proves the lemma.□

Proof. The series in (3.3) tends to zero as f\downarrow0, so choose f first. Choose \delta<f, then \eta sufficiently small for the first inequality of (3.4), then \tau, and finally \gamma, in that order. By (3.2), choose m\ge1 so that the probability that \Lambda_m meets no infinite cluster at parameter p is less than (\gamma/2)^{24}.

For every integer \ell>m, any infinite cluster meeting \Lambda_m gives an open path from \Lambda_m to the vertex boundary of \Lambda_\ell inside that cube. Thus the probability of missing the whole boundary is less than (\gamma/2)^{24}. By signed coordinate symmetry, all 24 quarter-face miss events have the same probability, say a_\ell. They are decreasing events of a finite product, so positive association gives

Consequently a_\ell<\gamma/2 for every \ell>m.

Now M and \rho_0 are fixed and positive. Choose K, define L and \alpha>0, and choose R and then r to satisfy (3.5). All these choices precede the choice of q. At each of the three radii 2r,2r+1,10r, a quarter-face connection event uses finitely many bits, so its probability is a polynomial in the parameter. The strict estimate at p, with margin \gamma/2, therefore persists with margin \gamma at some single q\in(p/2,p), simultaneously for all 24 faces and all three radii. Translation invariance gives the same estimates for every center u. This proves (3.6).□

Proof. We first choose a deterministic layer at which a connection to B usually supplies many possible entry points. We then try disjoint open seed boxes at those points, and use Corollary 2.3 to pass from a successful seed to T.

Choosing a layer. The disjoint closure events used here also appear in Grimmett and Marstrand [7, Section 3, Lemma 3]. For m\le j<R, expose only the bits internal to the induced graph outside B^{(j)}. Let Y_j be the exterior neighbors of B^{(j)} reachable from o by an open path in this outside graph, and set N_j=|Y_j|. Every exterior neighbor y of a rectangle has a unique neighbor z_y inside it. Both endpoints and their edge lie in B^{(j+1)}\subseteq D. Since o is outside B^{(R)}, any path from o to B has a first entry into B^{(j)}, and hence N_j\ge1.

On 1\le N_j<L, consider the event that all bonds \{y,z_y\}, y\in Y_j, are closed in the bond model, or that all corresponding sites z_y are closed in the site model. Given the outside bits, these are unexposed parameter-q bits. There are at most N_j distinct bits; repeated sites z_y can only increase the closure probability. Thus its conditional probability is at least

Such a closure prevents every first entry into B^{(j)}. In particular, N_i=0 for all i<j, because every exterior neighbor of B^{(i)} belongs to B^{(j)}. The events consisting of 1\le N_j<L and this closure are therefore pairwise disjoint as j varies. It follows that

Fix a deterministic j\in\{m,\ldots,R-1\} for which

Write C=B^{(j)}. Let \xi be the configuration of bits internal to C, and let \zeta be the configuration of bits internal to the induced graph outside C. Thus Y_j is determined by \zeta. For bonds, the remaining bits are the bonds crossing between C and its complement. The configurations \xi, \zeta, and these crossing bits are independent. All bits of \xi and all crossing bits have parameter q, since they lie in B^{(j+1)}\subseteq D. For sites, \xi and \zeta already partition the bits.

We will use these two configurations for different purposes. The exterior \zeta selects entrances that o has reached, whereas \xi determines which relay centers have high conditional probability of reaching T. We first estimate relay quality for each fixed entrance, then use independence to apply that estimate to the entrances selected by \zeta.

Defining good relays from \xi. For every exterior neighbor y of C, choose v_y so that

Explicitly, clamp each coordinate of z_y to the corresponding coordinate interval of C shrunk by m at both ends. Those shrunken intervals are nonempty because j\ge m. Let O_y be the event that every internal bit of U_y is open. Then O_y is determined by \xi and \mathbb P(O_y)=q^M. Define

In this definition the exterior configuration and the crossing bits are still averaged over according to their original product law. In particular, A_\xi is determined by \xi alone.

For a fixed y, apply the geometric hypothesis at u=v_y. The quarter-face estimate (3.6) supplies an increasing event of probability greater than 1-\gamma connecting U_y to T inside the specified cube. On its intersection with O_y, the center v_y also connects to T. Positive association gives

Since O_y is determined by \xi, it follows that

This bounds the chance that a fixed seed is open but its center fails the defining condition for A_\xi.

Selecting reachable entrances using \zeta. Condition now on \zeta. Whenever N_j\ge L, choose deterministically K members of Y_j at pairwise sup distances greater than 4m+2. This is possible by greedy selection: each chosen vertex excludes at most (8m+5)^3 candidates, while L=K(8m+5)^3. The corresponding centers have pairwise distances greater than 2m, so their boxes U_y are vertex-disjoint.

Call a selected entrance successful if O_y holds and, for bonds, the crossing bond \{y,z_y\} is open. For sites, y is already open because it is reachable in the outside graph, and the open seed contains z_y. In either model a success therefore gives an actual open path from o to v_y.

Given \zeta, these successes are independent Bernoulli trials with common parameter

Indeed, the boxes use disjoint sets of bits of \xi, and the selected crossing bonds are distinct and independent of \xi and \zeta. If S counts successes, its conditional variance is at most Kc. Chebyshev’s inequality gives

Let Z count successful entrances whose centers satisfy g_y\le1-\tau. For each selected y, (4.3) gives

Indeed, after fixing \zeta the selected vertices are fixed, and O_y\cap\{g_y\le1-\tau\} is an event of \xi, whose law has not changed. For bonds the additional crossing bit is independent and contributes a factor q. Summing these bounds gives

If S\ge Kc/2 and Z<Kc/2, some successful entrance has its center in A_\xi. Thus o reaches A_\xi. Integrating over \zeta and including the low-entry event from (4.2), we conclude that

Passing from the relay to the target. The estimate (4.5) is now under the original law. To control the remaining failure event, condition on \xi alone. Then A_\xi is a deterministic set, the remaining bits have their product law, and the conditional target probability of each v_y\in A_\xi is the number g_y>1-\tau used in its definition. Corollary 2.3 therefore gives

including the trivial case A_\xi=\varnothing. Integrating this bound, and splitting the desired failure event according to whether o reaches A_\xi, yields

Each of the four terms is less than \eta/4 by (3.4) and (3.5).□

Proof. By translation and a signed permutation of coordinates, we may suppose that c_v=0 and c_x=(20r+1,0,0). Thus

Indeed, the first-coordinate intervals of the two cubes are [-10r,10r]\cap\mathbb Z and [10r+1,30r+1]\cap\mathbb Z, whose union has no missing lattice vertices.

We construct rectangles P_0,\ldots,P_{13}, starting with P_0=B_v and ending with P_{13}\subseteq B_x, such that Lemma 4.1 applies with B=P_i and T=P_{i+1} for every 0\le i<13. At each translation, the required R-expansion of the starting rectangle is accommodated by increasing every half-width by R. We first shorten the rectangle in each of its three coordinate directions, leaving room for ten such increases before the final rectangle must fit inside B_x. Figure 2 shows these two stages, and Table 1 records the thirteen target rectangles and the radii and orientations used to choose the quarter-faces.

Three contraction steps. For t=1,2,3, let P_t be centered at zero with coordinate half-widths

Fix u\in P_{t-1}^{(R)}. Its coordinate bounds are 2r+tR in directions h<t and 4r+tR in directions h\ge t. In the cube \Lambda_{2r}(u), choose a quarter-face normal to coordinate t, with its normal sign and both transverse signs directed toward coordinate zero. At a zero coordinate, either sign may be used.

In the normal direction, the face coordinate has absolute value at most

In a transverse direction, the face coordinate ranges between a number a and a-2r\operatorname{sign}(a), with either sign allowed when a=0. Its absolute value is therefore at most \max\{|a|,2r\}, which fits the corresponding half-width in (5.5). The chosen quarter-face is consequently contained in P_t.

The full cube \Lambda_{2r}(u) has all coordinate absolute values at most 6r+3R<10r, by (5.1), and so lies in D. In particular P_{t-1}^{(R)}\subseteq D. Since o\notin D, the remaining geometric hypothesis of Lemma 4.1 is also satisfied. This proves its applicability to all three contraction steps. The resulting rectangle is

Ten translation steps. Define the step lengths and centers by

For 1\le i\le10, set

The R-expansion of the preceding rectangle, P_{2+i}^{(R)}, is centered at z_{i-1} and has half-width w_i. Fix u in that expansion. In \Lambda_{s_i}(u) choose the quarter-face with forward normal in coordinate 1, and with both transverse signs directed toward zero. The normal coordinate on this face is u_1+s_i. Relative to the new center z_i, its offset is exactly u_1-(z_{i-1})_1, of absolute value at most w_i. Transverse absolute coordinates are at most \max\{w_i,s_i\}=w_i. The equality also holds for the last step, because 13R\ge1. Hence this quarter-face is contained in P_{3+i}.

To check containment of the full radius-s_i cube, note that 0\le(z_{i-1})_1\le18r, w_i\le2r+13R, and s_i\le2r+1. Its first coordinate is therefore between

and its transverse absolute coordinates are at most 4r+13R+1. Condition (5.1) gives 13R+1<6r and 13R<8r, so these bounds lie inside the prism (5.4). It follows again that the preceding expanded rectangle lies in D and avoids o. The radii used are 2r and 2r+1, both allowed by Lemma 4.1. Thus all ten translation steps satisfy that Lemma’s hypotheses.

The final center is z_{10}=(9(2r)+(2r+1),0,0)=c_x, and the final half-width is w_{10}=2r+13R<4r. Consequently P_{13}\subseteq B_x. If o is connected to P_0 but not to P_{13}, then for at least one i\in\{0,\ldots,12\} it is connected to P_i but not to P_{i+1}. A union bound and thirteen applications of Lemma 4.1 now give

No independence between these thirteen connection events is required.□

Proof. The initialization fixes finitely many bits and leaves the others independent with parameter q. At every later step, the preceding revealed values determine which finite set of bits is exposed. Conditioning on the values of this selected set again leaves the remaining bits with their product law. The classifications, queue, parent assignments, and numbers b_x are all functions of revealed values. They therefore add no conditions on the remaining bits. Induction proves the first assertion.

When x is assigned parent v, its graph G(x) is precisely the graph G' used to compute b_x. The rule for declaring v good therefore establishes (6.1) for x at that time. To prove persistence, it suffices to verify that processing other vertices cannot expose any of the unknown bits of H_x.

All ancestor cubes and their connecting interfaces have already been revealed. Thus the unknown bits of H_x lie in Q_x or, for bonds, on I_{vx}. The cubes are vertex-disjoint, so another vertex’s processing does not reveal an internal bit of Q_x. Each step also reveals only the processed vertex’s incoming parent interface. Distinct parent links use distinct interfaces. Moreover, a pending vertex has no children, since only processed good vertices acquire them. Hence I_{vx} cannot be revealed by another step while x is pending. If this interface was prescribed at initialization because v is the root, its fixed values simply remain part of the history.

Consequently, until x is processed, the known bits of H_x stay fixed and its unknown bits retain the same product law. Its conditional connection probability is unchanged. Together with the initial verification, this proves (6.1) at every step.□

Proof. Condition on a positive-probability history immediately before processing v. Let \mathcal F denote this history and \mathcal F^+ the history after the prescribed reveal at v. The unvisited neighbors to be tested are already determined by \mathcal F.

Fix one such neighbor x and the corresponding graph G'. Under the conditioning on \mathcal F, every bit internal to the prism D=Q_v\cup Q_x has its fresh parameter-q law. To check this carefully, neither cube has been processed: v is pending and x is unvisited. Their interface has not been revealed as a parent link, since that would require x to have been visited or v to have been processed. Neither vertex is the root, so their interface is not one prescribed by initialization. Although an initialized root interface may meet Q_v, it is external to D. Lemma 6.1 gives the required independence.

The graph G' contains every edge internal to this prism, and o lies outside it in the disjoint root cube. All exterior bits have independent laws, with probabilities 0 or 1 for known bits and q for unknown bits. Thus Lemma 5.1 applies. If C_x=\{o\leftrightarrow B_x\text{ in }G'\}, it gives

because H_v implies a connection to B_v in the larger graph G'. Notice that the relay estimate is applied before revealing Q_v, not after conditioning on H_v.

The event H_v is determined by \mathcal F^+, and b_x=\mathbb P_{\mathcal I}(C_x\mid\mathcal F^+). The tower property therefore yields

On H_v\cap\{b_x\le1-\delta\} the integrand is at least \delta, so

There are at most four tests. The promise and a union bound now give

where the last inequality is (3.4). No independence between the tests is needed.□

Proof. The assertion is immediate if the set contains the root, which is declared good. Otherwise, fix such a set S. For 1\le j\le k, let T_j be the processing time of the jth member of S to be processed, and set T_j=\infty if fewer than j members are ever processed. Let E_j be the event that T_j<\infty and these first j members are all declared bad; put E_0 equal to the whole sample space.

For each finite time t, the event

is determined before the reveal at time t. Indeed, at that moment one knows the next vertex, how many members of S have already been processed, and whether all of those members were bad. On \{T_j=t\} there are exactly j-1 such previous members, so these observations determine E_{j-1} there. After termination we keep the history constant; events specifying a later processing time are empty. Applying Lemma 6.2 at time t and summing gives

Iteration yields \mathbb P_{\mathcal I}(E_k)\le f^k. Since no vertex is processed twice, E_k is exactly the event in the statement. The proof does not assume that every member of S is eventually processed.□