Uniform spanning forests (Q1872175)

Let \(G(V,E)\) be a connected graph, and let \(C\) be a function from the undirected edges of \(G\) to the positive reals. The pair \((G,C)\) is said to be a network. The network is finite if \(G\) is finite. In this case the \textit{D. B. Wilson} algorithm [in: Proceedings of the 28th annual ACM symposium on the theory of computing, 296-303 (1996; Zbl 0946.60070)] can choose a spanning tree \(T\) at random, not only according to uniform measure, but, in general, proportional to weight\((T)=\prod_{e\in T}C(e)\). The authors first extend Wilson's algorithm to infinite graphs, and then focus on two different spanning forest measures, namely the FSF ((weighted) free spanning forest) and the WSF ((weighted) wired spanning forest) measures. \textit{R. Pemantle} [Ann. Probab. 19, No. 4, 1559-1574 (1991; Zbl 0758.60010)] proved that the free and wired spanning forests coincide in \(\mathbb Z^d\) and that they give a single tree if and only if \(d\leq 4\). The authors extend Pemantle's alternative to general graphs and exhibit further connections of uniform spanning forests to random walks, potential theory, invariant percolation and amenability. The paper is a long and very interesting collection of new theorem, classical properties which are presented in a particular transparent way, comments, remarks and references. Among the results are the following: The FSF and WSF in a graph \(G\) coincide iff all harmonic Dirichlet functions on \(G\) are constant. For \(K\subseteq E\), denote by \(\mathcal{F}(K)\) the \(\sigma\)-field of events depending only on \(K\). The tail \(\sigma\)-field is the intersection of \(\mathcal{F}(E\setminus K)\) over all finite \(K\). Then, the tail \(\sigma\)-fields of the WSF and the FSF are proved to be trivial on any graph. Cayley graphs are explored. An end of a graph \(G(V,E)\) is a mapping \(\xi\) that assigns to any finite set \(K\subset V\) an infinite component of \(G\setminus K\), and satisfies the consistency condition \(K_0\subset K\Rightarrow \xi(K_0)\supset\xi(K)\). The authors prove that on any Cayley graph that is not a finite extension of \(\mathbb Z\), all component trees of the WSF have one end; this is new in \(\mathbb Z^d\) for \(d\geq 5\). Also, they show that a Cayley graph is amenable iff for all \(\varepsilon>0\) the union of the WSF and Bernoulli percolation with parameter \(\varepsilon\) is connected. On any tree, as well as on any graph with spectral radius less than 1, a.s. all components of the WSF are recurrent. The basic topology of the free and the wired uniform spanning forest measures on lattices in hyperbolic space \(\mathbb H^d\) is analyzed. Harmonic measure from infinity is shown to exist on any recurrent proper planar graph with finite codegrees. The paper ends with a discussion of several open problems and conjectures.