zbMATH — the first resource for mathematics

Percolation and minimal spanning forests in infinite graphs. (English) Zbl 0827.60079
Summary: The structure of a spanning forest that generalizes the minimal spanning tree is considered for infinite graphs with a value \(f(b)\) attached to each bond \(b\). Of particular interest are stationary random graphs; examples include a lattice with i.i.d. uniform values \(f(b)\) and the Voronoi or complete graph on the sites of a Poisson process, with \(f(b)\) the length of \(b\). The corresponding percolation models are Bernoulli bond percolation and the “lily pad” model of continuum percolation, respectively. It is shown that under a mild “simultaneous uniqueness” hypothesis, with at most one exception, each tree in the forest has one topological end, that is, has no doubly infinite paths. If there is a tree in the forest, necessarily unique, with two topological ends, it must contain all sites of an infinite cluster at the critical point in the corresponding percolation model. Trees with zero, or three or more, topological ends are not possible. Applications to invasion percolation are given. If all trees are one-ended, there is a unique optimal (locally minimax for \(f)\) path to infinity from each site.

60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation
60D05 Geometric probability and stochastic geometry
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI