×

zbMATH — the first resource for mathematics

Wired cycle-breaking dynamics for uniform spanning forests. (English) Zbl 1364.05062
The uniform spanning forest of an infinite locally finite connected graph \(G\) is the infinite volume limit of uniformly chosen random spanning trees in large finite subgraphs of \(G\). We work with the wired uniform spanning forest of a graph: roughly, this is a boundary condition on the finite graphs over which the limit is taken. We denote by WUSF the wired uniform spanning forest of the graph we are considering.
A component of an infinite graph \(G\) is said to be one-ended if, over all finite sets \(W\) of vertices, the graph formed by deleting \(W\) from \(G\) has a maximum of one distinct infinite connected components. D. J. Aldous and R. Lyons [Electron. J. Probab. 12, 1454–1508 (2007; Zbl 1131.60003)], building on work of I. Benjamini et al. [Ann. Probab. 29, No. 1, 1–65 (2001; Zbl 1016.60009)] showed that all WUSF components are one-ended almost surely in every transient random rooted graph with bounded vertex degrees.
The paper under review removes the requirement that degrees be bounded from the result of D. J. Aldous and R. Lyons [loc. cit.]. A formal statement is that n a transient reversible random rooted network (a network is a graph where edge of \(G\) has a conductance \(c(e)>0\) attached to it) and for any vertex \(c(v)\) is the sum of the \(c(e)\) over edges incident with \(v\), and the root is \(\rho\), then, provided \(\mathbb{E}((c(\rho))^{-1})<\infty\) every component of the wired uniform spanning forest on it is one-ended almost surely. Note that graphs (networks with \(c(e)\equiv 1\) for every edge) automatically satisfy this condition as \(\rho\) has positive degree. There are networks discussed in the paper where without the condition \(\mathbb{E}((c(\rho))^{-1})<\infty\) the result fails.
Proof techniques include a method for updating an oriented forest at an edge, which leads to a family of Markov chains called the wired cycle-breaking dynamics. The result has implications for supercritical Galton-Watson trees conditioned to survive. The recurrent (as opposed to transient) case remains open. There are important consequences for the abelian sandpile model.

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
05C40 Connectivity
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI arXiv