The Setting
An adaptive exploration processes vertices of while revealing finite blocks of percolation variables on . A pending vertex carries a finite graph in which an open connection from the origin to a relay cube is tested.
Fix a model , either bond or site percolation. The cubic lattice consists of integer triples.✦ Write for its coordinate unit vectors, with ; the positive coordinate step from is , and nearest-neighbor vertices differ by or . A lattice bond has endpoints and .✦ The variable set consists of these bonds in the bond model and of lattice vertices in the site model.✦ A configuration assigns an open or closed state to every variable.✦
Open lattice adjacency requires the intervening bond to be open in the bond model, and both nearest-neighbor vertices to be open in the site model.✦ A vertex is available unconditionally in the bond model and precisely when it is open in the site model.✦ On any graph, open site adjacency requires adjacent open vertices; open site connectivity requires a finite path of such adjacencies and open endpoints, including for a path of length zero. A bond path of length zero connects a vertex to itself. Adjacency restricted to a region requires both vertices of each step to belong to that region.✦
A finite lattice graph has a finite vertex set and a finite bond set whose endpoints belong to .✦ The underlying simple graph of a finite lattice graph is the graph that joins two vertices when they are incident to one of the bonds of , in either order.✦ Open bond adjacency in uses an open bond of , and open connectivity in uses finite paths in this graph under the chosen model. For and , the target connection means an open connection in to some vertex of .✦ Write for the graph variables, namely in the bond model and in the site model.✦
For any variable set and parameter family , let be the independent Bernoulli product measure with opening probability at coordinate .✦ The notation denotes constant opening probability .
Coarse Packets
A lattice box has coordinatewise ordered corners and contains the integer vertices satisfying for every . The bonds of a lattice box are lattice bonds whose endpoints both belong to . Write for its bonds or vertices, according to .✦ A graph contains when it contains all these vertices and bonds.✦ The cube of coordinate radius centered at , and the coarse embedding and cubes at scale , are given in (1), where is a coarse lattice point: (1)
The four coarse directions have outward steps , , , and . For coarse vertices , let be the finite set of lattice bonds with one endpoint in and the other in .✦ The interbox variables equal for bonds and the empty set for sites.✦ The block variables and root variables are the finite sets in (2): (2) For a finite set , the processed region variables are in (3): (3)✦
A parent-chain packet at scale is a triple consisting of a coarse vertex , a coarse parent vertex , and a finite lattice graph containing and the origin.✦ For a parent-chain packet , the root connection event is the event defined by .✦ For a coarse point , the child packet has vertex , parent , and extended graph with vertex set and bond set .✦
Scale Parameters
The seed variable count is .✦ A quarter-face index is a pair consisting of a coordinate and a sign vector .✦ The quarter-face associated with coordinate and sign vector is the set of lattice vertices defined by (4); these 24 signed-coordinate quarter-faces may overlap on their boundaries: (4)✦
The confined seed connection event consists of configurations having an available vertex joined to some by a finite path of open lattice adjacencies restricted to .✦
Scale parameters for are densities and , allowances , and nonnegative integer scales with , , , and . They satisfy the budgets in (5), with fixed contour error tolerance , and the face connection requirement (6): (5) (6)
Histories and Revelations
A finite observation history on records a finite known set and a configuration whose values on are the observations.✦ Partial replacement uses on and elsewhere; this is the configuration frozen on . For a finite reveal set , observing gives .✦
For an event , the pinned parameters and finite-coordinate conditional probability are defined in (7). The history-product law uses with : (7) An event is determined by when configurations agreeing on have the same membership in ; more generally a function is determined by when its value is unchanged between such configurations.✦ The pattern is the event .✦ The zero extension of an assignment is the configuration on that agrees with on and is closed elsewhere.✦
A coarse exploration state at scale consists of a history on , a finite processed set , an ordered packet queue , and finite good and bad sets of coarse vertices.✦ The visited set of a coarse exploration state is the set defined by .✦ The unrevealed block of a coarse exploration state is the finite set given by when its queue has head , and by when its queue is empty.✦ The history of a coarse exploration state after block revelation at is the finite observation history given by ; write for its value assignment.✦
The candidate list consists, in direction order, of the children whose vertices lie outside .✦ Packet acceptance is the event in (8): (8)✦ The rejected packet indicator is one when the queue has head and , and zero otherwise.✦ The frozen packet event is .✦
The single exploration step replaces the history by and, for a nonempty queue with head and tail , processes . Acceptance appends to and puts in the good set; rejection leaves queue and puts in the bad set. An empty queue leaves the state unchanged.
A state is valid at when the origin is processed, queued vertices are distinct and unprocessed, every queued parent is processed, and (9) holds: (9)✦
Adaptive Decisions
An adaptive reveal scheme on variables and states specifies a finite reveal set , product parameters , an optional current vertex, and, for each assignment , a bad decision and a successor state . The successor parameters are obtained from by pinning to . For an adaptive reveal scheme at state , the pattern weights and bad mass are the probabilities and weighted sum defined in (10), with : (10)
The coarse exploration reveal scheme at uses and the history-product parameters of . Its current vertex is the head vertex when the queue is nonempty, its bad decision is , and its successor is . Denote its bad mass by .
The Claim
Theorem 1. For any coarse exploration state , , and , the bad mass satisfies (11): (11)✦
Take scale parameters for and a state valid at . Suppose its queue has head , and is unvisited. The relay failure estimate is (12): (12)✦ For every valid state at these scale parameters, (13) holds: (13)✦
Let be a variable set, , and finite, and let be a real number. Suppose is determined by , is measurable, , and . Then the finite-coordinate conditional failure estimate is (14): (14)✦
In the paper, the result reads: immediately before any pending vertex of the exploration is processed, its conditional probability of being declared bad is less than .
What Is Checked
The statements concern finite graph packets containing the origin and their assigned cubes, valid coarse exploration states, and Bernoulli product laws with finitely many pinned coordinates.