1Percolation
III Percolation and Random Walks on Graphs
1.3 Two dimensions
We now focus on 2 dimensions. As discussed previously, we can exploit duality to
prove a lot of things specific to two dimensions. In particular, we will show that,
at
p
=
p
c
=
1
2
, certain probabilities such as
P
1
2
(0
↔ ∂B
(
n
)) exhibit a power law
decay. This is in contrast to the exponential decay for subcritical percolation
(and being bounded away from zero for supercritical percolation).
First we establish that p
c
is actually
1
2
.
Theorem. In Z
2
, we have θ
1
2
= 0 and p
c
=
1
2
.
It is conjectured that for all
d ≥
2, we have
θ
(
p
c
(
d
)) = 0. It is known to be
true only in d = 2 and d ≥ 11.
This was proved first by Harris, Kesten, Russo, Seymour, Welsh in several
iterations.
Proof. First we prove that θ
1
2
= 0. This will imply that p
c
≥
1
2
.
Suppose not, and θ
1
2
> 0. Recall that B(n) = [−n, n]
2
, and we define
C(n) = [−(n − 1), (n −1)]
2
+
1
2
,
1
2
in the dual lattice. The appearance of the
−
1 is just a minor technical inconve-
nience. For the same n, our B(n) and C(n) look like
B(n)C(n)B(n)
We claim that for large
n
, there is a positive probability that there are open
paths from the left and right edges of
B
(
n
) to
∞
, and also there are closed
paths from the top and bottom edges of
C
(
n
) to
∞
. But we know that with
probability 1, there is a unique infinite cluster in both the primal lattice and
the dual lattice. To connect up the two infinite open paths starting from the
left and right edges of
B
(
n
), there must be an open left-right crossing of
B
(
n
).
To connect up the two infinite closed paths starting from the top and bottom
of
C
(
n
), there must be a closed top-bottom crossing. But these cannot both
happen, since this would require an open primal edge crossing a closed dual edge,
which is impossible.
To make this an actual proof, we need to show that these events do happen
with positive probability. We shall always take
p
=
1
2
, and will not keep repeating
it.
First note that since there is, in particular, an infinite cluster with probability
1, we have
P(∂B(n) ↔ ∞) → 1.
So we can pick n large enough such that
P(∂B(n) ↔ ∞), P(∂C(n) ↔ ∞) ≥ 1 −
1
8
4
.
Let
A
`
/
A
r
/
A
t
/
A
b
be the events that the left/right/top/bottom side of
B
(
n
) is
connected to
∞
via an open path of edges. Similarly, let
D
`
be the event that
the left of C(n) is connected to ∞ via a closed path, and same for D
r
, D
r
, D
b
.
Of course, by symmetry, for
i, j ∈ {`, r, t, b}
, we have
P
(
A
i
) =
P
(
A
j
). Using
FKG, we can bound
P(∂S
n
6↔ ∞) = P(A
c
`
∩ A
c
r
∩ A
c
t
∩ A
c
b
) ≥ (P(A
c
`
))
4
= (1 −P(A
`
))
4
.
Thus, by assumption on n, we have
(1 −P(A
`
))
4
≤
1
8
4
,
hence
P(A
`
) ≥
7
8
.
Of course, the same is true for other A
i
and D
j
.
Then if G = A
`
∩ A
r
∩ D
t
∩ D
b
, which is the desired event, then we have
P(G
c
) ≤ P(A
c
`
) + P(A
c
r
) + P(D
c
t
) + P(D
c
b
) ≤
1
2
.
So it follows that
P(G) ≥
1
2
,
which, as argued, leads to a contradiction.
So we have
p
c
≥
1
2
. It remains to prove that
p
c
≤
1
2
. Suppose for contradiction
that
p
c
>
1
2
. Then
p
=
1
2
is in the subcritical regime, and we expect exponential
decay. Thus, (again with
p
=
1
2
fixed) there exists a
c >
0 such that for all
n ≥ 1,
P(0 ↔ ∂B(n)) ≤ e
−cn
.
Consider
C
n
= [0
, n
+ 1]
×
[0
, n
], and define
A
n
to be the event that there exists
a left-right crossing of C
n
by open edges.
Again consider the dual box D
n
= [0, n] × [−1, n] +
1
2
,
1
2
.
C
n
D
n
Define
B
n
to be the event that there is a top-bottom crossing of
D
n
by closed
edges of the dual.
As before, it cannot be the case that
A
n
and
B
n
both occur. In fact,
A
n
and
B
n
partition the whole space, since if
A
n
does not hold, then every path from
left to right of C
n
is blocked by a closed path of the dual. Thus, we know
P(A
n
) + P(B
n
) = 1.
But also by symmetry, we have P(A
n
) = P(B
n
). So
P(A
n
) =
1
2
.
On the other hand, for any point on the left edge, the probability of it reaching
the right edge decays exponentially with n. Thus,
P(A
n
) ≤ n(n + 1)P(0 ↔ ∂B
n
) ≤ (n + 1)e
−cn
which is a contradiction. So we are done.
So we now know that p
c
=
1
2
. We now want to prove that
P
1
2
(0 ↔ ∂B(n)) ≤ An
−α
for some
A, α
. To prove this, we again consider the dual lattice. Observe that if
we have a closed dual circuit around the origin, then this prevents the existence
of an open path from the origin to a point far far away. What we are going to
do is to construct “zones” in the dual lattice like this:
The idea is to choose these zones in a way such that the probability that each
zone contains a closed circuit around the origin is
≥ ζ
for some fixed
ζ
. Thus, if
B
(
n
) contains
m
many of these zones, then the probability that 0 is connected
to
∂B
(
n
) is bounded above by (1
−ζ
)
m
. We would then be done if we can show
that m ∼ log n.
The main strategy to bounding these probabilities is to use FKG. For example,
if we want to bound the probability that there is a closed circuit in a region
then we cut it up into the pieces
If we can bound the probability of there being a left-to-right crossing of a
horizontal piece, and hence by symmetry the probability of there being a top-to-
bottom crossing of a vertical piece, then FKG gives us a bound on the probability
of there being a closed circuit.
For convenience of notation, we prove these bounds for open paths in the
primal lattice. We make the following definitions:
B(k`, `) = [−`, (2k −1)`] × [−`, `]
B(`) = B(`, `) = [−`, `]
2
A(`) = B(3`) \ B(`)
LR(k`, `) = {there exists left-right crossing of B(k`, `) of open edges}
LR(`) = LR(`, `)
O(`) = {there exists open circuit in A(`) that contains 0 in its interior}.
We first note that we have already proven the following:
Proposition. P
1
2
(LR(`)) ≥
1
2
for all `.
Proof.
We have already seen that the probability of there being a left-right
crossing of [0
, n
+ 1]
×
[0
, n
] is at least
1
2
. But if there is a left-right crossing of
[0, n + 1] × [0, n], then there is also a left-right crossing of [0, n] × [0, n]!
For a general
p
, Russo–Symour–Welsh (RSW) lets us bound
P
p
(
O
(
`
)) by
P
p
(LR(`)):
Theorem (Russo–Symour–Welsh (RSW) theorem). If P
p
(LR(`)) = α, then
P
p
(O(`)) ≥
α
1 −
√
1 −α
4
12
.
A large part of the proof is done by the cut-and-paste argument we sketched
above. However, to successfully do cut-and-paste, it turns out we need bounds
on the probability of a left-right crossing on something that is not a square. The
key, non-trivial estimate is the following:
Lemma. If P
p
(LR(`)) = α, then
P
p
LR
3
2
`, `
≥ (1 −
√
1 −α)
3
.
To prove this, we need a result from the first example sheet:
Lemma
(
n
th root trick)
.
If
A
1
, . . . , A
n
are increasing events all having the same
probability, then
P
p
(A
1
) ≥ 1 −
1 −P
p
n
[
i=1
A
i
!!
1/n
.
Proof sketch.
Observe that the proof of FKG works for decreasing events as well,
and then apply FKG to A
c
i
.
We can now prove our initial lemma.
Proof sketch.
Let
A
be the set of left-right crossings of
B
(
`
) = [
−`, `
]
2
. Define a
partial order on
A
by
π
1
≤ π
2
if
π
1
is contained in the closed bounded region of
B(`) below π
2
.
Note that given any configuration, if the set of open left-right crossings is
non-empty, then there exists a lowest one. Indeed, since
A
must be finite, it
suffices to show that meets exist in this partial order, which is clear.
For a left-right crossing
π
, let (0
, y
π
) be the last vertex on the vertical axis
where
π
intersects, and let
π
r
be the path of the path that connects (0
, y
π
) to
the right.
O
(0, y
π
)
π
r
Let
A
−
= {π ∈ A : y
π
≤ 0}
A
+
= {π ∈ A : y
π
≥ 0}
Letting
B
(
`
)
0
= [0
,
2
`
]
×
[
−`, `
], our goal is to find a left-right crossing of the
form
O
More precisely, we want the following paths:
(i) Some π ∈ A
−
(ii) Some top-bottom crossing of B(`
0
) that crosses π
r
.
(iii)
Some left-right crossing of
B
(
`
0
) that starts at the positive (i.e. non-
negative) y axis.
To understand the probabilities of these events happening, we consider the
“mirror” events and then apply the square root trick.
Let π
0
r
be the reflection of π
r
on {(`, k) : k ∈ Z}. For any π ∈ A, we define
V
π
= {all edges of π are open}
M
π
= {exists open crossing from top of B(`)
0
to π
r
∪ π
0
r
}
M
−
π
= {exists open crossing from top of B(`)
0
to π
r
}
M
+
π
= {exists open crossing from top of B(`)
0
to π
0
r
}
L
+
= {exists open path in A
+
}
L
−
= {exists open path in A
−
}
L
π
= {π is the lowest open LR crossing of B(`)}
N = {exists open LR crossing of B(`)
0
}
N
+
= {exists open LR crossing in B(`)
0
starting from positive vertical axis}
N
−
= {exists open LR crossing in B(`)
0
starting from negative vertical axis}
In this notation, our previous observation was that
[
π∈A
−
(V
π
∩ M
−
π
)
| {z }
G
∩N
+
⊆ LR
3
2
`, `
So we know that
P
p
LR
3
2
`, `
≥ P
p
(G ∩N
0
) ≥ P
p
(G)P
p
(N
+
),
using FKG.
Now by the “square root trick”, we know
P
p
(N
+
) ≥ 1 −
q
1 −P
p
(N
+
∪ N
−
).
Of course, we have P
p
(N
+
∪ N
−
) = P
p
(LR(`)) = α. So we know that
P
p
(N
+
) ≥ 1 −
√
1 −α.
We now have to understand
G
. To bound its probability, we try to bound it by
the union of some disjoint events. We have
P
p
(G) = P
p
[
π∈A
−
(V
π
∩ M
−
π
)
≥ P
p
[
π∈A
−
(M
−
π
∩ L
π
)
=
X
π∈A
−
P
p
(M
−
π
| L
π
)P
p
(L
π
).
Claim.
P
p
(M
−
π
| L
π
) ≥ 1 −
√
1 −α.
Note that if
π
intersects the vertical axis in one point, then
P
p
(
M
−
π
| L
π
) =
P
p
(
M
−
π
| V
π
), since
L
−
π
tells us what happens below
π
, and this does not affect
the occurrence of M
−
π
.
Since M
−
π
and V
π
are increasing events, by FKG, we have
P
p
(M
−
π
| V
π
) ≥ P
p
(M
−
π
) ≥ 1 −
q
1 −P
p
(M
−
π
∪ M
+
π
) = 1 −
q
1 −P
p
(M
π
).
Since P
p
(M
π
) ≥ P
p
(LR(`)) = α, the claim follows.
In the case where
π
is more complicated, we will need an extra argument,
which we will not provide.
Finally, we have
P
p
(G) ≥
X
π∈A
−
P
p
(L
π
)(1 −
√
1 −α) = (1 −
√
1 −α)P
p
(L
−
).
But again by the square root trick,
P
p
(L
−
) ≥ 1 −
q
1 −P
p
(L
+
∪ L
−
) = 1 −
√
1 −α,
and we are done.
We now do the easy bit to finish off the theorem:
Lemma.
P
p
(LR(2`, `)) ≥ P
p
(LR(`))
P
p
LR
3
2
`, `
2
P
p
(LR(3`, `)) ≥ P
p
(LR(`)) (P
p
(LR (2`, `)))
2
P
p
(O(`)) ≥ P
p
(LR(3`, `))
4
Proof. To prove the first inequality, consider the box [0, 4`] × [−`, `].
3``
We let
LR
1
= {exists left-right crossing of [0, 3`] ×[−`, `]}
LR
2
= {exists left-right crossing of [`, 4`] ×[−`, `]}
T B
1
= {exists top-bottom crossing of [`, 3`] × [−`, `]}.
Then by FKG, we find that
P
p
(LR(2`, `)) ≥ P
p
(LR
1
∩ LR
2
∩ TB
1
) ≥ P
p
(LR
1
)P
p
(LR
2
)P
p
(T B
1
).
The others are similar.
Theorem. There exists positive constants α
1
, α
2
, α
3
, α
4
, A
1
, A
2
, A
4
such that
P
1
2
(0 ↔ ∂B(n)) ≤ A
1
n
−α
1
P
1
2
(|C(0)| ≥ n) ≤ A
2
n
−α
2
E(|C(0)|
α
3
) ≤ ∞
Moreover, for p > p
c
=
1
2
, we have
θ(p) ≤ A
4
p −
1
2
α
4
.
It is an exercise on the example sheet to prove that
P
1
2
(0
↔ B
(
n
))
≥
1
2
√
n
using the BK inequality. So the true decay of
P
1
2
(0
↔ ∂B
(
n
)) is indeed a power
law.
Proof.
(i) We first prove the first inequality. Define dual boxes
B(k)
d
= B(k) +
1
2
,
1
2
.
The dual annuli A(`)
d
are defined by
A(`)
d
= B(3`)
d
\ B(`)
d
.
We let
O
(
`
)
d
be the event that there is a closed dual circuit in
A
(
`
)
d
containing
1
2
,
1
2
. Then RSW tells us there is some ζ ∈ (0, 1) such that
P
1
2
(O(`)
d
) ≥ ζ,
independent of `. Then observe that
P
1
2
(0 ↔ ∂B(3
k
+ 1)) ≤ P
p
(O(3
r
)
d
does not occur for all r < k).
Since the annuli (
A
(3
r
)
d
) are disjoint, the events above are independent.
So
P
1
2
(0 ↔ ∂B(3
k
+ 1)) ≤ (1 − ζ)
k
,
and this proves the first inequality.
(ii)
The second inequality follows from the first inequality plus the fact that
|C(0)| ≥ n implies 0 ↔ ∂B(g(n)), for some function g(n) ∼
√
n.
(iii)
To show that
E
1
2
[
|C
(0)
|
α
3
]
< ∞
for some
α
3
, we observe that this expecta-
tion is just
X
n
P
1
2
(|C(0)|
α
3
≥ n).
(iv) To prove the last part, note that
θ(p) = P
p
(|C(0)| = ∞) ≤ P
p
(0 ↔ ∂B
n
)
for all
n
. By the corollary of Russo’s formula, and since
{
0
↔ ∂B
n
}
only
depends on the edges in B
n
, which are ≤ 18n
2
, we get that
P
1
2
(0 ↔ ∂B
n
) ≥
1
2p
18n
2
P
p
(0 ↔ ∂B
n
).
So
θ(p) ≤ (2p)
18n
2
P
1
2
(0 ↔ ∂B
n
) ≤ A
1
(2p)
18n
2
n
−α
1
.
Now take n = b(log 2p)
−1/2
c. Then as p &
1
2
, we have
n ∼
1
(2p −1)
1
2
.
Substituting this in, we get
θ(p) ≤ C
p −
1
2
α
1
/2
.
By similar methods, we can prove that
Theorem.
When
d
= 2 and
p > p
c
, there exists a positive constant
c
such that
P
p
(0 ↔ ∂B(n), |C(0)| < ∞) ≤ e
−cn
.
It is natural to ask if we have a similar result in higher dimensions. In higher
dimensions, all the techniques in Z
2
don’t work.
Higher dimensions
In d ≥ 3, define the slab
S
k
= Z
2
× {0, 1, . . . , k}
d−2
.
Then S
k
⊆ S
k+1
⊆ Z
d
.
In general, for a graph
G
, we let
p
c
(
G
) be the critical probability of bond
percolation in G. Then we have
p
c
(S
k
) ≥ p
c
(S
k+1
) ≥ p
c
.
So the sequence (p
c
(S
k
)) must converge to a limit. Call this limit
p
slab
c
= lim
k→∞
p
c
(S
k
).
We know that p
slab
c
≥ p
c
.
A lot of the results we can prove for
Z
2
can be proven for
p
slab
c
instead of
p
c
.
So the natural question is how
p
slab
c
is related to
p
c
, and in particular, if they
are equal. This has been an open question for a long time, until Grimmett and
Marstrand proved it.
Theorem
(Grimmett–Marstrand)
.
Let
F
be an infinite-connected subset of
Z
d
with p
c
(F ) < 1. Then for all η > 0, there exists k ∈ N such that
p
c
(2kF + B
k
) ≤ p
c
+ η.
In particular, for all d ≥ 3, p
slab
c
= p
c
.
We shall not prove the theorem, but we shall indicate how the “in particular”
part works.
We take F = Z
2
× {0}
d−2
. Then
2kF + B
k
= Z
2
× ([−k, k]
d−2
∩ Z
d−2
),
a translate of S
2k
. So p
c
(S
2k
) = p
c
(2kF + B
k
) → p
c
as k → ∞.
A consequence of Grimmett-Marstrand is that
Theorem. If d ≥ 3 and p > p
c
, then there exists c > 0 such that
P
p
(0 ↔ ∂B(n), |C(0)| < ∞) ≤ e
−cn
.