Minimal spanning forests

Abstract

Minimal spanning forests on infinite graphs are weak limits of minimal spanning trees from finite subgraphs. These limits can be taken with free or wired boundary conditions and are denoted FMSF (free minimal spanning forest) and WMSF (wired minimal spanning forest), respectively. The WMSF is also the union of the trees that arise from invasion percolation started at all vertices. We show that on any Cayley graph where critical percolation has no infinite clusters, all the component trees in the WMSF have one end a.s. In ${\mathbb{Z}}^d$ this was proved by Alexander [Ann. Probab. 23 (1995) 87--104], but a different method is needed for the nonamenable case. We also prove that the WMSF components are ``thin'' in a different sense, namely, on any graph, each component tree in the WMSF has $p_{\mathrm{c}}=1$ a.s., where $p_{\mathrm{c}}$ denotes the critical probability for having an infinite cluster in Bernoulli percolation. On the other hand, the FMSF is shown to be ``thick'': on any connected graph, the union of the FMSF and independent Bernoulli percolation (with arbitrarily small parameter) is a.s. connected. In conjunction with a recent result of Gaboriau, this implies that in any Cayley graph, the expected degree of the FMSF is at least the expected degree of the FSF (the weak limit of uniform spanning trees). We also show that the number of infinite clusters for Bernoulli($p_{\mathrm{u}}$) percolation is at most the number of components of the FMSF, where $p_{\mathrm{u}}$ denotes the critical probability for having a unique infinite cluster. Finally, an example is given to show that the minimal spanning tree measure does not have negative associations.

Published at http://dx.doi.org/10.1214/009117906000000269 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• Percolation in the Hyperbolic Plane
• Phase Transitions on Nonamenable Graphs
• Scaling Limits for Minimal and Random Spanning Trees in Two Dimensions
• Ground State Structure in a Highly Disordered Spin Glass Model
• On the Red-Green-Blue Model
• Ends in free minimal spanning forests

Cited by in corpus (20)

• Uniqueness and non-uniqueness in percolation theory
• Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model
• Ergodic Subequivalence Relations Induced by a Bernoulli Action
• The local weak limit of the minimum spanning tree of the complete graph
• Non-unitarisable representations and random forests
• Interlacements and the Wired Uniform Spanning Forest
• Brooks's theorem for measurable colorings
• Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model
• Percolation beyond ${\mathbb{Z}}^{\bolds{d}}$: The contributions of Oded Schramm
• Invariant percolation and measured theory of nonamenable groups
• Ends in free minimal spanning forests
• Minimal spanning trees and Stein's method
• Geometry of the minimal spanning tree of a random $3$-regular graph
• Critical Percolation and the Minimal Spanning Tree in Slabs
• Random Complexes and l^2-Betti Numbers
• Processes on Unimodular Random Networks
• Random spatial growth with paralyzing obstacles
• Connected allocation to Poisson points in R^2
• A remark about the spectral radius
• Uniform non-amenability, cost, and the first l^2-Betti number