A pdf version is available here.

I would like to thank Dr. Sarkar for advising me on this project. With his guidance, I have been able to explore a world where probability theory meets graph theory.

The text I am mainly consulting is Percolation by Bollobás and Riordan. The arguments presented here are virtually identical to the proofs in the book with commentary. None of these arguments I can claim as my own. In writing these sections, I did not want to robotically reproduce their works and so I did my best to recreate them from my mind. Yet, due to the time I spent studying the book, you'll notice that naming of variables, and likely word choice as well, lines up with the presentation by Bollobás and Riordan. This page focuses on working through the ideas that were not completely obvious to me while reading, as well as providing more visuals to make percolation more accessible. Please contact me if you have any concerns about copyright infringement.

What are the differences between the graphs below?

Going from 0.4 to 0.5 to 0.6, we see more edges are being added. I would like to draw your attention to the size of the clusters, or the clumps of connected edges. At 0.4, the clusters are small; none of them take up more than a quarter of the graph. At 0.5, we see see bigger clusters, and at 0.6, most of the graph belongs to the same cluster.

Of course, we haven't discussed the mechanism behind why we are including edges, but we see a rapid transition from going 0.4 to 0.6. Understanding this transition is the big question behind this paper and is at the heart of Percolation Theory.

What is Percolation Theory? In short, it is the study of rapid transition within a random system. When coffee is percolating, water passes through a filter. If the water did not pass through, we would say percolation did not occur and we would not be able to enjoy our coffee. The fibers in the filter bind in patterns which may allow water to pass through, but what if we changed the probability of the fibers binding slightly? Would water be able to flow through now?

Or consider this: Take two cups of water of the same size and temperature. In one, many many molecules are interacting in a complex way and, in the other one, we also have many many molecules bouncing off each other in a different way. Yet, when we place them in a freezer, once the cups reach 0$^\circ C$, structure suddenly arises in both of them regardless of how the molecules are interacting. Percolation theory provides a way to model these systems. Contrast percolation with a diffusion process. Both percolation and diffusion model the spread of fluid, yet diffusion focuses on randomness regarding the fluid and percolation focuses on the randomness regarding the medium.

Some applications of percolation theory are in material science, neuroscience, information theory, and economics. Percolation theory was born out of the ponderings of Broadbent in modeling mask filters for coal mining (1954). The Monte Carlo simulations to estimate these models were considered some of the most difficult programs of the day. In 1961, the Murray Hill Lab had a program run for 39 hours analyzing these models. This was no small task for computers needing constant maintenance to prevent them from breaking down. When economists consider the industrial revolution, they focus on the diffusion ideas. Yet the medium of communication of these ideas was far more important in the drastic permanent change of society.

Returning to the idea of a rapid transition, percolation, to some degree, is the study of probability measures on a lattice graph structure. The quest to find the probability where this sudden transition occurs on different lattices, or infinite grids, was the focus of percolation theory for the first 20 years of the field's existence. There have been some deep results in percolation theory. Recently, the 2010 Fields Medal was awarded to Stanislav Smirnov for his work in percolation on the triangular lattice.

The first portion of the paper focuses on the basics. It includes definitions, a proof of a unique boundary for a finite cluster, and then a proof bounding the critical probabilities (which will be defined shortly) between 1/3 and 2/3. These bounds were established by Broadbent and Hammersley. The second portion of the paper builds up the machinery to prove Harris's Theorem via Harris's Lemma and lemmas regarding the crossing of rectangles. The proof of Harris's Theorem will show that the critical bond probability for having an infinite cluster is greater than or equal to 1/2. Enjoy!

To improve accessibility, the definitions will be less general than what Bollobás and Riordan present. Our focus will be on independent bond percolation in $\mathbb{Z}^2$. For those interested in the matter, I encourage you to read their work —site percolation, oriented percolation, and lattices of different structures are just the beginning.

The edges we will refer to as Bonds and the vertices as Sites. You'll notice that every site has exactly 4 bonds leaving it (we say the Degree of each vertex is 4) and each site is at an integer pair. It is a very nice and simple structure. In general, our Graph $\Lambda$ will be connected, infinite, and locally finite (which just means each site has a finite degree). As you see, $\mathbb{Z}^2$ fulfills these properties. We refer to the set of bonds as $E(\Lambda)$ and the set of sites as $V(\Lambda)$. Out of laziness, often we will say $x \in \Lambda$ instead of $x \in V(\Lambda)$ and put off doing the dishes.

More formally, $\mathbb{Z}^2$ is such that $V(\mathbb{Z}^2)=\{(a,b): a,b \in \mathbb{Z}\}$ and $E(\mathbb{Z}^2)=\{ab: |a-b|=1 \text{ for } a,b \in V(\mathbb{Z}^2)\}$.

$\mathbb{Z}^2$ is very simple. But we can choose a Subgraph of $\mathbb{Z}^2$, which may be more interesting, by selecting which bonds to consider open, or in our subgraph, along with all our sites. For example, we might choose the subgraph below:

Choosing bonds to be open by hand is tedious, especially if we want to choose an infinite number of them. We should defined a function that does the work for us. A Bond Configuration is a function $\omega: E(\mathbb{Z}^2) \rightarrow \{ 0,1 \}$, $e \rightarrow \omega_e$ where a bond $e$ is open iff $\omega_e=1.$ When we consider a specific $\omega$, it chooses if a bond is open (in the subgraph) or closed (not in the subgraph). We will let $\Omega$ be the set of all bond configurations. There are many functions from the edges set to $\{ 0,1 \}$ but let's imagine a function assigns each bond $e$ independently to be open with some probability, $p$, i.e. one bond being open has no effect on other bonds being open. We will consider the subgraph $\omega$ induces, $\mathbb{Z}^2_p$. Without great formality we will define a Probability Measure for $\mathbb{Z}^2$: $$\mathbb{P}_{\mathbb{Z}^2, p}=\prod_{f \in F_1}p\prod_{f \in F_0\ }(1-p)$$ where the bonds in $F_1$ are open and in $F_0$ closed. We will use the shorthand $\mathbb{P}_{ p}=\mathbb{P}_{\mathbb{Z}^2, p}.$ Now we can talk about the probability of events on the square lattice. For example, the probability that all bonds are open is $\mathbb{P}_{p}(e \in F_1| e \in \mathbb{Z}_2)=\prod_{e \in \mathbb{Z}_2}p=0$ except when $p =1$. Recall the three graphs from the overview, now with the largest clusters highlighted and associated values of $p.$

Notice the clusters form at random. As we increase $p$, the size of the clusters change quite rapidly. At first very few are connected, and then suddenly most of the sites in our rectangle are part of the same cluster.

To discuss this mathematically, let's define a few things: $x_i$ refers to a site and $e_i$ is a bond joining $x_{i-1}$ and $x_{i}$.

A Path, a Cycle, and a Walk (Repeated Edges Hidden)

A Walk is an alternating series of sites and bonds, $x_0,e_1,x_1,e_2,...,e_l,x_l$ where $e_i=x_{i-1}x_{i}$ for $0 < i \leq l$.

A Path is a walk such that $x_i \not = x_j$ for $0 \leq i < j \leq l$, otherwise known as a self-avoiding walk.

A Cycle is a walk such that $x_0=x_l$ and $x_i \not = x_j$ for $0 < i < j < l.$

Distance, $d$ is the minimum number of bonds to walk along to join two sites.

An Open Path is a path along open bonds from $x$ to $y \in \Lambda$ denoted $\{x \rightarrow y \}$. If there are an infinite number of elements in the set $\{y \in \Lambda:\{x \rightarrow y \}\}$, then we say $\{x \rightarrow \infty\}$. More conveniently, we will refer to $C_x:= \{y \in \Lambda: x \rightarrow y \}$, the Open Cluster containing site $x$.

This allows us to consider $\theta_x(p):=\mathbb{P}_p(|C_x|=\infty)$, the Probability $C_x$ is Infinite for a given $p.$ ($|C_x|$ is the size of the set $C_x$.) If we have two vertices $x$ and $y$ at distance $d$, what is the relationship between $\theta_x(p)$ and $\theta_y(p)$? If $x$ is part of an infinite cluster, then $y$ would also be part of an infinite cluster if we have $\{x \rightarrow y \}$. The probability of the event $\{x \rightarrow y \}$ is greater than $p^d,$ since that the is probability that the shortest path between them is open. Thus $\theta_y(p) \geq p^d\theta_x(p).$ Since every $y \in \mathbb{Z}^2$ is some finite distance from $x$, if $\theta_x(p)>0,$ then $\theta_y(p)>0.$

In other words, if there is a chance we have an infinite cluster somewhere, then at any place on our lattice an infinite cluster has a chance of occurring. Either $\theta_x(p)=0$ everywhere or $\theta_x(p)>0$ everywhere. Obviously if $p=0$, we have $\theta_x(p)=0$ and if $p=1,$ then $\theta_x(p)$ is definitely greater than zero. To explore the transition between these two endpoints, we need a few more definitions and results: Let $$A=\bigcup_{x\in \mathbb{Z}^2} \{|C_x|=\infty\}.$$ In words, $A$ is the event that there is an infinite cluster somewhere. Can we change whether or not $A$ occurs by changing the state of any finite number of bonds to be open or closed? Nope!

Take a bond $xy\in E(\mathbb{Z}^2)$. If we have a infinite cluster and $xy$ is closed, then making $xy$ open only potentially adds to the infinite cluster. Similarly, if there is no infinite cluster and $xy$ is open, changing it to closed makes clusters only smaller.

If we add an open bond $xy$ where $x$ and $y$ are each contained only in finite clusters, then the resulting cluster is no bigger than the sum of the cluster containing $x$ and the cluster containing $y.$ Thus by adding only a finite number of open bonds, we can only join a finite number of finite clusters, resulting in a finite cluster. Hence, if we did not start with an infinite cluster, then the resulting largest cluster will still be finite.

If removing a bond happened to break an infinite cluster into two finite pieces, then adding that bond back would only result in a finite cluster, a contradiction. Thus we could not have broken the infinite cluster into two finite pieces. Repeating this process a finite number of times, we see that removing a finite number of bonds cannot keep an infinite cluster from occurring. Hence we cannot change if an infinite cluster occurs by changing a finite number of bonds.

Thus $\mathbb{P}(A)$ is independent of the states of any finite number of bonds in $\mathbb{Z}^2.$ This allows us to classify $A$ as a Tail Event.

To properly define a tail event, let $X=(X_1,X_2,...)$ be a sequence of independent events. If $A$ is an event the space of possible events created by $X$ and, for every $n\in \mathbb{N},$ if $A$ is independent of $X_1,X_2,...,X_n$, then $A$ is a tail event.

By Kolmogorov's 0-1 Law, the probability of a tail event is either 0 or 1, thus $\mathbb{P}(A)$ is either 0 or 1. In other words, for every value $p$ we can be certain about the existence of an infinite cluster. The infinite cluster is not a random event for a given $p$. We are certain when $p=0$ that there is no infinite cluster and we are certain that there is an infinite cluster when $p=1$. But where is the transition? There must be a $p$ where we go from having no infinite cluster to having one with certainty.

Such a rapid transition from $\theta_x(p)=0$ everywhere to $\theta_x(p)>0$ everywhere suggests a critical $p_H$ where $C_x$ is finite for all $p < p_H$ and infinite for all $p > p_H$. This critical probability is named in honor of Hammersley. When we say percolation occurs, we are referring to a value of $p$ such that $p> p_H$.

For $p < p_H$, $C_0$ is finite with certainty. However, the expected size of $C_0$, $\mathbb{E}_p(C_0)$ is not necessarily finite. The expectation of $X$ is the sum of the $x\in X$ values times their respective probabilities, $E(x)=\sum_{x\in X}x\cdot p(x).$ To further clarify, consider the St. Petersburg Lottery:

We will we play a game where you flip a coin until you get tails. If you get tails on the first flip I give you 2 dollars. If you get heads on the first flip, but then get tails on the next flip, I give you four dollars. If you get heads on first two flips but then a tails, I give you eight dollars. And so on, until we get a tails. Needless to say, I will become incredibly poor playing this game, but also the game is finite with certainty. But what is the appropriate price to charge to play this game? If I wanted to make money in the long run, I would have to price the game above the expected value of the payout. However, the expected value $E(X)$ is infinite:

$$E(X)=\frac{1}{2}2+\frac{1}{4}4+\frac{1}{8}8+...=1+1+1+...$$

Despite the game being finite, and hence every payout being finite, the expected value is infinite. Similarly, a cluster can be finite with certainty even though its expected size is not finite.

This gives us another critical value: $p_T$ is $p$ such that $\mathbb{E}_p(|C_x|) < \infty$ for $p < p_T$ and $\mathbb{E}_p(|C_x|)= \infty$ for $p > p_T$, in honor of Temperley. Despite the abstractness of expected size, $p_T$ is generally easy to measure or bound. A good example of this is percolation on the Bethe Lattice, however we will not discuss it here.

What is the relationship between $p_H$ and $p_T$? Suppose we chose a $p>p_T$, then $\theta_x(p)>0$. Thus there is some probability $x$ is part of an infinite cluster. Thus if we break the expectation into its two parts,

$$\mathbb{E}_p(|C_x|)=\sum_{C_x\text{is finite}} \mathbb{P}(|C_x|)+\infty \theta_x(p).$$

Since $\theta_x(p)>0$ then $\mathbb{E}_p(|C_x|)=\infty$ and so $p>p_T.$ Thus $p_T\leq p_H.$

The dual graph is critical to understanding percolation in $\mathbb{Z}^2$. The Dual Graph of $\Lambda = \mathbb{Z}^2$ can be seen as a shifted graph: $\Lambda^*:=\mathbb{Z}^2+ (1/2,1/2)$. Often we take the corresponding dual bond, $e^* \in \Lambda^*$, to open when $e$ is closed and vice versa. By Corresponding Dual Bond, we mean the bond $e^*$ with the same midpoint.

Before discussing the boundary, let's go back to examining $\mathbb{Z}^2$. Since no bonds intersect anywhere other than at sites, $\mathbb{Z}^2$ is a Plane Graph. Plane graphs have some really nice properties. If we draw a polygon in $\mathbb{Z}^2$, it divides $\mathbb{Z}^2$ into two regions, the interior, which is bounded, and the exterior.

Since a cycle in $\mathbb{Z}^2$ forms a polygon, we can use a cycle to bound a region. Furthermore, if we have sites $x_0, x_i, x_j, x_k$ where $0 < i < j < k < l$, we cannot have two disjoint interior paths from $x_0$ to $x_j$ and $x_i$ to $x_k$. Similarly, we cannot have two exterior disjoint paths.

Now we can tackle the proof of a unique boundary for finite clusters.

Suppose we have a cluster $C.$ Let's first consider the three sets of sites of $\mathbb{Z}^2$: $C, C_\infty,$ and $R:= \mathbb{Z}^2 -C -C_\infty$.

$C$ is the set of sites in the cluster, $C_\infty$ is the set of sites in an infinite component disjoint from $C$, and $R$ the rest of the sites in $\mathbb{Z}^2$ that is not in $C$ or in $C_\infty$. The external boundary, $\partial^\infty C$, is the set of bonds in $\mathbb{Z}^{2*}$ dual to bonds joining $C$ and $C_\infty$.

An example of this below: The set of black sites connected by black bonds is $C$, $C_\infty$ is the infinite set of black sites disjoint from $C$ ( black sites outside the blue cycle), the rest of $\mathbb{Z}^2$ is $R$ (crossed out black sites). The blue cycle is $\partial^\infty C.$

Proposition: If the set of sites $C$ in a cluster is finite in $\mathbb{Z}^2$, then $\partial^\infty C$ is an open cycle with $C$ on the interior.

Proof: First we must establish that $C_\infty$ is well defined and unique.

Lemma: If the set of sites $C$ in a cluster is finite in $\mathbb{Z}^2$, then there exists a unique infinite component $C_\infty$ in $\mathbb{Z}^2$ disjoint from $C$.

Existence: Since $C$ is finite, there exists a leftmost site. Take sites to the left of that site. That component is infinite and disjoint from $C$.

Uniqueness: Suppose there is more than one infinite component: $C^1_\infty$ and $C^2_\infty$. For $x \in C^1_\infty$ and $y \in C^2_\infty$, for every path $P$ between $x$ and $y$, there must exist a site in $C$ that is in $P$. Thus $C$ must be infinite, which is a contradiction. Hence $C_\infty$ is unique. $\square$

Now consider oriented bonds of the form $\overrightarrow{uv} \in\overrightarrow{B}$ from a site $u \in C$ to a site $v \in C_\infty$. For $\overrightarrow{uv}$ consider $\overrightarrow{uv}^* \in \overrightarrow{B}^*$ where $\overrightarrow{uv}^*$ is $\overrightarrow{uv}$ rotated counterclockwise on it midpoint by $\pi/2$. Since $\overrightarrow{uv}^*$ is the corresponding bond in the dual to $uv$, and $uv$ is closed, $\overrightarrow{uv}^*$ is open. Notice that $\overrightarrow{B}^*$ is an orientation of $\partial^\infty C$.

We will show for $\overrightarrow{uv}^*$, there exists a unique bond in $\overrightarrow{B}^*$ leaving the site $v^*$ (the endpoint of $\overrightarrow{uv}^*$):

Let us look at the immediate square around $v^*$ in $\mathbb{Z}^2.$

The red arrow is $B$ and the blue one is in $B^*$

The site $s$ is the one in the upper right corner and $t$ is the site in the upper left corner. $s$ and $t$ may each be elements of $C, C_\infty,$ or $R$.

Existence: If there is no bond leaving the square through the right side, then $tv \not \in \overrightarrow{B}$ thus $t$ cannot be in $C$. $t$ also cannot be in $R$ since it is adjacent to $v$, a site in $C_\infty$. Hence, $t\in C_\infty$. Similarly, to prevent a bond leaving through the top of the square, $s$ must also be in $C_\infty$. However, since $u$ is in $C$, then the bond $us \in\overrightarrow{B}$, and further, $us \in \overrightarrow{B}^*$, thus we must have a bond in $\overrightarrow{B}^*$ leaving from $v^*$.

If we don't allow the dashed blue lines then we cannot have the dashed red lines and are forced to have the red line.

Uniqueness: Suppose two bonds leave the square.

If we have the top bond and another bond, the orange site must be in $C$ and $C_\infty.$

If one of these two is the bond leaving through the top, rotate both bonds back to their respective elements in $C$ and $C_\infty$. The head or tail of $st$ will be at the tail or head of the other bond, respectively. This forces either $s$ or $t$ to be in both $C$ or $C_\infty$, which is a contradiction.

If we rotate back the bonds leaving the sides, we have $s\in C_\infty$ and $t\in C$ and thus the existence of two disjoint paths (Impossible!)

So both bonds must leave out the sides. This means $s\in C_\infty$ and $t\in C$. Further, there must be a path of sites in $C$ joining $u$ and $t$ as well as a path of sites in $C_\infty$ joining $s$ and $v$. However these paths must intersect, implying the existence of a site that is in both $C$ and $C_\infty$, which is a contradiction.

Thus there is a unique bond leaving $v^*$ for every $\overrightarrow{uv}^*$ and since $\overrightarrow{B}^*$ is finite, the non-oriented bonds in $\partial^\infty C$ form cycles in the dual plane and these cycles are disjoint. By construction, for every cycle, sites in $C$ are to the immediate left and $C_\infty$ to the immediate right. If there is more than one cycle then C cannot be connected, thus $\partial^\infty C$ consists of a single cycle. $\square$

We now have the tools to bound the critical probabilities: $1/3 \leq p_T \leq p_H \leq 2/3$.

If the cluster is infinite, then the expected size of the cluster is also infinite. Thus $p_T \leq p_H$ as mentioned above. All we must check are the outer inequalities.

Proposition: $p_T \geq 1/3$.

Proof: If a site is in a cluster of $x_0$, then there is at least one open path from $x_0$ to that site. Thus the expected number of open paths is greater than the expected number of sites in the cluster. The number paths of length $d$ from ${x_0}$ is $\mu_d$. The probability of a path of length d being open is $p^d$.

A path starting at the origin has 4 possible choices for its first step. Since a path cannot immediately return to where it just came from, there are at most 3 options for each step after that. Thus $\mu_d \leq 4(3^{d-1})$.

If $p< 1/3$ then,

$$\mathbb{E}(|C_x|) \leq \mathbb{E}(\mu_d)=\sum_{d\geq 0}\mu_dp^d \leq 1+ \sum_{d\geq 1}4(3^{d-1})p^d=1+\frac{4}{3}\sum_{d \geq 1}(3p)^{d} < \infty.$$ Therefore $p_T \geq 1/3.\text{ } \square$

Proof of Upper Bound: $p_T \geq 1/3$. First note the contrapositive of Unique Boundary Theorem: If we do not have boundary in the dual graph around a cluster, then the size of the cluster is infinite.

For the upper bound we will consider the dual graph $\mathbb{Z}^{2*}$ where $e^* \in E(\mathbb{Z}^{2*})$ is closed when $e \in E(\mathbb{Z}^{2})$ is open. We will show that if our cluster has a sufficiently large $k$ ``radius," sometimes the dual graph does not contain a open cycle of any size around our cluster (the contrapositive of the dual boundary) and also our cluster can get that large. This will imply $p_H\leq2/3$ by contrapositive of the Unique Boundary Theorem.

Proposition: $p_H \leq 2/3.$

Proof: Let $L_k$ be the line connecting $(0,0)$ to $(k,0)$ in $\mathbb{Z}^{2}$. Consider the open dual cycle of length $2l$ containing $L_k$. The bond $e^*$ must occur somewhere between $(k+1/2,0)$ and $(l+3/2,0)$. Thus there are fewer than $l$ choices for $e^*$.

The number of choices for the remainder of the cycle must be less than the number of possible paths $\mu_{2l-1}$. Also recall that bonds in $\mathbb{Z}^{2*}$ are open with probability $1-p$.

The blue line is $L_9$. Every dual cycle of length $2l=40$ around $L_9$ must cross the x-axis between the green line and the right side of the black cycle.

$$\mathbb{E}_p(Y_k) \leq \sum_{l>1+k}(1-p)^{2l}l\mu_{2l-1}\leq \frac{4}{3}\sum_{l>1+k} l[3(1-p)]^{2l}.$$

That final sum converges for $p>2/3$. [Try the ratio test! Remember $k$ is fixed!].

Since the series is convergent, as we increase $k$, $\mathbb{E}(Y_k)$ goes to zero. Thus there a $K$ such that for $k>K,$ we have $\mathbb{E}(Y_k) <1$. Since this expectation is less than one and $Y_k$ measures the number of open dual cycles, there is a positive probability that there will be no dual cycle for a given $k$. We will call the event that there are no dual cycles for a given $k$, $A_k$. Notice if there are no dual cycles in the dual plane containing our cluster, then there can be no boundary for our cluster by the contrapositive of the Unique Boundary Theorem.

Further, if a cluster has no boundary in the dual, then it is infinite in size! Before we jump the gun, remember we are assuming the dual cycle must go around the line $L_k$. This is only necessary if all the bonds in $L_k$ are open, which is certainly not guaranteed. Hence, let $B_k$ be the event that all the bonds in $L_k$ are open. Notice events $A_k$ and $B_k$ are independent since the bonds that determine if they occur are not the same.

Independence of $A_k$ and $B_k$: The bonds that determine if a line is open are the interior ones while the ones that determine if we have a dual cycle are, at worst, the ones around the edge.

Thus for $k>K$, $C_x \geq \mathbb{P}(A_k \cap B_k) =\mathbb{P}(A_k)\mathbb{P}(B_k)=\mathbb{P}(A_k)p^k>0.$

Thus $p_H \leq 2/3.\text{ } \square$

It is worth noting how drastically we over-counted in our bounding of $\mathbb{E}_p(Y_k)$. If we chose a walk at random of length $2l-1$, almost all the time it would not finish our dual cycle.

Some of the things we counted for $L_9$ and $l=100$:

Now that we have established bounds on $p_H$ and $p_T$, let us begin to tackle Harris's Theorem. In building up the machinery, our first goal is to show increasing events are positively correlated (Harris's Lemma) by looking at powersets.

Powersets may seem unrelated to percolation. However, they provide the context for relating different bond configurations and identification of special events on the lattice, which will bring us to Harris's Lemma!

First, here are three ways of thinking about the powerset, each building upon the previous one: The Powerset, $\mathcal{P}(S)$, of a set $S$ is the set of all subsets of $S$.

1) For $A \subset S$ we have the characteristic function: $1_A: S \rightarrow \left\{0,1\right\}$ where

$1_A(x)= \left\{ \begin{array}{lr} 1 & \text{if } x \in A \\ 0 & \text{if } x \notin A \end{array} \right . $

Notice this is the same process as choosing which bonds are in a bond configuration. We choose a subset of bonds to be considered open.

For a finite $S$, we can consider $S$ identified by $ [n]= \left\{1,2,3,...,n\right\}$.

2) We can also identify $a \subset [n]$ by the 0-1 sequence $(a_i)^{n}_{i=1}$ where $a_i=1$ if $i \in a$ and $0$ if $i \in [n]\backslash a$. For $\left\{1,4\right\} \subset [5],$ $(a_i)^{5}_{i=1}=(1,0,0,1,0).$ The set of all possible sequences is given by $\left\{0,1\right\}^n$ and identifies $\mathcal{P}([n])$.

Example: $\left\{0,1\right\}^3=\left\{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\right\}$ which corresponds to $\left\{ \emptyset, \left\{3\right\},\left\{2\right\},\left\{2,3\right\},\left\{1\right\},\left\{1,3\right\},\left\{1,2\right\},\left\{1,2,3\right\}\right\}.$

3) Finally, we can think of a Hypercube, $Q^n,$ as the graph where vertices are given by elements of $\mathcal{P}([n])$.

$Q^3$

An edge connects two vertices (the sets $a \subset [n]$ and $b \subset [n]$) if there is only one element in their symmetric difference, $\Delta$. $\big[a\Delta b=(a \cup b)\backslash (a \cap b)\big]$.

$Q^3$

Another way of picturing $Q^n$ is the vertex set given by $\left\{0,1\right\}^n \subset \mathbb{R}^n$ and there is an edge connecting vertex $a$ and $b$ if $a-b=\pm e_i$ where $(e_1,e_2,...,e_n)$ is the canonical basis of $\mathbb{R}^n$. Now $\mathcal{P}([n])$ can be partially ordered*.

The bond $ab$ is now $\overrightarrow{ab}$ if $a \leq b$ for $a,b \in \mathcal{P}([n])$.

$Q^3:$ Partially Ordered

If we select elements to be in our subset with probability $p$ for each element, we the can now talk about the Weight Hypercube with Probability p, $Q^n_p$ and its associated probability measure, $\mathbb{P}$, on elements of the vertex set.

Suppose $p$ is 1/2. The probability of choosing a set of vertices $A$ at random is just a series of $n$ coin flips for each element of $|A|/{2^n}$.

In general, for $a=(a_1,a_2,...a_n) \in Q^n$ and $A \subset Q^n$,

$$\mathbb{P}(A)=\sum_{a \in A} \left[\prod_{a_i=1}p \prod_{a_i=0}(1-p)\right]$$

This is no different from selecting bonds to be considered open with that probability measure.

Let us define a Up-set, or an increasing event as:

For $a,b \in Q^n,$ $U \subset Q^n$ is an up-set if $a \in U$ and $a \leq b \Rightarrow b\in U$.

Similarly, we can define a Down-set as:

For $a,b \in Q^n,$ $D \subset Q^n$ is a down-set if $b \in U$ and $a \leq b \Rightarrow a\in D$.

Why do increasing events matter?

There are sets of bonds necessary to have open to form an open horizontal crossing of a rectangle, $H(R)$. Such sets are examples of up-sets. Some of these sets are disjoint from another, while others share most elements. However, adding additional open bonds doesn't change the value of the event. It still occurs. If we think of a bond configuration, $A$, and then we add bonds to make a set $B$, then $A \subset B$. If $A \Rightarrow H(R)$, then $B \Rightarrow H(R)$. Thus $H(R)$ is an increasing event.

• i) $a \leq a$ (reflexivity)
• ii) $a \leq b$ and $b \leq a \Rightarrow a=b$ (antisymmetry)
• iii) $a \leq b$ and $b \leq c \Rightarrow a \leq c$ (transitivity)

Harris's Theorem: Crossing a Square

Our long term goal is to create dual cycles around the origin. In order to do this, it is convenient to first find the probability of a open crossing of a square in $\mathbb{Z}^2$. We then will use the probability of this crossing to bound the probability of crossing thinner rectangles. Rotating and aligning these rectangles allows us to bound the probability of dual cycles around the origin.

Let's consider a rectangle, $R$ in $\mathbb{Z}^2$ with dimensions $A \times B$ with the lower left corner at the point $(a,b)$.

Let's define $R'$ to be a rectangle with dimensions $A-1 \times B+1$ with the lower left corner at the point $(a+.5,b-.5)$.

If a bond, $e,$ is open in $R$, the bond $e^*$ in $R'$ that intersects $e$ is taken to be closed.

Let $H(R)$ be the event that there is a horizontal crossing of $R$, that is, that there is a path of open bonds from the left to the right side of $R$, and let $V(R')$ be the event that there is a vertical crossing of $R'$.

Lemma: Exactly one of $H(R)$ and $V(R')$ will occur for any given bond configuration in $R$.

A Bond Configuration on $R$

Proof: Given a bond configuration on $R$, create an Archimedean lattice where octagons are gray or white if they correspond to sites in $R$ or $R'$, respectively. At an intersection of a bond, $e$, and a dual bond, $e^*$, exactly one will be open: we will place a square, colored gray if $e$ is open and white if $e$ is closed.

overlay.png

Associated Archimedean lattice

Notice a horizontal crossing is independent of the states of bonds on the left and right edges of $R$. Thus regardless of the state of those bonds, we will make the state of bonds on the left and right of $R$ to be open. Similarly, a vertical crossing is independent of the bonds on the top and bottom of $R'$ and so we will take those bonds to be closed.

 

The Modified Archimedean Lattice

$H(R)$ can only occur if there is a path of gray octagons and squares joining the left and right sides. Similarly, $V(R')$ only occurs if there is a path of white octagons and squares joining the top and bottom.

In other words, to have both $H(R)$ and $V(R')$ occur, we need two disjoint interior paths: yet this is impossible. At most one of $H(R)$ and $V(R')$ must occur. Yet we still must show that one of them must occur. Assume $H(R)$ does not occur. We must show $V(R')$ occurs.

 

The Path from $x$

Now consider the interface graph, $I$, where edges are edges in the lattice which separate gray regions from white ones, and vertices are at the endpoints of each edge in $I$. With the exception of the corners $x,y,z,w$ which have degree one, the degree of every vertex is two. (Since the rest of the vertices are at the intersection of three faces, two of faces must share a color by the pigeonhole principle.) If a vertex is part of a cycle, the vertex is required to have at least two edges and the vertex must be adjacent to two vertices that are also in a cycle. Thus if a vertex $v$ in $I$ is adjacent to a vertex not in a cycle, $v$ must not be a cycle as well.

Consider the component containing $x$. The site $x$ cannot be a part of a cycle since its degree is one. Thus the vertex adjacent to $x$ is also not part of a cycle. Thus the component containing $x$ is without a cycle. Since every vertex of this component has degree at most two, then this component is a path! Seeing that we have restricted ourselves to a path within a rectangle, this path must terminate. Noting that the degree of the every non $x,y,z,w$ vertex is two, the path cannot terminate anywhere other than the corners $x,y,z,w$. The path cannot terminate at $x$, since doing so would make a cycle. It cannot terminate at $w$, otherwise we have a horizontal crossing of $R$ [It is the same argument as presented below for $y$]. The path cannot terminate at $z$, since at every edge along the path in $I$, beginning at one leaving $x$, gray has remained on the right. To end at $z$ would mean we would have switched gray to the left. Thus the path containing $x$ must terminate at $y$.

Since our path in $I$ ends at $y$, take the subgraph $T \subset R$ that correspond to white octagons and squares to the left of the path in $I$. Form a minimal connected subgraph $P$ in $T$ from the top to bottom, discarding unnecessary bonds and sites. Thus $P$ is a path from top to bottom and $V(R')$ occurs. $\square$

It is important to note that the vertical crossing found by this method is the leftmost vertical crossing of $R$. This path is not determined by the state of the bonds to the left of it and thus is independent of these bonds. This is crucial in the next section.

Corollary 1: Now consider a bond configuration given by the probability measure: $\mathbb{P}_p$. Bonds in $R$ are open with probability $p$ and bonds in $R'$ are open with probability $1-p$. Since every bond configuration in $R$ determines the bond configuration in $R'$: $$ \mathbb{P}_p(H(R))+\mathbb{P}_{1-p}(V(R'))=1.$$

Corollary 2: Consider a rectangle $N$ with dimensions $n \times n-1$. If $p=1/2,$ then $\mathbb{P}_{1/2}(H(N))+\mathbb{P}_{1/2}(V(N'))=1.$ Notice $N'$ is $N$ rotated by $\pi/2$. Thus the probability of having a vertical crossing of $N'$ is the same as having a horizontal crossing of $N$. [$\mathbb{P}_{1/2}(H(N))=\mathbb{P}_{1/2}(V(N'))$] Therefore,

$$\mathbb{P}_{1/2}(H(N))=1/2.$$

Corollary 3: Consider a square $S$, with dimensions $s \times s$. Since the square has more possible open horizontal paths than the rectangle $N$:

$\mathbb{P}_{1/2}(H(S)) \geq 1/2.$ And by symmetry:

$$\mathbb{P}_{1/2}(H(S)=\mathbb{P}_{1/2}(V(S))\geq 1/2.$$

This argument is equivalent to $R$ in the dual and $R'$ in $\mathbb{Z}^2$. Thus for the following arguments, so long as we are working with $p=1/2$, it is unnecessary to specify which lattice we are working in.