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

Benjamini, Itai; Kesten, Harry; Peres, Yuval; Schramm, Oded

Ann. Math. (2) 160, No. 2, 465-491 (2004).

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.”

Reviewer: Hsien-Kuei Hwang (Taipei)

MSC:

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

Keywords:

spanning trees; lattice; random relation; stochastic dimension

Citations:

Zbl 0758.60010