The Setting
A coarse exploration tests vertices of using connections in finite subgraphs of the nearest-neighbor lattice . The test at a vertex depends on the observations already made and on a finite set of newly revealed variables. The bad events concern rejection of specified vertices during this exploration.
Fix a model , either bond or site percolation. A lattice bond joins to its positive coordinate step , where is the th coordinate unit vector.✦ Bond endpoint incidence relates a lattice bond to the pair of vertices and , in either order.✦ A configuration assigns each bond, in the bond model, or each vertex, in the site model, a state in , with meaning open.✦ Open lattice adjacency means nearest-neighbor adjacency with the joining bond open, or with both vertices open, respectively.✦ A vertex is available unconditionally in the bond model and precisely when it is open in the site model.✦
A lattice box in is a coordinate interval with ordered lower and upper corners.✦ Its vertices include the boundary, and its bonds have both endpoints in the box. Write for its bonds or vertices according to .✦ A finite lattice subgraph has finite vertex and bond sets, with both endpoints of each bond in ; write for its percolation variables. The underlying simple graph of a finite lattice subgraph is the graph with vertex set and adjacency given by bond endpoint incidence.✦ Open connectivity $\xleftrightarrow[G]{\omega}$ is the relation on vertices of given by paths within : successive vertices share an open bond in the bond model and are adjacent open vertices in the site model.✦ A bond path of length zero connects a vertex to itself; a site path of length zero requires that vertex to be open. A connection from to a target means a connection within to some vertex of .✦ A lattice box is contained in a finite lattice subgraph when both its vertices and its bonds belong to .✦
For a lattice center and coordinate radius , the lattice cube is the coordinate interval in (1).✦ For a coarse vertex , the center and the relay and surrounding cubes at scale are also specified there. (1) The four coarse directions have outward unit vectors equal to in that order.✦ For coarse vertices , the interface is the set of lattice bonds with one endpoint in and the other in .✦ The interbox variables are for bonds and the empty set for sites.✦ The block variables , root variables , and processed region variables for finite are the finite sets in (2). (2)
Scale Parameters and Conditioned Laws
For a family of opening probabilities, is the independent Bernoulli product measure on configurations.✦ Write when all parameters equal . A finite observation history consists of a finite known set and a configuration whose values on record the observations.✦ The finite pattern consists of configurations agreeing with on .✦ Pinning to this pattern gives the parameters in (3)✦; the history-conditioned law is . (3) For configurations and a finite set of percolation variables, the partial replacement is the configuration equal to on and to elsewhere.✦ For a finite observation history , the extension by observations on a finite set is the history .✦
A quarter-face index is a pair consisting of a coordinate and a choice of sign for each coordinate.✦ For a lattice center , a radius , and a quarter-face index , the quarter-face of is the set of lattice vertices in (4).✦ These 24 signed-coordinate quarter-faces may overlap on their boundaries. (4) For radii , a lattice center , and a target set , the confined seed connection event consists of configurations with an available vertex in connected to a vertex of by open lattice adjacencies restricted to .✦ Restricted adjacency requires both adjacent vertices to lie in this cube.✦
Admissible scale parameters consist of densities , error allowances , and integer scales satisfying (5). Here is the seed radius, the trial count, the seed variable count, and the contour error tolerance. The difference is taken in the nonnegative integers. (5)
The Exploration and Its Tests
A parent-chain packet consists of a coarse vertex , a parent , and a finite lattice graph containing and the lattice origin; write , , and for its components.✦ The root connection event of a parent-chain packet is the event in (6) of a connection within from the lattice origin to the relay cube .✦ $$A_t=\{\omega:\text{there is }y\in B_v\cap V_G \text{ with }0\xleftrightarrow[G]{\omega}y\}.$$(6) The child packet has vertex , parent , and the extended graph in (7), where and denote the vertex and bond sets of .✦ (7)
An exploration state consists of a finite history , a finite processed set , an ordered queue of packets, and finite good and bad sets .✦ The visited set of an exploration state is the set .✦ For an exploration state and a packet , the candidate list is the ordered list of children whose vertices are outside the visited set of , in direction order.✦ For an exploration state with a nonempty queue headed by , the set of unrevealed variables is ; when the queue is empty, .✦ The history after block revelation is , with value configuration .✦
Packet acceptance is the event in (8). (8)✦ The rejection indicator is zero for an empty queue and otherwise equals one precisely outside for its head .✦
A single exploration step replaces the history by , removes the queue head , and adds to the processed set. On acceptance it adds to the good set and appends to the queue; on rejection it adds to the bad set. An empty queue leaves the state unchanged. Let be the state after steps from , using the same configuration at every step and starting with .✦ The eventually bad vertex event is defined by (9). (9)✦
A colored state is an exploration state with and .✦ A valid state at is an exploration state whose processed set contains the origin, whose queued vertices are distinct and unprocessed, and whose queued parents are processed, subject also to (10).✦ (10)
Adaptive Reveal Schemes
An adaptive reveal scheme on variables , target labels , and states assigns to each state a finite reveal set , Bernoulli parameters , and either a current label or no current label. For each pattern it specifies a bad indicator and a next state . Its parameter update is the pinning condition in (11). Write for the event of agreement with on .✦ The pattern weight and bad outcome probability are also defined in (11). (11)
The timed bad target event , for finite , is the configuration event defined recursively in (12). Here , and in the last line. (12)✦ The coarse exploration scheme is an adaptive reveal scheme on exploration states, with reveal set , parameters from and , and the queue head’s vertex as its current label, with no current label for an empty queue. The zero extension of a revealed pattern on is the configuration equal to on and closed elsewhere. For the coarse exploration scheme at state and revealed pattern , the bad indicator is the rejection indicator evaluated at the zero extension , and the next state is the single exploration step evaluated at .
The Claim
Theorem 1. Fix a bond or site model and admissible scale parameters as in (5). Let be a valid exploration state at and let be finite and deterministic. Then (13)✦ If is also colored and , then (14)✦ For a general adaptive reveal scheme , let and let be a class of states with for every . Assume that whenever and . For and finite deterministic , (15)✦
In the paper, the result reads: for every deterministic set of distinct coarse vertices, the probability under the paper’s conditioned Bernoulli law that all are processed and declared bad is at most .
What Is Checked
The bounds (14) and (13) are stated over finite observation histories and valid bond or site exploration states with admissible scale parameters, with the coloring and empty initial bad set required in (14); the bound (15) is stated over adaptive reveal schemes and classes of states closed under transitions of positive pattern weight.
The graph of a child packet contains the original packet graph, the surrounding cube at the child vertex, and the lattice origin.