Edge-inclusion formula for a uniform spanning tree Created 2026-10-05 Updated 2026-11-05
For a finite electrical network with positive electrical conductances , choose a spanning tree with lawThe one-edge case of the transfer-current theorem gives for . A unit injected electric current produces voltage , and Ohm's law makes the electric current along equal to .
In a triangle of unit resistors, one resistor is parallel to a series pair, so . Each edge consequently has inclusion probability , also clear from the three equally likely spanning trees. For a wired uniform spanning forest, take the finite wired limit and use the limiting wired effective resistance.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 214 4 d Solution Created 2026-10-03 Updated 2026-10-05
On a tree, every finite connected induced subgraph is itself a tree, and its only spanning tree contains all its edges. Thus the free uniform spanning forest is deterministic:Suppose for a contradiction that is a transient graph. By part (c), choose whose removal leaves two transient graph components . Let be their effective resistances to infinity measured from their respective endpoints.
In a wired finite exhaustion, the edge of resistance one is in parallel with the route from through to the wired boundary and back through to . The latter route has resistance , converging to . Consequently the limiting wired effective resistance isThe edge-inclusion formula for a uniform spanning tree, the one-edge case of the transfer-current theorem, states that an edge of conductance is present with probability . Passing to the wired limit and using givesBut under the free uniform spanning forest, is present with probability one. This contradicts . Therefore the tree is recurrent. Combined with part (b), this characterizes equality of the free and wired uniform spanning forests on locally finite unweighted trees.
Transfer current 2026-11-05
In a finite connected graph with unit edge electrical resistances, orient two edges and . The transfer current is the signed current through when one unit of electric current is injected at and removed at . If is the resulting vertex potential, Ohm's law giveswhere is the graph Laplacian. Potentials are determined up to an additive constant, which cancels in the difference.
On a unit-resistance triangle, injecting across one edge sends of the current along that edge and along the two-edge alternative path. Thus . The transfer-current theorem identifies this diagonal value with the probability that the edge belongs to a uniform spanning tree; exactly two of the triangle's three spanning trees contain it.
Electrical reciprocity makes the unit-resistance kernel symmetric. Reversing one edge orientation changes the appropriate sign, while the determinants giving joint tree-edge probabilities remain unchanged.[ref]
Local Characteristics, Entropy and Limit Theorems for Spanning Trees and Domino Tilings via Transfer-Impedances by Robert Burton and Robin Pemantle. Theorem1.1 and section4, transfer-impedance kernel and determinants