1 The Critical Probability for Bond Percola-

tion on Z^{2} is \frac{1}{2}

The main theorem we are going to prove in this section is that the critical value for bond percolation on Z^{2} is \frac{1}{2}. This is known as the Harris-Kesten Theorem, after Harris, who proved that p_{c} ≥ \frac{1}{2} in 1960, and Kesten, who proved that p_{c} ≤ \frac{1}{2} in 1980.

The critical value of \frac{1}{2} was conjectured well before being proven (at least since 1960), as a result of the symmetries between the lattice and it’s dual. (we will show this in the next section) but the result does not follow easily (as far as we know) from this symmetry.

We will begin by using the duality to show that at p = \frac{1}{2}, the crossing probability of a square is \frac{1}{2}. We shall than prove our main tool, a useful lemma by Russo, and Seymor and Welsh, which will give us a lower bound on the crossing probabilities of rectangles. Harris’s theorem will quickly follow, and after a bit more work, Kesten’s theorem as well. We might even see more than 1 way to finish the proof, each having it’s own merits.

Remark. The proof brought here is a combination of the proofs in Durret’s book and the paper of Bollobas and Ryorden. The self duality is folklore , but a good place to look is the B-R paper, the RSW proof is an adaptation of the version in B-R paper, and the harris and 1st Kesten proofs are taken from Durrets book, while the second proof is from the B-R paper. Grimmett also has a proof of the HK theorem that takes another approach, using results on the sub-critical case. I apologize for not having the nice drawings in here, though they are very helpful for the proofs. I’ll try to draw/scan something soon (volunteers?)

1.1 Using self duality

For a rectangle R in ℤ^{2}, let H(R) denote the event of an open horizontal crossing of R, and V (R) the event of an open vertical crossing of R.

Claim. Let R be an (n + 1) × n square. Then P_{\frac{1}{2}} (H(R)) = \frac{1}{2}. (And in particular P_{\frac{1}{2}} ([n] × [n]) ≥ \frac{1}{2}).

Proof. Use duality. The dual of R, denoted R_{∗} is an n × (n + 1) rectangle,(**Missing Drawing**) and a closed vertical crossing of R_{∗} exists iff an open horizontal crossing of R does not (for a full rigorous proof see [?] or [?]). But by symmetry these events have the same probability, so each happens with probability \frac{1}{2}.

Remark. More generally, for any rectangle R = [k] × [l], the dual is the rectangle R_{∗} = [k − 1] × [l + 1], and for any p, we have by the same proof, that

ℙ_{p}(H(R)) + ℙ_{1−p}V (R_{∗}) = 1

1.2 RSW Technology

The main tool we will use is a Lemma (or series of lemma’s) by Russo, and Seymor and Welsh, from 1978, which bounds below the crossing probability of ρn × n rectangles in terms of the crossing probability of an n × n square.

All along, we will denote by τ_{p}(n) the probability of existence of an open crossing of the n × n square under ℙ_{p}, and by τ_{p}(ρn, n) the probability of existence of an open crossing of the ρn × n rectangle.

We will get the results in 3 steps:

Step 1 - a clever symmetry argument:

Lemma. Let L be a 2n × 2n square, and let R_{1} be the lower left n × n square in L. Let F denote the event that there exist a vertical open crossing P_{1} of R_{1}, and an open path H_{1} connecting the right side of L with P_{1} (see drawing). Then ℙ_{p}(F) ≥ \frac{τ_{p}(n)τ_{P} (2n)}{2}.

Proof. Let E_{s} denote the event that s is the leftmost vertical crossing of R_{1}. Note that if a vertical crossing exists, than so does a leftmost one. Note also that the event E_{s} is independent on all bonds to the right of s. (It depends only on the edges of s and those to the left of s).

Let R_{2} denote the upper left n × n square of L.

For a given leftmost vertical crossing s, let s_{2} denote the reflection of s onto R_{2}. Then s∪s_{2} is a vertical path in L (the edges of s_{2} are not necessarily open). Let A_{s}^{1} be the event that there exists an open path in L connecting the right side of L and s, using only bonds to the right of s ∪ s_{2}, and let A_{s}^{2} be the event that there exists an open path connecting the right side of L and s_{2},using only bonds to the right of s ∪ s_{2}. Then:

1. By symmetry and independence, ℙ(A_{s}^{1} | E_{s}) = ℙ(A_{s}^{2} | E_{s}).

2. Since s ∪ s_{2} is a vertical path in L, H(L) ⊂ A_{s}^{1} ∪ A_{s}^{2}.

Combining the above we get

ℙ(A_{1} | E_{s}) ≥ ℙ(H(L))/2

And since F ⊃ ⋃_{s}(E_{s} ∩ A_{s}^{1}) we have

ℙ(F) ≥ ∑_{s}(E_{s} ∩ A_{s}^{1}) = ∑_{s} ℙ(E_{s})ℙ(A_{s}^{1} | E_{s})

≥ ∑_{s} ℙ(E_{s})ℙ(H(L))/2 = \frac{1}{2}ℙ(V (R_{1}))ℙ(H(L)) = \frac{1}{2}τ_{p}(n)τ_{p}(2n)

step 2: Crossing an [3n/2, n] rectangle.

Lemma. step 3: crossing general constant-relation rectangles: The square root trick:

Claim. If A_{1} and A_{2} are 2 increasing events satisfying ℙ(A_{1}) = ℙ(A_{2}). And let A = A_{1} ∪ A_{2} then

ℙ(A_{1}) ≥ 1 − \sqrt{1 − ℙ(A)}

Proof.

(1 − ℙ(A_{1}))^{2} = 1 − 2ℙ(A_{1}) − ℙ^{2}(A_{1}) =
1 − ℙ(A_{1}) − ℙ(A_{2}) − ℙ(A_{1})ℙ(A_{2}) ≥
1 − ℙ(A_{1}) − ℙ(A_{2}) − P (A_{1} ∩ A_{2}) = 1 − P (A)

This bound has the advantage over the trivial ℙ(A_{1}) ≥ ℙ(A)/2 since it’s close to 1 when P (A) is close to 1.

Lemmas revised:

lemma 1 , revised, has the following form:

ℙ(F) ≥ τ_{p}(2n)(1 − \sqrt{1 − τ_{p}(n)})

and the other bounds change accordingly.

1.3 Harris Theorem

We will show something stronger:

Theorem. θ(\frac{1}{2}) = 0. i.e. There is no infinite giant component at p = \frac{1}{2}.

Proof. Lemma. (RSW) There is a constant δ > 0 such that for any L > 0, the probability that an open circuit around 0 exists inside the annulus of radii L to 3L is bounded below by δ Proof. Divide the annulus into 4 3L × L rectangles (2 horizontal, 2 vertical) in the obvious way. By RSW, each is crossed in the long direction with probability ≥ δ_{0} for some constant δ_{0}. (since τ_{\frac{1}{2}} (n) ≥ \frac{1}{2})). By FKG, the probability of all these crossings existing together is more then the product of these probabilities, and if they all exist, then the union of these crossings includes a circuit around 0. q.e.d.

Look at the dual lattice L^{∗}. Take L_{n} = 4^{n} , and let A_{n} be the annulus of radii L_{n} to 3L_{n}. Then by the above lemma, each contains a closed circuit around the origin with probability ≥ δ. Since A_{n} do not intersect, these events are independent, and therefore with probability 1 such a closed circuit exists. But such a circuit insures 0 is not in an infinite component, so θ(\frac{1}{2}) = 0

1.4 Kesten’s theorem, the old fashioned way

We have 3 steps:

Step 1: - If p > \frac{1}{2} then τ_{p}(n) → 1) as n → ∞. Step 2: If τ_{p}(n) ≥ 1 − ϵ_{0} then for any integer k > 1, τ_{p}(3^{ρ}n, n) ≥ 1 − e^{−k} Step 3: Show θ(p) > 0

Step 1:

Proof. We will show that if τ_{p}(n) < 1 − ϵ then H([n] × [n]) has a high expected number of pivotal edges, and then we can use Russo’s formula. To find enough pivotal edges we work as follows:

Let L be a n × n square. Let s be the lowest left-right crossing of L. Let v_{1} be the leftmost closed vertical path in the dual of L connecting the upper boundary of L^{∗} with s. (Exists with probability ≥ ϵ since the edges above s are independent of s and below, and since ℙ(H(L)) ≤ 1 − ϵ.)

Let w be the edge in which v_{1} intersects s. then w is pivotal for H(L). Now lets draw log_{3} n disjoint square annuli in L,of constant proportions between their inner and outer radii. In each there is a closed path in L^{∗} connecting s and v_{1} with probability ≥ f(ϵ) > 0. The edge of s which such a path crosses must be pivotal. So E(N(H(L))) ≥ f(ϵ) log_{3} n and we are done.

Step 2: Exercise.

τ_{p}(4n, 2n) ≥

Step 3:Take a 3n×n horizontal rectangle containing 0. Put on it a 3^{2}n×3n vertical rectangle, etc.. Each such rectangle is crossed with probability ≥ 1− e^{−k}, and they are positively correlated, so with probability ≥ ∏_{k≥1}(1−e^{−k}) > 0. But if all such crossings exist, then their union is an infinite path, so an infinite component exists.

1.5 Bollobas-Ryordens proof of kestens theorem

1.6 Another proof of uniqueness of the infinite component in Z^{2}