Induced graphs of uniform spanning forests

Abstract: Given a subgraph

H

of a graph

G

, the induced graph of

H

is the largest subgraph of

G

whose vertex set is the same as that of

H

. Our paper concerns the induced graphs of the components of

o p e r a t o r n a m e W S F (G)

, the wired spanning forest on

G

, and, to a lesser extent,

o p e r a t o r n a m e F S F (G)

, the free uniform spanning forest. We show that the induced graph of each component of

o p e r a t o r n a m e W S F (m a t h b b Z^{d}

) is almost surely recurrent when

d g e 8

. Moreover, the effective resistance between two points on the ray of the tree to infinity within a component grows linearly when

d g e 9

. For any vertex-transitive graph

G

, we establish the following resampling property: Given a vertex

o

in

G

, let

m a t h c a l T_{o}

be the component of

o p e r a t o r n a m e W S F (G)

containing

o

and

o v e r l i n e m a t h c a l T_{o}

be its induced graph. Conditioned on

o v e r l i n e m a t h c a l T_{o}

, the tree

m a t h c a l T_{o}

is distributed as

o p e r a t o r n a m e W S F (o v e r l i n e m a t h c a l T_{o})

. For any graph

G

, we also show that if

m a t h c a l T_{o}

is the component of

o p e r a t o r n a m e F S F (G)

containing

o

and

o v e r l i n e m a t h c a l T_{o}

is its induced graph, then conditioned on

o v e r l i n e m a t h c a l T_{o}

, the tree

m a t h c a l T_{o}

is distributed as

o p e r a t o r n a m e F S F (o v e r l i n e m a t h c a l T_{o})

.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Induced graphs of uniform spanning forests