Uniform spanning forests
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.
- Ends in uniform spanning forests
- Subequivalence relations and positive-definite functions
- Essential spanning forests and electrical networks on groups
- The components of the wired spanning forest are recurrent
- Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination
- Nonamenable products are not treeable
- Scaling limits of loop-erased random walks and uniform spanning trees
- Indistinguishability of the components of random spanning forests
- A Palm hierarchy for determinantal point processes with the Bessel kernel
- A proof of the transfer-current theorem in absence of reversibility
- Quasi-symmetries of determinantal point processes
- Interlacements and the wired uniform spanning forest
- Random forests and networks analysis
- The height fluctuations of an off-critical dimer model on the square grid
- Coloring percolation clusters at random.
- Sandpile models
- Change intolerance in spanning forests
- Determinantal probability measures
- Random interlacements and amenability
- Hölder regularity and dimension bounds for random curves
- The Dirichlet problem for orthodiagonal maps
- The abelian sandpile model on randomly rooted graphs and self-similar groups
- Induced graphs of uniform spanning forests
- Kernels of conditional determinantal measures and the Lyons-Peres completeness conjecture
- External diffusion-limited aggregation on a spanning-tree-weighted random planar map
- A reverse Aldous-Broder algorithm
- Stationary determinantal processes on \({\mathbb{Z}}^d\) with \(N\) labeled objects per site. I: Basic properties and full domination
- Random walks with local memory
- Quenched and averaged tails of the heat kernel of the two-dimensional uniform spanning tree
- Route lengths in invariant spatial tree networks
- Weights of uniform spanning forests on nonunimodular transitive graphs
- Uniform spanning forests on biased Euclidean lattices
- Multicolour Poisson matching
- Metric graphs, cross ratios, and Rayleigh's laws
- The free uniform spanning forest is disconnected in some virtually free groups, depending on the generator set
- The Hölder continuity of the scaling limit of three-dimensional loop-erased random walk
- Spatial networks and percolation. Abstracts from the workshop held January 17--23, 2021 (hybrid meeting)
- Local geometry of the rough-smooth interface in the two-periodic Aztec diamond
- Indistinguishability of collections of trees in the uniform spanning forest
- Stabilization of DLA in a wedge
- Four-dimensional loop-erased random walk
- Limits of random tree-like discrete structures
- Limiting entropy of determinantal processes
- Asymptotic height distribution in high-dimensional sandpiles
- Local limits of uniform triangulations in high genus
- The Green's function on the double cover of the grid and application to the uniform spanning tree trunk
- Invariance principle for the random conductance model with unbounded conductances
- Decomposition and convergence for tree martingales
- The component graph of the uniform spanning forest: transitions in dimensions \(9,10,11,\ldots\)
- One-ended spanning trees in amenable unimodular graphs
- Universality of high-dimensional spanning forests and sandpiles
- Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth
- Hyperbolic and parabolic unimodular random maps
- Indistinguishability of trees in uniform spanning forests
- Continuous versus discrete spins in the hyperbolic plane
- Infinite volume limit of the abelian sandpile model in dimensions \(d \geq 3\)
- Uniqueness of maximal entropy measure on essential spanning forests
- Ends in free minimal spanning forests
- Anchored burning bijections on finite and infinite graphs
- Approaching criticality via the zero dissipation limit in the abelian avalanche model
- Loop-erased random walk on a torus in dimensions 4 and above
- Infinite volume limit for the stationary distribution of Abelian sandpile models
- Two badly behaved percolation processes on a nonunimodular graph
- The diameter of uniform spanning trees in high dimensions
- Phase transitions for a class of gradient fields
- Loop-erased walks and total positivity
- Invariant coupling of determinantal measures on sofic groups
- The looping constant of Z^d
- Uniformly Discrete Forests with Poor Visibility
- Tree number pairs for free and wired spanning forests
- Solvable and algebraic systems on infinite ladder
- Invariant monotone coupling need not exist
- scientific article; zbMATH DE number 1195780 (Why is no real title available?)
- scientific article; zbMATH DE number 1123757 (Why is no real title available?)
- Couplings of uniform spanning forests
- Minimal configurations and sandpile measures
- On roughly transitive amenable graphs and harmonic Dirichlet functions
- Infinite-step stationarity of rotor walk and the wired spanning forest
- High-performance sampling of generic determinantal point processes
- Wired cycle-breaking dynamics for uniform spanning forests
- The local weak limit of \(k\)-dimensional hypertrees
- Laplacian growth, sandpiles, and scaling limits
- Uniform spanning forests of planar graphs
- Rotor walks on transient graphs and the wired spanning forest
- The Z-invariant massive Laplacian on isoradial graphs
- All properly ergodic Markov chains over a free group are orbit equivalent
- Geometry of Uniform Spanning Forest Components in High Dimensions
- Uniform spanning trees on Sierpiński graphs
- Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs
- Factor of iid percolation on trees
- Watermelons on the half-plane
- A note related to the CS decomposition and the BK inequality for discrete determinantal processes
- On combinatorial testing problems
- On the probabilistic representation of the free effective resistance of infinite graphs
- Recurrence of horizontal-vertical walks
- On tail triviality of negatively dependent stochastic processes
- Uniform even subgraphs and graphical representations of Ising as factors of i.i.d.
- Harnack inequality and one-endedness of UST on reversible random graphs
- Random interlacement is a factor of i.i.d.
- Logarithmic corrections to scaling in the four-dimensional uniform spanning tree
This page was built for publication: Uniform spanning forests
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1872175)
