=Paper= {{Paper |id=Vol-3010/PAPER_03 |storemode=property |title=Duality and Outermost Boundaries in Generalized Percolation Lattices |pdfUrl=https://ceur-ws.org/Vol-3010/PAPER_03.pdf |volume=Vol-3010 |authors=Ghurumuruhan Ganesan }} ==Duality and Outermost Boundaries in Generalized Percolation Lattices== https://ceur-ws.org/Vol-3010/PAPER_03.pdf

Duality and Outermost Boundaries in Generalized
Percolation Lattices
Ghurumuruhan Ganesan1
1
Institute of Mathematical Sciences, HBNI, Chennai

Abstract
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.

Keywords
Percolation lattices, Star and plus connected components, Outermost boundaries, Duality, Left-right
crossings,

1. Introduction
The structure of the outermost boundary of finite components is crucial for contour analysis
problems of percolation [3] and random graphs [5]. For the square lattice, self-duality plays a
crucial role in determining the properties of star and plus connected components and we refer
to Chapter 3 [2] for a detailed discussion of combinatorial properties of percolation in regular
lattices. For general graphs, [6] uses separating sets in equivalence class of infinite paths to
study duality in locally finite graphs and [5] uses unicoherence and topological arguments to
investigate plus connected components.
In many applications, it might happen that the lattice on which percolation occurs is not
necessarily regular, like for example percolation in Voronoi tessellations [2]. It would therefore
be interesting to study the duality properties of such irregular lattices and determine conditions
under these lattices have behaviour similar to the regular lattices. In this paper we study
outermost boundaries in generalized percolation lattices and prove duality properties analogous
to regular lattices. We first consider an arbitrary planar graph 𝐺 and impose certain cyclic
conditions on 𝐺 that results in a cellular structure analogous to regular lattices. We then define
the dual graph of 𝐺 and determine necessary and sufficient conditions for the dual to be a
percolation lattice, analogous to 𝐺. Using 𝐺 and its dual, we study outermost boundaries,
occupied components and rectangular left-right crossings in generalized percolation lattices.
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

Algorithms, Computing and Mathematics Conference (ACM 2021), Chennai, India
" gganesan82@gmail.com (G. Ganesan) ORCID: 0000-0001-5857-5411 (G. Ganesan)
© 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)

36
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.

2. Percolation lattices
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 [2].

Theorem 1. If 𝐺 is a percolation lattice, then there are distinct cells
𝑄1 , 𝑄2 , . . . , 𝑄𝑇 such that
𝑇
⋃︁
𝐺= 𝑄𝑖 . (2.1)
𝑖=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 {Δ𝑙 }.

37
⋃︀4 1: Example of a percolation lattice 𝐺 along with the corresponding cellular decomposi-
Figure
tion 𝑖=1 𝑄𝑖 .

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 [4],
we use an iterative piecewise algorithmic construction for obtaining the merged cycle.
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.

38
(b)
(a)
Figure 2: (𝑎) The cycle 𝑎𝑏𝑐𝑑𝑓 𝑔𝑎 formed by merging the cycles 𝑎𝑏𝑒𝑑𝑓 𝑔𝑎 and 𝑏𝑒ℎ𝑑𝑐𝑏. (𝑏) The path 𝑃 =
𝑋𝑌 𝑍 ⊂ 𝐷 lies in the exterior cycle 𝐶 = 𝑋𝑈 𝑍𝑉 𝑋.

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

39
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).

3. Outermost boundaries
⋃︀𝑇
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 compo-
nent 𝐶(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 .

40
(𝑖𝑖𝑖) 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, [1]). As an illustration, Figure 3(𝑎) describes a percolation lattice with six cells. The
cells with circle inside them are occupied and the rest are vacant. The occupied cells form a
star connected component and the outermost boundary consists of two cycles 𝐶1 = 𝑎𝑏𝑐𝑑𝑒𝑓 𝑔𝑎
and 𝐶2 = 𝑓 ℎ𝑘𝑓.

(a)
(b)
Figure 3: (𝑎) A star connected component formed by the cells with circle inside them. The outermost
boundary consists of two cycles 𝐶1 = 𝑎𝑏𝑐𝑑𝑒𝑓 𝑔𝑎 and 𝐶2 = 𝑓 ℎ𝑘𝑓. (𝑏) Replacing an interior path 𝑃 =
𝑎𝑏𝑐𝑑𝑒 in the cycle 𝐷𝑘 (denoted by the wavy curve) with a path 𝑄 = 𝑎𝑥𝑒 ⊆ 𝐷𝑘 .

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 = 𝑎𝑏𝑐𝑑𝑒𝑓 𝑔𝑎.

41
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 prop-
erty (𝑎); 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 suffices 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 com-
ponent 𝐶(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

42
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 sub-
graphs {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 𝐶𝑜𝑢𝑡 .

Plus connected components
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

43
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 𝑆𝑖

44
(a) (b)
Figure 4: (𝑎) An example where the dual graph 𝐺𝑑 is non-planar but connected and every edge of 𝐺𝑑
belongs to a cycle. (𝑏) An example where 𝐺𝑑 is planar and every edge of 𝐺𝑑 belongs to a cycle but 𝐺𝑑 is
not connected.

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 compo-
nent 𝐶(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 ) := 𝑅(𝑣) (4.1)
𝑣∈𝜕0

45
Figure 5: Cycle of vacant cells surrounding a star connected occupied component.

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.

Plus connected components
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 surround-
ing 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 𝑒𝑖

46
of 𝜕 + (0) belongs to a occupied cell of 𝐶 + (0) and also to a vacant cell 𝑍𝑖 lying in the ex-
terior 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 𝜕𝑍 .

5. Left right and top bottom crossings in rectangles
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 𝑎1 𝑏1 and 𝑎2 𝑏2 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 ∪ {𝑎1 𝑏1 , 𝑎2 𝑏2 } 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.

47
Figure 6: The sides of the rectangle are nicely covered by the cells of 𝐺.

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.

Proof of Theorem 6
We prove the following three statements.
(𝐼) The events 𝐿𝑅* (𝑅, 𝑂) and 𝑇 𝐷+ (𝑅, 𝑉 ) cannot both occur simultaneously.

48
(𝐼𝐼) 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)
Figure 7: (𝑎) If 𝐽1 lies below Γ, then the path Γ would cross the top side of 𝑅. (𝑏) The top cell 𝑇 =
𝑎𝑓 𝑐𝑑𝑒𝑏𝑎 containing the dual vertex 𝑤1 in its interior. The dual edge (𝑤1 , 𝑤2 ) with 𝑤2 present in the
interior of 𝑅, must cross the top edge of 𝑅 in the segment 𝑌 𝑍.

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

49
Figure 8: The edge 𝑓 = (𝑣5 , 𝑣6 ) belonging to the path Γ = (𝑣1 , 𝑣2 , . . . , 𝑣7 ) and the dual edge 𝑒 =
(𝑤2 , 𝑤3 ) belonging to the path 𝑃 = (𝑤1 , . . . , 𝑤5 ) intersect.

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 , . . . , 𝑍𝑡 ) surround-
ing ℱ𝑡𝑜𝑡 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

50
Figure 9: The part of the vacant cycle Δ𝑣𝑎𝑐 that intersects the rectangle 𝑅.

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 𝑅.

Bond Percolation
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

51
left right crossings.

Definition 5. A path 𝑃 = (𝑣1 , . . . , 𝑣𝑚 ) ⊂ 𝐺, 𝑚 ≥ 4 is said to be a left right crossing of a
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 𝑅.

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 different 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 suffices
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

52
Figure 10: The outermost boundary cycle 𝜕𝐸 = (𝑧1 , . . . , 𝑧9 , 𝑧1 ) denoted by the dotted lines, intersects
the top and bottom sides of the rectangle 𝑅.

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 = 𝑎1 𝑏1 , 𝑒2 = 𝑎2 𝑏2 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

53
Figure 11: The edge (𝑦𝑚 , 𝑦𝑚+1 ) ∈ Γ𝑊 cuts an edge intersecting the right side of 𝑅.

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 suffices 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.

54
Acknowledgments
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.

References
[1] B. Bollobás, Modern Graph Theory, Springer, 1998.
[2] B. Bollobás and O. Riordan, Percolation, Academic Press, 2006.
[3] G. Grimmett, Percolation, Springer Verlag, 1999.
[4] H. Kesten, The critical probability of bond percolation on the square lattice equals 12 ,
Communications in Mathematical Physics, 74 (1980) 41–59.
[5] M. Penrose, Random Geometric Graphs, Oxford, 2003.
[6] A. Timár, Boundary-Connectivity via Graph Theory, Proceedings of the American Mathe-
matical Society, 141 (2013), 475–480.