Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 214 / 4

A spanning tree of a finite connected graph $G$ is a connected acyclic subgraph containing every vertex. A uniform spanning tree is a random spanning tree chosen uniformly from the finite set of all spanning trees of $G$.

For an infinite locally finite recurrent connected graph, take an increasing exhaustion by finite connected subgraphs and sample a uniform spanning tree in each. The restrictions to any fixed finite edge set converge in distribution; on a recurrent graph the free and wired limits coincide and form one tree. This infinite-volume law is called the uniform spanning tree of the recurrent graph.

It can be generated by Wilson's algorithm. Fix a root and an enumeration of the remaining vertices. Starting with the root, run a random walk from the first vertex not yet in the tree until it hits the existing tree, erase its loops chronologically, and add the resulting path. Recurrence ensures every walk hits the finite tree almost surely. Repeating this operation produces the infinite uniform spanning tree, independently of the enumeration.

Exhaust ${\mathbb{Z}}^2$ by finite boxes $G_n$ and let $T_n$ be a uniform spanning tree of $G_n$. Every finite tree satisfies the handshaking lemma, soChoose the root uniformly from $V(G_n)$. The proportion of roots within any fixed distance of the boundary tends to zero, and the rooted trees converge locally to the uniform spanning tree $T$ of ${\mathbb{Z}}^2$. Since every degree is at most four, expectations also converge. Translation invariance therefore givesThe four edges incident to $0$ have equal inclusion probability by the rotations and reflections of the square lattice. If that common probability is $r$, then $4r=\mathbb{E}{\mathrm{deg}}_T(0)=2$. Consequentlyfor every edge $e$ by translation invariance.