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

S⊆B

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

be a transient graph, and start with

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

n−1

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

n−1

∪ 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

))

k≥0

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

x−y

(X

t+s

= 0) ≈

X

t=kx−yk

tP

x−y

(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=kx−yk

1

t

d/2−1

.

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.