Uniform spanning tree

A uniform spanning tree is sampled uniformly from all spanning trees of a finite connected graph.

On a connected locally finite recurrent graph, root Wilson's algorithm at a fixed graph vertex $r$ and process a countable enumeration of the graph vertices. Every walk hits the existing tree almost surely, since it contains $r$. Each attached graph path is finite, and the union is a connected acyclic spanning subgraph. Its law is the infinite uniform spanning tree.

It is also the common free and wired finite-volume limit of a sequence along every graph exhaustion. For a finite edge set, run a finite initial segment of the chosen enumeration containing all its endpoints. Its membership is then permanently decided, because later attachments have new internal graph vertices. Only finitely many finite random-walk trajectories were used, and their graph vertices and graph neighbours fit inside all sufficiently large exhaustion sets. Coupling then gives convergence of those finite-dimensional edge laws for both boundary conventions. Finite Wilson's algorithm is root/order independent, so the limiting law is too. There is no uniform counting measure on all infinite spanning trees; the definition is this limiting probability law.

A uniform spanning forest is an infinite-volume limit of uniform spanning trees on finite graph approximations. Free and wired boundary identifications give the free uniform spanning forest and wired uniform spanning forest, respectively.

The free uniform spanning forest of an infinite locally finite graph is the weak limit of uniform spanning trees on finite induced connected exhaustions with free boundary. Every component is infinite almost surely.

For a uniform spanning tree, increasing events supported on disjoint sets of edges have nonpositive covariance. This negative association and the spatial Markov property imply monotonicity of free-boundary spanning-tree measures under exhaustion.

For oriented edges $e_1,\dots ,e_k$, the probability that their unoriented versions all belong to a uniform spanning tree is the determinant of the matrix of transfer currents between them. In particular, every finite forest that can be extended to a spanning tree has positive inclusion probability.

In a finite unweighted connected graph, take distinct graph vertices $a\ne z$ and orient the unique graph path from $a$ to $z$ in a uniform spanning tree and assign signed unit current to its edges. Its mean over trees is the electrical unit flow from $a$ to $z$. The Kirchhoff node law follows by averaging graph path divergences. For the graph cycle law, let ${\mathcal{F}}_{az}$ be the two-component spanning forests separating the terminals and $A_F$ the component containing $a$. Deleting a tree-path edge and conversely adjoining an edge across a forest cut are inverse operations. Hence the mean signed current on an edge $u\to v$ isThis is the gradient of $h(u)=|\mathcal{T}(G){|}^{-1}{\sum }_F{1}_{A_F}(u)$, proving the graph cycle law. In particular $R_{\mathrm{eff}}(a,z)=|{\mathcal{F}}_{az}|/|\mathcal{T}(G)|$. For an oriented existing edge $e=(a,z)$, that edge is used by the tree graph path exactly when it belongs to the tree, and then has positive orientation. Thus its mean current is $\mathbb{P}(e\in T)$, giving the edge-inclusion formula for a uniform spanning tree by Ohm's law.

For an edge $e=\{a,b\}$ of conductance $c_e$ in a finite electrical network, its inclusion probability in the conductance-weighted uniform spanning tree is $c_e{R}_{\mathrm{eff}}(a,b)$. The same formula holds for the wired limit using the limiting wired effective resistance.

On a transitive graph, the free and wired uniform spanning-forest measures are invariant and ergodic under the transitive automorphism group. Consequently every translation-invariant event has probability zero or one.

The Aldous-Broder algorithm runs a random walk and includes the edge by which each vertex other than the start is first entered. On a finite graph this yields a uniform spanning tree. The same first-entrance construction works on recurrent infinite graphs through the infinite-volume limit.

Wilson's algorithm samples a uniform spanning tree by starting from a root and successively attaching loop-erased random walks from vertices not yet in the tree.

The wired uniform spanning forest of an infinite graph is the weak limit of uniform spanning trees on finite exhaustions whose exterior vertices are identified to one wired boundary vertex.

Wilson's algorithm rooted at infinity builds the wired uniform spanning forest on a transient graph by successively adding loop-erased random walks, run forever when they never hit the forest already constructed.

The number of trees in a wired uniform spanning forest is almost surely constant. This follows from its tail triviality together with the fact that every component is infinite.