In this paper we consider a connected planar graph and impose conditions that results in having a percolation lattice-like cellular structure. Assigning each cell of to be either occupied or vacant, we describe the outermost boundaries of star and plus connected components in . We then consider the dual graph of and impose conditions under which the dual is also a percolation lattice. Finally, using and its dual, we construct vacant cell cycles surrounding occupied components and study left right crossings and bond percolation in rectangles.
The structure of the outermost boundary of finite components is crucial for contour analysis
problems of percolation [
In many applications, it might happen that the lattice on which percolation occurs is not
necessarily regular, like for example percolation in Voronoi tessellations [
The paper is organized as follows: In Section 2, we define generalized percolation lattices and describe the cellular structure of such lattices in Theorem 1 and in Section 3 we study outermost boundaries of star and plus connected components in generalized percolation lattices. Next, in Section 4, we define the dual graph to a percolation lattice and describe conditions under which the dual graph has the properties of a percolation lattice. Following this, we use dual lattices to study vacant cycles of cells surrounding plus and star connected components. Finally in Section 5, we study left right crossings of generalized percolation lattices in rectangles.
Let = (, ) be any connected finite planar graph in R2 where each edge is a straight line segment. Two vertices 1 and 2 are said to be adjacent if they share an edge in common. Two edges 1 and 2 are said to be adjacent if they share a vertex in common. A subgraph = (1, . . . , ) ⊆ is said to be a walk if is adjacent to +1 for 1 ≤ ≤ − 1. If = (, +1) is the edge containing end-vertices and +1, we also represent = (1, . . . , − 1) and say that 1 and are end-vertices of . We say that is a circuit if is a walk and 1 = . We say that is a path if is a walk and all the vertices in are distinct. Finally, we say that is a cycle if is a path and 1 = .
For a cycle ∈ , let = () be the bounded open set whose boundary is . We define the interior of to be and the closed interior of to be ∪ . We also define the exterior of to be ( ∪ ) and the closed exterior of to be . We say that the graph is a percolation lattice if every edge in belongs to a cycle. We say that a cycle in is a cell if there exists no point of an edge of in the interior of . By definition any two distinct cells 1 and 2 have mutually disjoint interiors and the intersection 1 ∩ 2 is either empty or a union of vertices and edges in . Any edge of belongs to at most two cells and we say that is unicellular if there is at most one cell containing as an edge.
The following intuitive result captures the main features of percolation lattices as studied
in [
Theorem 1. If is a percolation lattice, then there are distinct cells 1, 2, . . . , such that
= ⋃︁ .
=1 (2.1) Moreover, the representation (2.1) is unique in the sense that if 1, . . . , are cells such that = ⋃︀ =1 , then = and {}1≤ ≤ = {}1≤ ≤ .
The following additional properties hold: (1) For every edge , there are at most two cells containing as an edge. (2) If is contained in the closed interior of a cycle ∈ , then there are two cells containing as an edge and both cells lie in the closed interior of . If is contained in the closed exterior of , then all cells containing lie in the closed exterior of . (3) There are cycles Δ1, Δ2, . . . , Δ with mutually disjoint interiors such that every cell in is contained in the closed interior of one of these cycles. For any ̸= , the cycles Δ and Δ have at most one vertex in common and an edge ∈ is unicellular if and only if belongs to some cycle in {Δ}.
In Figure 1(), we illustrate the above result using a percolation lattice containing 4 cells 1, 2, 3 and 4.
For completeness, we prove Theorem 1 using the following auxiliary result regarding merging of two cycles that is of independent interest and used throughout the paper.
Proposition 1. Let and be cycles in the graph that have more than one vertex in common. There exists a unique cycle consisting only of edges of and with the following properties: () The closed interior of contains the closed interior of both and . () If an edge belongs to or , then either belongs to or is contained in its closed interior.
Moreover, if contains at least one edge in the closed exterior of , then the cycle also contains an edge of that lies in the closed exterior of .
The above result essentially says that if two cycles intersect at more than one point, there is an
innermost cycle containing both of them in its interior. For illustration, we refer to Figure 2()
where two cycles and ℎ have the edge and the vertex in common. The
merged cycle contains both the smaller cycles in its closed interior. Analogous to [
Proof of Proposition 1: Let ⊂ be any path that has its end-vertices in the cycle 0 := and lies in the exterior of 0 (for illustration see Figure 2() where = and = ). Letting = ⊂ the cycle 1 := ∪ then contains the cycle = 0 in its interior. We then repeat the above procedure with the cycle 1 and look for another path 1 ⊂ that lies in the exterior of 1 and has end-vertices in 1. Arguing as before, we get a cycle 2 that contains 1 as a subpath and has the cycle in its closed interior. This procedure continues until we obtain a cycle that does not contain any edge of in its exterior.
We argue that is the desired cycle . By construction both and are contained in the closed interior of and consists of only edges of and so () and () are true. Moreover, each cycle , 1 ≤ ≤ contains an edge of that lies in the closed exterior of . The uniqueness of is also true since if 1 ̸= is any edge satisfying () − () and 1 contains an edge of in its closed exterior, then some edge of or is present in the closed exterior of 1, a contradiction.
Proof of Theorem 1: Let 1, . . . , be the set of all cycles containing = (, ) as an edge. We shrink the cycles in an iterative manner as follows. Let 0 := 1 and suppose there exists some point of an edge of the cycle , ≥ 2 in the interior of 0. Because the graph is planar, there exists a path 1 ⊂ present in the closed interior of 0. We shrink the cycle 0 to the cycle 1 containing the edge and the path 1. For illustration we again use Figure 2() with 0 = 1 = and 2 = . In this case 1 = and 0 = . The “shrinked" cycle 1 = contains every edge 1. We now repeat the above procedure with the cycle 1 and proceed iteratively to finally obtain a cycle that does not contain any point of ⋃︀ =1 in its interior.
The cycle =: is a cell containing the edge . If there exists a cycle such that and have mutually disjoint interiors, then we repeat the above procedure starting with the cycle and obtain another cell , also containing as an edge. By construction and have mutually disjoint interiors and for any cycle we have that either or is contained in the closed interior of . The set of all distinct cells in {}∈ ⋃︀{}∈ is the desired cellular decomposition (2.1) of . The decomposition (2.1) is unique since every must necessarily be one of 1, . . . , .
The proof of (1) and the proof of (2) for present in the closed exterior of , follow from the above construction. To prove the remaining part of (2), suppose that is present in the closed interior of . Since is a percolation lattice, there exists a cycle ∈ containing as an edge. This cycle contains an edge in the closed interior of and therefore a path ⊂ with end-vertices , ∈ contained in the closed interior of . Let 1 and 2 be the two paths with end-vertices , that form the cycle . For reference, in Figure 2(), we have = , = , 1 = , 2 = and = . The cycles ∪ 1 and ∪ 2 have mutually disjoint interiors and so arguing as before, we obtain two cells and containing as an edge. By construction both and are contained in the interior of .
The cycles in (3) are obtained by repeatedly merging cells in as follows: We first pick one cell 1 and using Proposition 1, merge 1 with another cell, say 2, that shares an edge with 1 to get a new cycle 12. We then pick another cell, say 3, that shares an edge with 12 and lies in the exterior of 12 and merge these together to get a new cycle 123. Continuing this way, we get a cycle Δ1 satisfying the property that no cell in { } lying in the exterior of Δ1 shares an edge with Δ1. If there still exists cells in the exterior of Δ1, then because is connected, one of these exterior cells (call it 21) necessarily shares a vertex with Δ1. We then repeat the above procedure starting with the cell 21. Continuing this way until all cells are exhausted, we get the desired cycles Δ, 1 ≤ ≤ .
Finally, if is unicellular and is contained within Δ, then the cell necessarily shares the edge with Δ. This completes the proof of (3).
Let be a percolation lattice with cellular decomposition = ⋃︀ =1 as in (2.1). We have the following definition of star and plus adjacency.
Definition 1. We say that two cells 1 and 2 in are star adjacent if 1 ∩ 2 contains a vertex in and plus adjacent if 1 ∩ 2 contains an edge in .
We assign every cell , 1 ≤ ≤ , one of the two states, occupied or vacant and assume that there exists an occupied cell 0 containing the origin. We say that the cell is connected to the cell by a star connected − path if there is a sequence of distinct cells (1, 2, ..., ), ⊂ {}, 1 ≤ ≤ such that is star adjacent to +1 for all 1 ≤ ≤ − 1 and 1 = and = . If all the cells in {}1≤ ≤ are occupied, we say that is connected to by an occupied star connected − path.
Let (0) be the collection of all occupied cells in {}1≤ ≤ each of which is connected to the cell 0 by an occupied star connected − path. We say that (0) is the star connected occupied component containing the origin and let {}1≤ ≤ ⊂ { } be the set of all the occupied cells belonging to the component (0).
To define the outermost boundary of (0), we begin with a few preliminary definitions. Let 0 be the graph with vertex set and edge set, respectively being the vertex set and edge set of the cells {}1≤ ≤ = (0). An edge ∈ 0 is a said to be boundary edge if is unicellular or is adjacent to a vacant cell. (By definition, is already adjacent to an occupied cell of the component (0)). We have the following definition.
Definition 2. We say that the edge in the graph 0 is an outermost boundary edge of the component (0) if the following holds true for every cycle in 0 : either is an edge of or is in the closed exterior of .
We define the outermost boundary 0 of (0) to be the set of all outermost boundary edges of 0.
Thus outermost boundary edges cannot be contained in the interior of any cycle in the graph 0. We have the following result regarding the outermost boundary of the star component (0).
Theorem 2. There are cycles 1, 2, . . . , ⊆ satisfying the following properties: () An edge ∈ 0 if and only if ∈ ⋃︀=1 . () The graph ⋃︀ =1 is a connected subgraph of 0. () If ̸= , the cycles and have disjoint interiors and have at most one vertex in common. () Every occupied cell ∈ (0) is contained in the interior of some cycle . () If ∈ for some , then is a boundary edge belonging to an occupied square of (0) contained in the interior of . If is not unicellular, then also belongs to a vacant cell lying in the exterior of all the cycles in 0.
Moreover, there exists a circuit containing every edge of ∪1≤ ≤ .
The outermost boundary 0 is a connected union of cycles satisfying properties () − ()
and is therefore an Eulerian graph with denoting the corresponding Eulerian circuit (see
Chapter 1, [
(a) (b)
To prove Theorem 2, we use the following Proposition also of independent interest. Proposition 2. For every occupied cell ∈ (0), 1 ≤ ≤ , there exists a unique cycle in 0 satisfying the following properties. () The cell is contained in the closed interior of . () Every edge ∈ is a boundary edge adjacent to an occupied cell of (0) present in the closed interior of . If is not unicellular, then is also adjacent to a vacant cell present in the closed exterior of . () If is any cycle in 0 that contains in the interior, then every edge in either belongs to or is contained in the interior.
Every edge of is also an outermost boundary edge in the graph 0 and so we denote to be the outermost boundary cycle containing the cell ∈ (0). For example in Figure 3(), the outermost boundary cycle containing the cell is the cycle 1 = .
Below we prove Proposition 2 and Theorem 2 in that order.
Proof of Proposition 2: Let ℰ ̸= ∅ be the set of all cycles in the graph 0 satisfying property (); i.e., if ∈ ℰ then in present in the closed interior of . The set ℰ is not empty since is itself a cycle containing in its closed interior and so belongs to ℰ . Moreover if 1 and 2 are any two cycles in ℰ , then it cannot be the case that 1 and 2 have mutually disjoint interiors since both 1 and 2 contain the cell in its closed interior. Thus it is possible to merge 1 and 2 using Proposition 1 to get a new cycle 3 ∈ ℰ that contains both 1 and 2 in its closed interior. Continuing this way, we obtain an “outermost cycle" that contains all the cycles of ℰ in its closed interior.
By construction, the cycle satisfies properties () and (). To see that () also holds, suppose there exists an edge ∈ that is not a boundary edge. Since belongs to the graph 0, the edge is adjacent to an occupied cell 1 ∈ {}. But since is not a boundary edge, there exists one other cell 2 ∈ {} ∖ 1 containing as an edge and moreover 2 is also occupied. One of these cells, say 1, is contained in the interior of and the other cell 2, is contained in the exterior.
The cell 2 and the cycle have the edge in common and thus more than one vertex in common. We then use Proposition 1 to obtain a larger cycle ̸= containing both and 2 in its closed interior. This is a contradiction to the fact that satisfies property (). Thus every edge of is a boundary edge. By the same argument above, we also get that the edge cannot be adjacent to an occupied cell in the exterior of the cycle . Thus is adjacent to an occupied cell in the interior of and a vacant cell (if it exists) in the exterior.
Proof of Theorem 2: We argue that the set of distinct cycles in the set := ∪1≤ ≤ {} obtained in Proposition 2 is the desired outermost boundary 0 and satisfies the properties () − () mentioned in the statement of the theorem.
To prove (), it sufices to see that every edge in the union of the cycles = ∪1≤ ≤ {} is an outermost boundary edge. This is because, by definition, no edge with an end-vertex present in the interior of some cycle in can be an outermost boundary edge. Now, suppose some edge ∈ has an end-vertex in the interior of some cycle ⊆ 0. This necessarily implies that at least one edge of is present in the exterior of and moreover and cannot have a single common vertex. Therefore it is possible to merge and using Proposition 1 to get a bigger cycle ⊂ containing in its closed interior, a contradiction to the construction of . This completes the proof of ().
To prove (), we first see that the graph 0 formed by the vertices and edges of the component (0), is connected. Indeed, let 1 and 2 be vertices in 0 so that each , = 1, 2 is a corner of an occupied cell ∈ (0). By definition, there is a star connected cell path connecting 1 and 2, consisting only of cells in (0) and consequently, there exists a path in 0 from 1 to 2. Now let 1 and 2 be vertices in belonging to cycles 1 and 2 , respectively, for some 1 ≤ 1, 2 ≤ . By previous discussion, there exists a path 12 from 1 to 2 containing only edges of 0 and by construction, each such edge lies in the closed interior of some cycle in {}. This is true since all the occupied cells are present in some cycle in {}. For each sub-path ⊆ 12 that contains a point in the interior of some cycle and has end-vertices in , we replace with a path ⊆ (see Figure 3()). Iteratively replacing all such interior paths, we get a path from 1 to 2 containing only edges of {}. Thus the union of cycles is connected and this proves ().
Property () is true since otherwise we could merge the cycles and obtained in Proposition 2 to get a larger cycle containing both and in its closed interior, a contradiction to the fact that satisfies property () in Proposition 2. Indeed for any occupied cell ∈ (0) the corresponding outermost boundary cycle satisfies property () of Proposition 2 and so () is true. Moreover if ∈ is any edge, then using the fact that satisfies property () of Proposition 2, we get that the edge satisfies property ().
Finally, to obtain the circuit containing the outermost boundary, we first compute the cycle graph as follows. Let 1, 2, ..., be the distinct outermost boundary cycles in . Represent by a vertex in . If and share a corner, we draw an edge (, ) between and . Since the union of cycles , 1 ≤ ≤ is connected, we get that is connected as well.
Let be any spanning tree of and consider an increasing sequence of tree subgraphs {1} = 1 ⊂ 2 ⊂ . . . = . The graph 1 contains a single vertex {1} and so we set Π1 = 1 to be the circuit obtained at the end of the first iteration. Having obtained the circuit Π, let +1 ∈ +1 ∖ be adjacent to some leaf ∈ . This implies that the cycle +1 shares a vertex with the cycle . Since the circuit Π contains , we assume that is the starting and ending vertex of Π and also of +1 . The concatenation of Π and +1 is the desired circuit Π+1. Continuing this way, the final circuit Π obtained is the desired circuit .
The techniques used in the previous sections also allows us to obtain the outermost boundary for plus connected components. We recall that cells and are said to be plus adjacent if they share an edge between them. We say that the cell is connected to the cell by a plus connected − path if there is a sequence of distinct cells ( = 1, 2, ..., = ) ⊆ {}1≤ ≤ such that is plus adjacent to +1 for all 1 ≤ ≤ − 1. If all the cells in {}1≤ ≤ are occupied, we say that is connected to by an occupied plus connected − path.
Let +(0) be the collection of all occupied cells in {}1≤ ≤ each of which is connected to the occupied cell 0 containing the origin, by an occupied plus connected − path. We say that +(0) is the plus connected occupied component containing the origin. Further we also define 0+ to be the graph with vertex set being the set of all vertices of the cells of {} present in +(0) and edge set consisting of the edges of the cells of {} present in +(0).
Every plus connected component is also a star connected component and so the definition of outermost boundary edge in Definition 2 holds for the component +(0) with 0 replaced by 0+. We have the following result.
Theorem 3. The outermost boundary 0+ of +(0) is unique cycle in 0+ with the following properties: () All cells of +(0) are contained in the interior of 0+. () Every edge in 0+ is a boundary edge adjacent to an occupied cell of +(0) contained in the interior of 0+ and a vacant cell in the exterior.
This is in contrast to star connected components which may contain multiple cycles in the outermost boundary. In Figure 3() for example, the union of the cells and forms a plus connected component whose outermost boundary is the cycle .
Proof of Theorem 3: Proposition 2 holds with (0) replaced by +(0). Since +(0) is plus connected, the outermost boundary cycle 0 the cell 0 in its interior also contains all the cells of +(0) in its interior. Therefore cycle 0 satisfies the conditions () and () in the statement of the theorem, is unique and so 0+ = 0. 4. Vacant cell cycles surrounding occupied components In this section, we study vacant cycles of cells surrounding occupied star and plus components. We therefore begin with a discussion of the dual lattice. Let be any percolation lattice and let = ⋃︀
=0 be the cellular decomposition of .
Definition 3. We say that a graph is dual to if the following conditions hold: (1) Every cell in contains exactly one vertex of in its interior.
Suppose vertex ∈ is the present in the interior of the cell () of . (2) Vertices 1, 2 ∈ are adjacent if and only if the cells (1) and (2) are plus adjacent.
To study the similarity between and , we would like to first ensure that the dual graph is also a percolation lattice, i.e., we prefer that is connected, planar and each edge of belongs to a cycle. This is because, there are in fact dual graphs that satisfy exactly two of these three properties. For example, consider two plus adjacent squares 1 and 2 of same side length, to be the graph . If we let the centres of 1 and 2 be the vertex set of , then the edge set of is the single edge joining the centres of 1 and 2. The graph is connected and planar but acyclic. In Figure 4 (), we have an example of a graph (denoted by solid lines) and the corresponding dual graph (denoted by the dotted lines). The graph is connected and every edge of belongs to a cycle but is not planar. In Figure 4 (), the dual graph is planar and every edge of belongs to a cycle but is not connected.
Throughout the paper, we assume that the graph admits a dual graph satisfying the following properties: (1) (Niceness property) The percolation lattice is nice in the sense that any two plus adjacent cells in share exactly one edge in common and no other vertex. (2) (Interior edge property) Any edge (1, 2) ∈ is present in the interior of the cycle formed by merging the plus adjacent cells (1) and (2). (3) The dual graph is a connected and planar percolation lattice and is dual to . (4) The dual graph satisfies the niceness and interior edge property. (5) If is a vertex of the dual cell () and () is the cell in containing , then is a vertex of ().
Thus and have similar cellular structure. For example, the usual square lattice on the plane satisfies properties (1) − (5).
Let be a percolation lattice with cellular decomposition ⋃︀ =0 and let be a lattice dual to satisfying properties (1)− (5) and having cellular decomposition = ⋃︀ =0 . We say that the sequence = (1, ..., ) is a plus connected cell path in if for each 1 ≤ ≤ − 1, the cell is plus adjacent with the cell +1. We say that is a plus connected cell cycle if is adjacent to − 1 and +1 for each 1 ≤ ≤ with the notation that +1 = 1. Analogous definition holds for star connected paths and cycles.
Let (0) = ⋃︀
=0 be the star connected occupied cell component containing the cell 0 with origin in its interior. By definition, every cell in (0) is connected to 0 by a star connected cell path. We have the following result.
Theorem 4. Suppose properties (1) − (5) hold and suppose every vertex in the component (0) is present in the interior of some dual cell of .
There exists a unique cycle = (1, . . . , ) ⊂ such that each vertex is present in the interior of a vacant cell and satisfies the following properties: () For every , 1 ≤ ≤ , the cell is vacant and star adjacent to some occupied cell in (0). () All occupied cells in (0) are contained in the interior of . () If ̸= is any other cycle in that satisfies () − () above, then is contained in the closed interior of .
The sequence of cells in (1, . . . , ) form a plus connected cycle of vacant cells surrounding the star connected component (0). In Figure 5, the two cells containing the circles form the star connected occupied component. Every other cell is vacant. The two dual cycles 12345671 and 1234598671 both satisfy () − () and = 12345671.
Proof of Theorem 4: Let 0 denote the outermost boundary of the star connected component (0) in the percolation lattice . From Theorem 2 we have that 0 = ∪1≤ ≤ is a connected union of cycles {} with mutually disjoint interiors and moreover, for ̸= , the cycles and have at most one common vertex.
If vertices 1, 2 ∈ are adjacent in the outermost boundary 0 of the component (0), then the corresponding dual cells (1) and (2) are plus adjacent (property (4). Also, because 0 is connected (see property () Theorem 2), the union of dual cells (0) := ⋃︁ ()
∈0 (4.1) is a plus connected component in the dual graph . Moreover, each edge of 0 is present in the interior of closed interior of the union of cells of (0). Using Theorem 3 we therefore have that the outermost boundary (0) of (0) is a single cycle in containing all cells of (0) in its closed interior and all edges of 0 in its interior. Here the dual outermost boundary (0) is obtained as follows. Every dual cell belonging to (0) is labelled 1 and every dual cell sharing an edge with a cell in (0) and not belonging to (0), is labelled 0. We then apply Theorem 3 with label 1 cells as occupied and label 0 cells as vacant.
Suppose 1, 2, . . . , are the vertices of the dual cycle (0) encountered in that order; i.e., the vertex 1 is adjacent to 2, the vertex 2 is adjacent to 3 and so on. Each vertex is a vertex of the dual cell () for some ∈ 0. Therefore if () is the cell in containing in its interior, then is a vertex of (), by property (5). Moreover () lies in the exterior of 0 and is adjacent to the vertex of (0). This implies that () must necessarily be vacant. This proves that the cycle (0) satisfies properties () − ().
To get a unique dual cycle satisfying properties () − (), we merge all dual cycles satisfying properties () − (). This is possible since any two dual cycles satisfying () − () both contain the cell 0 in their respective interiors and therefore cannot have mutually disjoint interiors.
In this subsection we let +(0) = ⋃︀
=0 be the plus connected occupied cell component containing the cell 0 with origin in its interior. By definition, every cell in +(0) is connected to 0 by a plus connected cell path and the outermost boundary 0+ of +(0) is a single cycle containing all the cells of +(0) in its interior. We have the following result. Theorem 5. There exists a star connected cell cycle ℳ = (1, . . . , ) ⊂ such that: () Each cell is vacant, lies in the exterior of 0+ and is plus adjacent to some occupied cell of +(0). () The outermost boundary of ℳ is a single cycle containing all the cells of ℳ ∪ +(0) in its interior.
The sequence of cells in (1, . . . , ) form a star connected cell cycle of vacant cells surrounding the plus connected component +(0).
Proof of Theorem 5: From Theorem 3, we have that the outermost boundary 0+ = (1, . . . , ) of +(0) is a single cycle containing all cells of +(0) in its interior. Moreover every edge of +(0) belongs to a occupied cell of +(0) and also to a vacant cell lying in the exterior of 0+. It is possible that multiple edges in 0+ belong to the same cell and so the sequence (1, 2, . . . , ) could have repetitions. In such a case, we remove recurring entries and assume without loss of generality that is star adjacent to +1 for 1 ≤ ≤ with the notation that +1 = 1.
The set of cells in Γ := (1, . . . , ) form a star connected component and we suppose that the sequence of cells (1, . . . , ) form a star connected cycle for some ≤ . The outermost boundary of is a connected union of cycles ⋃︀1≤ ≤ and contains every cell of in the interior of some . If some cell of +(0) is contained in the interior of , then because +(0) is plus connected, every cell of +(0) is contained in the interior of . Moreover, since and share at most one vertex in common, it must the case that = 1 and so the outermost boundary of the star cycle (1, . . . , ) is the single cycle 1.
If on the other hand, every cell of +(0) is contained in the exterior of every cycle of , then every edge of is the edge of some occupied cell of +(0) that lies in the exterior of . This implies that the outermost boundary 0+ of +(0) is contained in the strict exterior of every cycle in . But this contradicts the fact that each contains at least one edge of 0+ and so there is at least one edge of 0+ contained in the closed interior of some cycle of .
In this section, we study the mutual exclusivity of left right and top down crossings in a rectangle. As before we assume that the percolation lattice = ⋃︀ =0 and the dual lattice = ⋃︀= 0 satisfy properties (1) − (5) and the origin is the present in the interior of the cell 0.
For a fixed rectangle , we assume that the sides of are nicely covered by cells of as shown in Figure 6. Consider the edges 11 and 22 intersecting the left side of . The vertices 1 and 2 are connected by a path 1 (shown by dotted line) in the interior of . Similarly the vertices 1 and 2 are connected by a path 1 in the exterior of . The union 1 ∪ 1 ∪ {11, 22} forms the cell 1. We define 1, . . . , to be the left cells. Similarly, the cells 1, . . . , are top cells, the right cells are 1, . . . , and the bottom cells are 1, . . . , . Any cell contained in the closed interior of is called an interior cell.
The cells , , and each contain a corner of the rectangle and have a single vertex contained in the interior of the rectangle. These four cells, called corner cells, are not plus adjacent to any interior cell. As in Figure 6, we assume that the cell 1 is plus adjacent to 2 and and does not share a vertex with any other left, right,top or bottom cell. We make analogous assumptions for each of the left, right, top and bottom cells.
Finally, we also assume that the cells are nicely padded in the following way: Let ℒ be the infinite line containing the top side of and define ℒ, ℒ and ℒℎ analogously. If 1 is any cell intersecting ℒ and star adjacent to a cell intersecting and 2 is any cell intersecting ℒ and star adjacent to a cell intersecting , then 1 and 2 are not star adjacent. A similar assumption holds for cells intersecting ℒ and ℒℎ.
Assuming that is nicely covered and padded as described above, we have the following definition of left right crossings.
Definition 4. A plus connected cell path = (1, . . . , ) ⊂ { }, ≥ 3 is said to be a plus connected left right crossing of a rectangle if 1 is a left cell, the cell is a right cell and every , 2 ≤ ≤ − 1 is an interior cell.
By the nicely padded assumption, must contain at least one interior cell. Every interior cell is now assigned one of the following two states: occupied or vacant. If every interior cell in a left right crossing of is occupied, we say that is an occupied plus connected left right crossing of the rectangle . We denote +(, ) and +(, ) to be the events that the rectangle contains an occupied and vacant plus connected left right crossing, respectively.
We have a similar definition of plus connected top down crossings and denote +(, ) and +(, ) to be the events that the rectangle contains an occupied and vacant plus connected top down crossing, respectively. Replacing plus adjacent with star adjacent, we obtain an analogous definition for star connected left right and top down crossings. We have the following result.
Theorem 6. Suppose properties (1) − (5) hold and is nicely covered and nicely padded by cells as in Figure 6. Also suppose that every vertex of a cell intersecting is present in the interior of a dual cell and that there is at least one plus connected left right crossing and one plus connected top bottom crossing. We have the following. () One of the events +(, ) or * (, ) always occurs but not both. () One of the events * (, ) or +(, ) always occurs but not both.
The above result describes the mutual exclusivity of occupied and vacant left right and top down crossings in any rectangle.
We prove the following three statements. ( ) The events * (, ) and +(, ) cannot both occur simultaneously. () If * (, ) does not occur, then +(, ) must necessarily occur. () If +(, ) does not occur, then * (, ) occurs.
Using () − () and the fact that a top down crossing of is a left right crossing of the rectangle ′ obtained by rotating by ninety degrees around the centre, we then get Theorem 6.
Proof of (): Suppose there exists a star connected occupied left right crossing of and let Γ = (1, . . . , ) be a path in crossing from left to right so that 1 intersects the left edge of , the edge intersects the right edge of and each , 2 ≤ ≤ − 1 belongs to an interior occupied cell of . The path Γ divides the rectangles into two halves.
Suppose +(, ) also occurs and let = (1, . . . , ) be a vacant plus connected top bottom crossing where 1 is a top cell, is a bottom cell and every other is an interior cell. Let be the vertex of present in the cell so that := (1, 2, . . . , ) is a path in . We claim that the vertex 1 necessarily above Γ. This is because if 1 were to be present below Γ, then the cell 1 ∈ containing 1 in its interior also lies below Γ. Let 1 be the infinite line parallel to the left side of and containing the point 1. Since 1 is contained in the interior of 1, the some edge of 1 contains a point ∈ 1 lying above 1. Since Γ lies above 1, there exists ∈ Γ lying above (see Figure 7 () for illustration). This would imply that some edge of Γ crosses the top side of , a contradiction.
(a) (b)
From the above paragraph we therefore get that the dual vertex 1 is necessarily above Γ and an analogous analysis implies that is below Γ. Next, we argue that the “first" edge (1, 2) ∈ is either present in the interior of or crosses the top edge of . For illustration we consider a magnified top cell = in Figure 7() containing edges and that intersect the top edge of (the dotted-dashed line). Because of the interior edge property (2), the dual edge (1, 2) must cross the top edge of in the segment .
Summarizing, the edge (1, 2) is either present in the interior of or crosses the top edge of . Similarly the final edge (− 1, ) is either contained in the interior of or crosses the bottom edge of . Every other vertex , 2 ≤ ≤ − 1 is present in the interior of Γ. Therefore the path necessarily crosses Γ in the sense that there are edges ∈ Γ and = (, +1) ∈ such intersects . The end-vertices of the dual edge belong to cells and +1 and the edge is common to and +1. At least one of the two cells or +1 lies in the interior of and so the edge is necessarily contained within the rectangle . Thus is an edge of some occupied cell in the left right crossing and so one of the cells or +1 must lie in the interior of and also be occupied, a contradiction.
We illustrate the above argument in Figure 8, where the edge = (5, 6) belonging to the path Γ = (1, 2, 3, 4, 5, 6) and the dual edge = (2, 3) in the path = (1, 2, 3, 4, 5) intersect.
Proof of (): The collection ℐ of all left cells 1, . . . , and the corner cells and in Figure 6 is a plus connected component. To each cell in ℐ we now assign a label . If some occupied cell in the interior of is connected to a left cell by a star connected occupied path, we assign the label to as well. The collection of all cells with the label is a star connected component which we denote as ℱ. If is any cell star adjacent to some cell in ℱ and not present in ℱ, we assign the label to .
By assumption, any vertex of a cell ∈ ℱ is contained in the interior of some dual cell. Therefore by Theorem 4, there exists a plus connected cell cycle Δ = (1, . . . , ) surrounding ℱ in such a way that the outermost boundary cycle of Δ contains all the cells of ℱ in its interior. The cell cycle Δ contains a plus connected cell sub-path Δ = (1 , . . . , 2 ) that lies to the right of ℒ, with 1 intersecting ℒ and 2 intersecting ℒ.
In Figure 9, we illustrate the part of the cycle Δ that intersects the rectangle with the cell labelled denoting . As in Figure 9, the cycle Δ may intersect the top side of multiple times but there exists a “last" cell after which the cycle never intersects the top side of . Formally, 1 be the largest index such that the cell intersects the top side of and 2 is the “first" cell after 1 that intersects the bottom side of . In Figure 9, 1 = 6 and 2 = 10.
By definition the cell 1 intersects the line ℒ, the cell 2 intersects the line ℒ and that every other , 1 < < 2 neither intersects ℒ nor intersects ℒ but lies between these two lines. By the nicely padded assumption we have that 2 > 1. No cell , 1 < < 2 can be a right cell because then there would exist an occupied cell contained in the interior of which is star adjacent to and is connected to some left cell by an occupied star connected cell path . The concatenation (, , ) would then form an occupied star connected left right crossing of , a contradiction. Thus each cell , 1 < < 2 is necessarily an interior cell.
By the nicely covered assumption, this necessarily means that 1 must be a top cell and not a corner cell. This is because, no corner cell is plus adjacent to an interior cell. Similarly 2 must be a bottom cell and not a corner cell and so (1 , 1+1, . . . , 2 ) forms a vacant plus connected top down crossing of .
Proof of (): The proof is analogous to the proof of () with minor modifications. Here Δ = (1, . . . , ) is star connected and if the corner cell or the bottom cell in Figure 6 appear in Δ, we simply remove the corresponding entry from Δ. The resulting sequence of vacant cells is still star connected and we proceed as before to get the desired vacant star connected top bottom crossing of .
In this section, we consider bond percolation in the lattice and the mutual exclusivity of left right and top down crossings of in a rectangle. We consider unoriented bond percolation and an analogous analysis holds for the oriented case as well. As before we assume that the percolation lattice = ⋃︀
=0 and the dual lattice = ⋃︀= 0 satisfy properties (1) − (5) and the origin is the present in the interior of the cell 0.
Moreover, we also assume that for a fixed rectangle , we assume that the sides of nicely covered and nicely padded by cells of as described prior to Definition 4.
Assuming that is nicely covered as described above, we have the following definition of left right crossings.
Definition 5. rectangle if: (1) The edge (1, 2) intersects the left side of and 1 lies in the exterior of . (2) The edge (− 1, ) intersects the right side of and lies in the exterior of . (3) Every other edge (, +1), 2 ≤ ≤ − 2 is contained in the interior of .
A path = (1, . . . , ) ⊂ , ≥ 4 is said to be a left right crossing of a By definition any left right crossing must contain at least one edge in the interior of . Every edge in the closed interior of is now assigned one of the following two states: open or closed. Moreover, if edge ∈ is open and if is the unique dual edge intersecting , then we assign to be open as well. If every interior edge in a left right crossing of is open, we say that is an open left right crossing of the rectangle . An analogous definition holds for top down crossings. We denote to be the event that the rectangle contains an open left right crossing of .
For the dual crossing we have a slightly diferent definition. We say that := (1, . . . , ) is a dual top bottom crossing of if the dual vertex 1 lies in a top cell, the dual vertex lies in a bottom cell and each edge (, +1), 1 ≤ ≤ − 1 intersects an interior edge of ; i.e., an edge of with both end-vertices present in the interior of .
We now see that every edge in a dual top bottom crossing has a state. By definition it sufices to see that the first edge (1, 2) and the last edge (− 1, ) both have states. First consider the edge (1, 2) and let (1, 2) ∈ intersect (1, 2). By the nicely covered assumption in Figure 6, we see that the edge (1, 2) belongs to one of the interior paths represented by the dotted lines and so necessarily lies in the interior of and consequently has a state. This implies that the dual edge (1, 2) has the same state as (1, 2). Similarly, the last edge (− 1, ) also has a state. If every edge in is closed, we say that is a closed dual top bottom crossing and we let be the event that contains a closed dual top bottom crossing consisting of edges of .
We have the following result.
Theorem 7. Suppose properties (1) − (5) hold. Further suppose that the rectangle is nicely covered and nicely padded by cells in as in Figure 6. One of the events or always occurs, but not both.
As before we need to prove three statements: () Both and cannot occur simultaneously. () If does not occur, then occurs. () If does not occur, then occurs.
The proof of () is analogous to the proof of () in Theorem 6. If Γ is any open left right crossing and Δ is any top bottom dual crossing, we obtain that one vertex of the dual crossing lies above Γ and one vertex lies below Γ and so these two paths must necessarily meet. The dual edge intersecting any edge ∈ has a state and in fact the same state as and this leads to a contradiction.
The proof of () is analogous to () and we prove () below.
Proof of (): Let {}1≤ ≤ be the set of edges of intersecting the left side of arranged in the decreasing order of the − coordinate of the intersection point and for 1 ≤ ≤ , let and be the end-vertices of present in the interior and exterior of , respectively. For example, in Figure 6, the edge 1 = 11, 2 = 22 and so on.
Let ℐ be the set of all open edges lying in the interior of and connected to some vertex in {}1≤ ≤ by an open path and for 1 ≤ ≤ − 1, let be the path between and +1 lying in the interior of the rectangle . The union ℰ = ℐ ∪ {}1≤ ≤ − 1 is then a connected component and each vertex ∈ ℰ is present in the interior of some dual cell () ⊂ . The union of the dual cells { ()}∈ℰ forms a plus connected dual component whose outermost boundary is a single cycle in containing all edges of ℰ in its interior.
We now see that contains at least one dual vertex present in the interior of a top cell. From Figure 6, the dual edge joining and intersects the edge (1, ) and so belongs to the dual cell (1) containing 1 in its interior. The dual vertex lying in the interior of the top cell 1 therefore belongs to the dual cell (1), by property (5). The dual edge (, ) is not present in any other dual cell (), ∈ ℰ and so belongs to the final cycle as well.
By an analogous argument, all the dual vertices present in the interior of the left cells 1, . . . , and the corner cells and form a sub-path of and the dual edge (0, 0) ∈ as well, where 0 and 0 are the dual vertices is present in the interior of the bottom left corner cell and the first bottom cell 1, respectively (See Figure 6). The subpath Δ := ∖ has end-vertices and 0. For illustration, in Figure 10, the outermost boundary cycle formed by the merging of the dual cells { ()}1≤ ≤ is shown by the dotted line (1, 2, . . . , 9, 1). Here 1 = , 9 = , 5 = 0 and 4 = 0. The sub-path = (5, 6, 7, 8, 9) and Δ = (1, 2, 3, 4).
The path Δ might contain many dual vertices present in the interior of some top cell and so we pick the “last" such vertex and call it 1. Similarly we pick the first dual vertex present in the interior of a bottom cell. Formally, we extract a sub-path Γ := (1, . . . , ) ⊂ Δ such that the vertex 1 lies in the interior of a top cell, the vertex lies in the interior of a bottom cell and every other lies in the interior of a right, corner or interior cell. To prove that each edge of Γ has a state it sufices to see that there does not exist such that belongs to a corner or a right cell and +1 belongs to a right cell.
As in Figure 11, we assume that and +1 both belong to right cells and an analogous argument holds for the corner cells since no corner cell is plus adjacent with an interior cell. From Figure 11 we see that the edge (, +1) ∈ Γ intersects some edge (, ) that cuts the right side of as in Figure 11. The vertex ∈ is therefore contained in the interior of the dual cell containing (, +1) (property (5)) and so by definition of the component ℰ, there exists an open path from to some vertex of the edge that intersects the left side of . The concatenation (, , (, )) would then form an open left right crossing of , a contradiction.
Finally by the nicely padded assumption there must exist at least two edges in Γ and so the subpath (1, . . . , ) ⊂ is a dual top bottom crossing of . It remains to see that each such edge is closed. Suppose not and the edge (, +1) ∈ Γ is open. By the interior edge property (2), there exists exactly one edge (1, 2) ∈ that intersects (, +1). By construction, one of the vertices, say 1 belongs to the component ℰ and so there is an open path from 1 to some end-vertex of the edge intersecting the left side of .
Since (, +1) is open, the edge (1, 2) is open as well and so 2 also belongs to ℰ. But if (1) and (2) denote the dual cells containing 1 and 2, respectively, then from property (4) the cells (1) and (2) are plus adjacent and share the edge (, +1). This implies that (, +1) is present in the interior of the cycle formed by merging (1) and (2) and consequently (, +1) must be present in the interior of the outermost boundary cycle as well, a contradiction. I thank Professors Rahul Roy, Thomas Mountford, Federico Camia, C. R. Subramanian and the referee for crucial comments that led to an improvement of the paper. I also thank IMSc for my fellowships.