III Percolation and Random Walks on Graphs

3Uniform spanning trees

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

= (

V, E

) be a finite weighted graph on

vertices. Then

e∈E

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

= (

V, E

) be a finite connected graph. A

spanning tree

is a connected subgraph of

which is a tree (i.e. there are

no cycles) and contains all the vertices in G.

Let

be the set of all spanning trees of

. 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

. For all every edge

= (

a, b

), define

(

s, a, b, t

) to be the set of spanning tress of

whose unique path from

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)

Then

is a unit flow from

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

is a flow from

. It is clear that

is anti-

symmetric. To check Kirchoff’s node law, pick

a 6∈ {s, t}

. We need to show

that

x∼a

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

may or may not contain

. If

it does not contain

, it contributes 0. If it contains

, then there is one edge

entering

and one edge leaving

, and it also contributes 0. So every spanning

tree contributes exactly zero to the sum.

So we have to prove that

satisfies the cycle law. Let

= (

, v

, . . . , v

n+1

) be a cycle. We need to show that

i=1

i(v

, 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,

and

, such that

s ∈ T

and

t ∈ T

Let

= (

a, b

) be an edge. Define

(

s, a, b, t

) to be the set of

s/t

bushes such

that a ∈ T

and b ∈ T

We claim that

(

s, a, b, t

)

(

s, a, b, t

). Indeed, given a bush in

(

s, a, b, t

we can add the edge

= (

a, b

) to get a spanning tree whose unique path from

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

= |{(v

, v

j+1

) : B ∈ B(s, v

, v

j+1

, t)}

−

= |{(v

, v

j+1

) : B ∈ B(s, v

j+1

, v

, t)}

Then the contribution of B is

− F

−

By staring it at long enough, since we have a cycle, we realize that we must have

= F

−

. So we are done.

Finally, we need to show that i is a unit flow. In other words,

x∼s

i(s, x) = 1.

But this is clear, since each spanning tree contributes

(

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

to a single vertex (keeping multiple edges if necessary). This

gives a correspondence between spanning trees of

containing

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

(

e ∈ UST of G.f

), and this is just

eff

(

;

G.f

). So it suffices

to show that

eff

(e; G.f) ≤ R

eff

(e; G).

But this is clear by Rayleigh’s monotone principle, since contracting

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

be a finite path in the graph

. We define the loop erasure as follows: for any pair

i < j

such that

remove x

i+1

, x

i+2

, . . . , x

, and keep repeating until no such pairs exist.

To implement Wilson’s algorithm, distinguish a root vertex of

, called

and take an ordering of

. Set

{r}

. Define

inductively as follows: take

the first vertex in the ordering is not in

. We start a simple random walk from

this vertex, and run until it hits

, and erase the loops. Then set

i+1

to be

the union of T

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

is generated. Under any vertex

, 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

, 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

), where

is the

th instruction under

, colour

(

x, S

) with colour

. A colour is now coloured, but not necessarily with the

same colour.

Suppose

is a cycle that can be popped in the order

, C

, . . . , C

, with

. Let

be any cycle in the original directed graph. We claim that

either

does not intersect

, . . . , C

, or

for some

, and

does not

intersect

, . . . C

k−1

. Indeed, if they intersect, let

x ∈ C

∩ C

, where

is the

smallest index where they intersect. Then the edge coming out of

will have

colour 1. Then

is also in the intersection of

and

, and so the same is

true for the edge coming out of

. Continuing this, we see that we must have

. So popping

, C

, . . . , C

k−1

, C

k+1

, . . . , C

gives the same result as

popping C

, . . . , C

Thus, by induction, if

is a cycle that is popped, then after performing a

finite number of pops,

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

lying over a spanning tree. Let

be the set of all (

O, T

), where

is the set of coloured cycles lying on top of

which arise from running the random walks.

Now if we can get to (

O, T

), then we could also get to (

O, T

) for any other

spanning spanning tree

, since there is no restriction on what could be under

the stacks. So we can write

X = X

× X

where

is a certain set of finite sets of coloured cycles, and

is the set of all

spanning trees.

Define a function Ψ on the set of cycles by

Ψ(C) =

e∈C

p(e), p(e) =

c(e)

c(e

−

)

where

= (

−

, e

), and

(

−

) 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) =

C∈O

Ψ(C).

Then

P(get (O, T ) using Wilson’s algorithm) =

e∈

C∈O

C∪T )

p(e) = Ψ(O) · Ψ(T ).

Since this probability factorizes, it follows that the distribution of

is indepen-

dent of

, and the probability of getting

is proportional to Ψ(

). So

has

the distribution of a uniform spanning tree.

Corollary

(Cayley’s formula)

The number of labeled unrooted trees on

vertices is equal to n

n−2

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.