Choosing a Spanning Tree for the Integer Lattice Uniformly

2004/04/02 by Robin Pemantle · 3 citations
Mathematics · #math.PR #msc:60C05 #msc:60K35

paper · pdf

published as Ann. Probab., 19, 1559 - 1574 (1991) · 24 pages

arxiv created 2004/04/02 · arxiv updated 2009/12/01

Abstract

Consider the nearest neighbor graph for the integer lattice Z^d in d dimensions. For a large finite piece of it, consider choosing a spanning tree for that piece uniformly among all possible subgraphs that are spanning trees. As the piece gets larger, this approaches a limiting measure on the set of spanning graphs for Z^d. This is shown to be a tree if and only if d=<4. In this case, the tree has only one topological end, i.e. there are no doubly infinite paths. When d>=5 the spanning forest has infinitely many components almost surely, with each component having one or two topological ends.

Cited by

• Nonmonotonic consensus transitions in bounded-confidence dynamics on unbiased networks
• Random walk reflected off of infinity, with applications to uniform spanning forests and supercritical Liouville quantum gravity
• A General Coupling for Ising Models and Beyond

Related

• Uniform spanning forest on the integer lattice with drift in one coordinate
• Uniform spanning forests associated with biased random walks on Euclidean lattices
• On spanning trees with high internal degree
• Minimal spanning arborescence
• Uniform random spanning trees