Choosing a Spanning Tree for the Integer Lattice Uniformly

1991/10/01 by Robin Pemantle · 8 citations
Mathematics · #Stochastic processes and statistical mechanics #Mathematical Dynamics and Fractals #Limits and Structures in Graph Theory #Spanning tree #Mathematics #Combinatorics #Minimum degree spanning tree #Euclidean minimum spanning tree #Minimum spanning tree #Limiting #Integer lattice #Lattice (music) #Discrete mathematics #Connected dominating set #Tree (set theory)

paper · pdf · doi:10.1214/aop/1176990223

openalex publication_date 1991/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15

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

• Interlacements and the wired uniform spanning forest
• Scaling limits of loop-erased random walks and uniform spanning trees
• The asymptotic determinant of the discrete Laplacian
• Dimension of the loop-erased random walk in three dimensions
• Conformal invariance of planar loop-erased random walks and uniform spanning trees
• Long-range properties of spanning trees
• The scaling limit of loop-erased random walk in three dimensions
• Loop-erased random walk [wikipedia]