3Uniform spanning trees

III Percolation and Random Walks on Graphs

3.2 Infinite uniform spanning trees and forests
Since recurrent graphs are boring, let G be an infinite transient graph. Then a
“naive” way to define a uniform spanning tree is by exhaustions.
Let
G
n
be an exhaustion of
G
by finite graphs. Define
G
W
n
(where
W
stands
for “wired”) to be the graph
G
n
, where all of the vertices of
G \G
n
are glued to
a single vertex
z
n
. The “free”
G
n
is just
G
n
considered as a subgraph. It turns
out the wired one is much easier to study.
Let
µ
n
be the uniform spanning tree measure on
G
W
n
. Let
B
be a finite set
of edges B = {e
1
, . . . , e
n
}. Then for T a UST of G
W
n
, we have
µ
n
(B T ) =
m
Y
k=1
µ(e
k
T | e
j
T for all j < k)
=
n
Y
k=1
R
eff
(e
k
; G
W
n
/{e
j
: j < k}),
where
G
W
n
/{e
j
:
j < k}
is the graph obtained from
G
W
n
by contracting the edges
{e
j
: j < k}.
We want to show that
µ
n
as a sequence of measures converges. So we want
to understand how
R
eff
(
e
k
;
G
W
n
/{e
j
:
j < k}
) changes when we replace
n
with
n
+ 1. By Rayleigh’s monotonicity principle, since
G
W
n
can be obtained from
G
W
n+1
by contracting more edges, we know the effective resistance increases when
we replace n with n + 1. So we know that
µ
n
(B T ) µ
n+1
(B T ).
So (µ
n
(B T )) is an increasing sequence. So we can define
µ(B F) = lim
n→∞
µ
n
(B T ),
and
F
is our uniform forest. We can then extend the definition of
µ
to cylinder
events
{F : B
1
F, B
2
F = ∅}
with B
1
, B
2
finite sets of edges, using inclusion-exclusion:
µ(B
1
F, B
2
F = ) =
X
SB
2
µ(B
1
S F)(1)
|S|
.
Then by commuting limits, we find that in fact
µ(B
1
F, B
2
F = ) = lim
n→∞
µ
n
(B
1
T, B
2
T = ).
If A is a finite union or intersection of cylinder sets of this form, then we have
µ(A) = lim
n→∞
µ
n
(A).
So this gives a consistent family of measures.
By Kolmogorov’s theorem, we get a unique probability measure
µ
supported
on the forests of
G
.
µ
is called the wired uniform spanning forest. One can
also consider the free uniform spanning forest, where we do the same thing but
without gluing, however, this is more complicated and we will not study it.
We can adapt Wilson’s algorithm to generate uniform spanning forests. This
is called Wilson’s method rooted at infinity (BKPS, 2001).
Let
G
F
0
=
. Pick an ordering of the
vertices of
V
=
{x
1
, x
2
, . . .}
. Inductively, from
x
n
, we start a simple random
walk until the first time it hits
F
n1
if it does. If it doesn’t, then run indefinitely.
Call this (possibly infinite) path
P
n
. Since
G
is transient,
P
n
will visit every
vertex finitely many times with probability 1. So it makes sense to define the
loop erasure of P
n
. Call it LE(P
n
). We set
F
n
= F
n1
LE(P
n
),
and take
F =
[
n
F
n
.
As before, the order of V that we take does not affect the final distribution.
Proposition.
Let
G
be a transient graph. The wired uniform spanning forest
is the same as the spanning forest generated using Wilson’s method rooted at
infinity.
Proof.
Let
e
1
, . . . , e
M
be a finite set of edges. Let
T
(
n
) be the uniform spanning
tree on
G
W
n
. Let
F
be the limiting law of
T
(
n
). Look at
G
W
n
and generate
T
(
n
)
using Wilson’s method rooted at
z
n
. Start the random walks from
u
1
, u
2
, . . . , u
L
in this order, where (
u
i
) are all the end points of the
e
1
, . . . , e
M
(
L
could be less
than 2M if the edges share end points).
Start the first walk from
u
1
and wait until it hits
z
n
; Then start from the
next vertex and wait until it hits the previous path. We use the same infinite
path to generate all the walks, i.e. for all
i
, let (
X
k
(
u
i
))
k0
be a simple random
walk on
G
started from
u
i
. When considering
G
W
n
, we stop these walks when
they exit
G
n
, .e. if they hit
z
n
. In this way, we couple all walks together and all
the spanning trees.
Let
τ
n
i
be the first time the
i
th walk hits the tree the previous
i
1 walks
have generated in G
W
n
. Now
P(e
1
, . . . , e
M
T (n)) = P
e
1
, . . . , e
M
L
[
j=1
LE(X
k
(u
j
)) : k τ
j
n
.
Let
τ
j
be the stopping times corresponding to Wilson’s method rooted at infinity.
By induction on
j
, we have
τ
n
j
τ
j
as
n
, and by transience, we have
LE(X
k
(u
j
) : k τ
k
j
) LE(X
k
(u
j
) : k τ
j
). So we are done.
Theorem
(Pemantle, 1991)
.
The uniform spanning forest on
Z
d
is a single tree
almost surely if and only if d 4.
Note that the above proposition tells us
Proposition
(Pemantle)
.
The uniform spanning forest is a single tree iff starting
from every vertex, a simple random walk intersects an independent loop erased
random walk infinitely many times with probability 1. Moreover, the probability
that
x
and
y
are in the same tree of the uniform spanning forest is equal to the
probability that simple random walk started from
x
intersects an independent
loop-erased random walk started from y.
To further simplify the theorem, we use the following theorem of Lyons, Peres
and Schramm:
Theorem
(Lyons, Peres, Schramm)
.
Two independent simple random walks
intersect infinitely often with probability 1 if one walks intersects the loop erasure
of the other one infinitely often with probability 1.
Using these, we can now prove the theorem we wanted. Note that proving
things about intersection, rather than collisions, tends to be higher, because any
attempts to, say, define the first intersection time would inherently introduce an
asymmetry.
We prove half of Pemantle’s theorem.
Theorem.
The uniform spanning forest is not a tree for
d
5 with probability
1.
Proof of Pemantle’s theorem.
Let
X, Y
be two independent simple random walks
in Z
d
. Write
I =
X
t=0
X
s=0
1(X
t
= Y
s
).
Then we have
E
x,y
[I] =
X
t
X
s
P
xy
(X
t+s
= 0)
X
t=kxyk
tP
xy
(X
t
= 0).
It is an elementary exercise to show that
P
x
(X
t
= 0)
c
t
d/2
,
so
P
x
(X
t
= 0)
X
t=kxyk
1
t
d/21
.
For d 5, for all ε > 0, we take x, y such that
E
x,y
[I] < ε.
Then
P(USF is connected) P
x,y
(I > 0) E
x,y
[I] < ε.
Since this is true for every ε, it follows that P(USF is connected) = 0.