Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 209 / 4 / b

Table of contents
- Solution b

Solution

The reduced graph Laplacian is

L^{(0)} = Δ (I - P^{(0)})

. By the matrix-tree theorem, the number

τ (D)

of spanning trees is

τ (D) = det L^{(0)} = Δ^{n} det (I - P^{(0)}) .

Combining this with part (a) gives

\prod_{j = 1}^{n} g_{D ∖ {x_{0}, \dots, x_{j - 1}}} (x_{j}) = \frac{Δ ^{n}}{τ ( D )} .

This is also the normalization behind Wilson algorithm: loop-erased random walks attach the vertices successively, and the order-independent product ensures that every rooted spanning tree has probability

1/ τ (D)

.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version