Geometry of the uniform spanning forest: transitions in dimensions 4, 8, 12,…. (English) Zbl 1071.60006

A spanning tree in a graph is a tree connecting all vertices in the graph. Given a graph, a uniform spanning tree “is a subgraph chosen uniformly at random among all spanning trees.” This paper addresses the geometry of the uniform spanning forest in \(\mathbb{Z}^d\), which is defined to be “the weak limit of uniform spanning trees in larger and larger finite boxes”. R. Pemantle [Ann. Probab. 19, 1559–1574 (1991; Zbl 0758.60010)] “proved that the uniform spanning forest consists almost surely of a single tree if and only if \(1\leq d\leq 4\).” The main result of this paper states that the maximum (among all pairs of vertices) of the minimum number of edges outside the uniform spanning forest in a path joining any two vertices equals \(\lfloor (d-1)/4\rfloor\). In particular, any two components of the uniform spanning forest are adjacent almost surely if \(5\leq d\leq 8\). “The notion of stochastic dimension for random relations in the lattice is introduced and used in the proof.”


60C05 Combinatorial probability
60G50 Sums of independent random variables; random walks
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
05C05 Trees
06Bxx Lattices


Zbl 0758.60010
Full Text: DOI arXiv Euclid