3Uniform spanning trees

III Percolation and Random Walks on Graphs



3.1 Finite uniform spanning trees
The relation between uniform spanning trees and electrical networks was discov-
ered by Kirchoff in 1850’s. Of course, he was not interested in uniform spanning
tress, but in electrical networks themselves. One of the theorems we will prove is
Theorem
(Foster’s theorem)
.
Let
G
= (
V, E
) be a finite weighted graph on
n
vertices. Then
X
eE
R
eff
(e) = n 1.
We can prove this using the commute-time formula, but there is a one-line
proof using this connection between electrical networks and uniform spanning
trees.
Definition
(Spanning tree)
.
Let
G
= (
V, E
) be a finite connected graph. A
spanning tree
T
of
G
is a connected subgraph of
G
which is a tree (i.e. there are
no cycles) and contains all the vertices in G.
Let
T
be the set of all spanning trees of
G
. Pick
T T
uniformly at random.
We call it the uniform spanning tree. We shall prove the following theorem:
Theorem. Let e 6= f E. Then
P(e T | f T ) P(e T).
It is tempting to ask a very similar question if we instead considered all
spanning forests, do we get the same result? Intuitively, we should, but it turns
out this is an open question. So let’s think about trees instead.
In order to prove this, we need the following result:
Theorem (Kirchoff). Let T be a uniform spanning tree, e an edge. Then
P(e T ) = R
eff
(e)
Of course, this immediately implies Foster’s theorem, since every tree has
n 1 edges.
Notation.
Fix two vertices
s, t
of
G
. For all every edge
e
= (
a, b
), define
N
(
s, a, b, t
) to be the set of spanning tress of
G
whose unique path from
s
to
t
passes along the edge (a, b) in the direction from a to b. Write
N(s, a, b, t) = |N(s, a, b, t)|,
and N the total number of spanning trees.
Theorem. Define, for every edge e = (a, b),
i(a, b) =
N(s, a, b, t) N(s, b, a, t)
N
.
Then
i
is a unit flow from
s
to
t
satisfying Kirchoff’s node law and the cycle law.
Note that from the expression for i, we know that
i(a, b) = P(T N(s, a, b, t)) P(T N(s, b, a, t)).
Proof.
We first show that
i
is a flow from
s
to
t
. It is clear that
i
is anti-
symmetric. To check Kirchoff’s node law, pick
a 6∈ {s, t}
. We need to show
that
X
xa
i(a, x) = 0.
To show this, we count how much each spanning tree contributes to the sum. In
each spanning tree, the unique path from
s
to
t
may or may not contain
a
. If
it does not contain
a
, it contributes 0. If it contains
A
, then there is one edge
entering
a
and one edge leaving
a
, and it also contributes 0. So every spanning
tree contributes exactly zero to the sum.
So we have to prove that
i
satisfies the cycle law. Let
C
= (
v
1
, v
2
, . . . , v
n+1
=
v
1
) be a cycle. We need to show that
n
X
i=1
i(v
i
, v
i+1
) = 0.
To prove this, it is easier to work with “bushes” instead of trees. An
s/t
bush is
a forest that consists of exactly 2 trees,
T
s
and
T
t
, such that
s T
s
and
t T
t
.
Let
e
= (
a, b
) be an edge. Define
B
(
s, a, b, t
) to be the set of
s/t
bushes such
that a T
s
and b T
t
.
We claim that
|B
(
s, a, b, t
)
|
=
N
(
s, a, b, t
). Indeed, given a bush in
B
(
s, a, b, t
),
we can add the edge
e
= (
a, b
) to get a spanning tree whose unique path from
s
to t passes through e, and vice versa.
Instead of considering the contribution of each tree to the sum, we count the
contribution of each bush to the set. Then this is easy. Let
F
+
= |{(v
j
, v
j+1
) : B B(s, v
j
, v
j+1
, t)}
F
= |{(v
j
, v
j+1
) : B B(s, v
j+1
, v
j
, t)}
Then the contribution of B is
F
+
F
N
.
By staring it at long enough, since we have a cycle, we realize that we must have
F
+
= F
. So we are done.
Finally, we need to show that i is a unit flow. In other words,
X
xs
i(s, x) = 1.
But this is clear, since each spanning tree contributes
1
N
to
i
(
s, x
), and there are
N spanning trees.
We can now prove the theorem we wanted to prove.
Theorem. Let e 6= f E. Then
P(e T | f T ) P(e T).
Proof.
Define the new graph
G.f
to be the graph obtained by gluing both
endpoints of
f
to a single vertex (keeping multiple edges if necessary). This
gives a correspondence between spanning trees of
G
containing
f
and spanning
trees of G.f. But
P(e T | f T ) =
number of spanning trees of G.f containing e
number of spanning trees of G.f
.
But this is just
P
(
e UST of G.f
), and this is just
R
eff
(
e
;
G.f
). So it suffices
to show that
R
eff
(e; G.f) R
eff
(e; G).
But this is clear by Rayleigh’s monotone principle, since contracting
f
is the
same as setting the resistance of the edge to 0.
In practice, how can we generate a uniform spanning tree? One way to do so
is Wilson’s method.
Definition
(Loop erasure)
.
Let
x
=
hx
1
, . . . x
n
i
be a finite path in the graph
G
. We define the loop erasure as follows: for any pair
i < j
such that
x
i
=
x
j
,
remove x
i+1
, x
i+2
, . . . , x
j
, and keep repeating until no such pairs exist.
To implement Wilson’s algorithm, distinguish a root vertex of
G
, called
r
,
and take an ordering of
V
. Set
T
0
=
{r}
. Define
T
i
inductively as follows: take
the first vertex in the ordering is not in
T
i
. We start a simple random walk from
this vertex, and run until it hits
T
i
, and erase the loops. Then set
T
i+1
to be
the union of T
i
with this (loop-erased) path. Repeat until all vertices are used.
Theorem (Wilson). The resulting tree is a uniform spanning tree.
Note that in particular, the choice of ordering is irrelevant to the resulting
distribution.
To prove this theorem, it is convenient to have a good model of how the
simple random walk on
G
is generated. Under any vertex
G
, place an infinite
number of cards that contain iid instructions, i.e. each card tells us to which
neighbour we jump. Different vertices have independent stacks. Whenever we
are at a vertex
x
, look at the top card underneath it and go to the neighbour it
instructs. Then throw away the top card and continue.
Given stacks of cards under the vertices of the graph, by revealing the top
card of each vertex, we get a directed graph, where directed edges are of the
form (x, y), where y is the instruction on the top card under x.
If there is no directed cycle, then we stop, and we have obtained a spanning
tree. If there is a directed cycle, then we remove the top cards from all vertices
on the cycle. We call this procedure cycle popping. Then we look at the top
cards again and remove cycles and cards used.
We first prove a deterministic lemma about cycle popping.
Lemma.
The order in which cycles are popped is irrelevant, in the sense that
either the popping will never stop, or the same set of cycles will be popped, thus
leaving the same spanning tree lying underneath.
Proof.
Given an edge (
x, S
i
x
), where
S
i
x
is the
i
th instruction under
x
, colour
(
x, S
i
x
) with colour
i
. A colour is now coloured, but not necessarily with the
same colour.
Suppose
C
is a cycle that can be popped in the order
C
1
, C
2
, . . . , C
n
, with
C
n
=
C
. Let
C
0
be any cycle in the original directed graph. We claim that
either
C
0
does not intersect
C
1
, . . . , C
n
, or
C
0
=
C
k
for some
k
, and
C
0
does not
intersect
C
1
, . . . C
k1
. Indeed, if they intersect, let
x C
0
C
k
, where
k
is the
smallest index where they intersect. Then the edge coming out of
x
will have
colour 1. Then
S
1
x
is also in the intersection of
C
0
and
C
k
, and so the same is
true for the edge coming out of
S
1
x
. Continuing this, we see that we must have
C
k
=
C
0
. So popping
C
k
, C
1
, . . . , C
k1
, C
k+1
, . . . , C
n
gives the same result as
popping C
1
, . . . , C
n
.
Thus, by induction, if
C
is a cycle that is popped, then after performing a
finite number of pops,
C
is still a cycle that can be popped. So either there is
an infinite number of cycles that can be popped, so popping can never stop, or
every cycle that can be popped will be popped, thus in this case giving the same
spanning tree.
Using this, we can prove that Wilson’s method gives the correct distribution.
In Wilson’s algorithm, we pop cycles by erasing loops in the order of cycle
creation. This procedure will stop will probability 1. With this procedure, we
will reveal a finite set of coloured cycles
O
lying over a spanning tree. Let
X
be the set of all (
O, T
), where
O
is the set of coloured cycles lying on top of
T
,
which arise from running the random walks.
Now if we can get to (
O, T
), then we could also get to (
O, T
0
) for any other
spanning spanning tree
T
0
, since there is no restriction on what could be under
the stacks. So we can write
X = X
1
× X
2
,
where
X
1
is a certain set of finite sets of coloured cycles, and
X
2
is the set of all
spanning trees.
Define a function Ψ on the set of cycles by
Ψ(C) =
Y
eC
p(e), p(e) =
c(e)
c(e
)
,
where
e
= (
e
, e
+
), and
c
(
e
) is the sum of the conductances of all edges with
vertex e
.
More generally, if O is a set of cycles, then we write
Ψ(O) =
Y
CO
Ψ(C).
Then
P(get (O, T ) using Wilson’s algorithm) =
Y
e
S
CO
CT )
p(e) = Ψ(O) · Ψ(T ).
Since this probability factorizes, it follows that the distribution of
O
is indepen-
dent of
T
, and the probability of getting
T
is proportional to Ψ(
T
). So
T
has
the distribution of a uniform spanning tree.
Corollary
(Cayley’s formula)
.
The number of labeled unrooted trees on
n
-
vertices is equal to n
n2
.
Proof. Exercise.
How can we generalize Wilson’s algorithm to infinite graphs? If the graph is
recurrent, then we can still use the same algorithm, and with probability one,
the algorithm terminates. If we have a transient graph, then we can still perform
the same algorithm, but it is not clear what the resulting object will be.
The Aldous–Broder algorithm is another way of generating a uniform spanning
tree. Run a random walk that visits all vertices at least once. For every vertex
other than the root, take the edge the walk crossed the first time it visited the
vertex, and keep the edge in the spanning tree. It is an exercise to prove that
this does give a uniform spanning tree. Again, this algorithm works only on a
recurrent graph. A generalization to transient graphs was found by Hutchcroft.