III Percolation and Random Walks on Graphs

3Uniform spanning trees

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

be an exhaustion of

by finite graphs. Define

(where

stands

for “wired”) to be the graph

, where all of the vertices of

G \G

are glued to

a single vertex

. The “free”

is just

considered as a subgraph. It turns

out the wired one is much easier to study.

Let

be the uniform spanning tree measure on

. Let

be a finite set

of edges B = {e

, . . . , e

}. Then for T a UST of G

, we have

(B ⊆ T ) =

k=1

µ(e

∈ T | e

∈ T for all j < k)

k=1

eff

; G

/{e

: j < k}),

where

/{e

j < k}

is the graph obtained from

by contracting the edges

: j < k}.

We want to show that

as a sequence of measures converges. So we want

to understand how

eff

(

;

/{e

j < k}

) changes when we replace

with

+ 1. By Rayleigh’s monotonicity principle, since

can be obtained from

n+1

by contracting more edges, we know the effective resistance increases when

we replace n with n + 1. So we know that

(B ⊆ T ) ≤ µ

n+1

(B ⊆ T ).

So (µ

(B ⊆ T )) is an increasing sequence. So we can define

µ(B ⊆ F) = lim

n→∞

(B ⊆ T ),

and

is our uniform forest. We can then extend the definition of

to cylinder

events

{F : B

⊆ F, B

∩ F = ∅}

with B

, B

finite sets of edges, using inclusion-exclusion:

µ(B

⊆ F, B

∩ F = ∅) =

S⊆B

µ(B

∪ S ⊆ F)(−1)

|S|

Then by commuting limits, we find that in fact

µ(B

⊆ F, B

∩ F = ∅) = lim

n→∞

⊆ T, B

∩ T = ∅).

If A is a finite union or intersection of cylinder sets of this form, then we have

µ(A) = lim

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

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

be a transient graph, and start with

∅

. Pick an ordering of the

vertices of

, x

, . . .}

. Inductively, from

, we start a simple random

walk until the first time it hits

n−1

if it does. If it doesn’t, then run indefinitely.

Call this (possibly infinite) path

. Since

is transient,

will visit every

vertex finitely many times with probability 1. So it makes sense to define the

loop erasure of P

. Call it LE(P

). We set

= F

n−1

∪ LE(P

and take

F =

[

As before, the order of V that we take does not affect the final distribution.

Proposition.

Let

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

be a finite set of edges. Let

(

) be the uniform spanning

tree on

. Let

be the limiting law of

(

). Look at

and generate

(

)

using Wilson’s method rooted at

. Start the random walks from

, u

, . . . , u

in this order, where (

) are all the end points of the

, . . . , e

(

could be less

than 2M if the edges share end points).

Start the first walk from

and wait until it hits

; 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

, let (

(

))

k≥0

be a simple random

walk on

started from

. When considering

, we stop these walks when

they exit

, .e. if they hit

. In this way, we couple all walks together and all

the spanning trees.

Let

be the first time the

th walk hits the tree the previous

i −

1 walks

have generated in G

. Now

P(e

, . . . , e

∈ T (n)) = P





, . . . , e

∈

[

j=1

LE(X

)) : k ≤ τ





Let

be the stopping times corresponding to Wilson’s method rooted at infinity.

By induction on

, we have

→ τ

n → ∞

, and by transience, we have

LE(X

) : k ≤ τ

) → LE(X

) : k ≤ τ

). So we are done.

Theorem

(Pemantle, 1991)

The uniform spanning forest on

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

and

are in the same tree of the uniform spanning forest is equal to the

probability that simple random walk started from

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

Proof of Pemantle’s theorem.

Let

X, Y

be two independent simple random walks

in Z

. Write

I =

∞

t=0

∞

s=0

1(X

= Y

Then we have

x,y

[I] =

x−y

t+s

= 0) ≈

t=kx−yk

x−y

= 0).

It is an elementary exercise to show that

= 0) ≤

d/2

= 0) ≤

t=kx−yk

d/2−1

For d ≥ 5, for all ε > 0, we take x, y such that

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.