David Wilson and a cover of Shlomo’s recent book “Curvature in mathematics and physics”
A few weeks ago, in David Kazhdan’s basic notion seminar, Shlomo Sternberg gave a lovely presentation Kirchhoff and Wilson via Kozdron and Stroock. The lecture is based on the work presented in the very recent paper by Michael J. Kozdron, Larissa M. Richards, and Daniel W. Stroock: Determinants, their applications to Markov processes, and a random walk proof of Kirchhoff’s matrix tree theorem. Preprint, 2013. Available online at arXiv:1306.2059.
Here is the abstract:
Kirchhoff’s formula for the number of spanning trees in a connected graph is over 150 years old. For example, it says that if are the nonzero eigenvalues of the Laplacian, then the number k of spanning trees is There are many proofs. An algorithm due to Wilson via loop erased random walks produces such a tree, and Wilson’s theorem is that all spanning trees are produced by his algorithm with equal probability. Hence, after the fact, we know that Wilson’s algorithm produces any given tree with probability 1/k. A proof due to Lawler, using the Green’s function, shows directly that Wilson’s algorithm has the probability 1/k of producing any given spanning tree, thus simultaneously proving Wilson’s theorem and Kirchhoff’s formula. Lawler’s proof has been considerably simplified by Kozdron and Stroock. I plan to explain their proof. The lecture will be completely self-contained, using only Cramer’s rule from linear algebra.
(Here are also lecture notes of the lecture by Ron Rosenthal.)
Here is some background.
The matrix-tree theorem
The matrix tree theorem asserts that the number of rooted spanning trees of a connected graph G is the product of the non-zero eigenvalues of L(G), the Laplacian of G.
Suppose that G has n vertices. The Laplacian of G is the matrix whose (i,i)-entry is the degree of the ith vertex, and its (i,j) entry for is 0 if the ith vertex is not adjacent to the jth vertex, and -1 if they are adjacent. So L(G)=D-A(G) where A(G) is the adjacency matrix of G, and D is a diagonal matrix whose entries are the degrees of the vertices. An equivalent formulation of the matrix-tree theorem is that the number of spanning trees is the determinant of a matrix obtained from the Laplacian by deleting the j th row and j th column.
How to generate a random spanning tree for a graph G?
Using the matrix-tree theorem
Method A: Start with an edge , use the matrix-tree theorem to compute the probability that e belongs to a random spanning tree of G, take e with probability . If e is taken consider the contraction and if G is not taken consider the deletion and continue.
This is an efficient method to generate a random spanning tree according to the uniform probability distribution. You can extend it by assigning each edge a weight and chosing a tree with probability proportional to the product of its weights.
Random weights and greedy
Method B: Assign each edge a random real number between 0 and 1 and chose the spanning tree which minimizes the sum of weights via the greedy algorithm.
This is a wonderful method but it leads to a different probability distribution on random spanning trees which is very interesting!
The Aldous-Broder random walk method
Method C: The Aldous-Broder theorem. Start a simple random walk from a vertex of the graph until reaching all vertices, and take each edge that did not form a cycle with earlier edges. (Or, in other words, take every edge that reduced the number of connected components of the graph on the whole vertex set and visited edges.)
Amazingly, this leads to a random uniform spanning tree. The next method is also very amazing and important for many applications.
David Wilson’s algorithm
Method D: Wilson’s algorithm. Fix a vertex as a root. (Later the root will be a whole set of vertices, and a tree on them.) Start from an arbitrary vertex u not in the root and take a simple random walk until you reach the root. Next, erase all edges in cycles of the path created by the random walk so you will left with a simple path from u to the root. Add this path to the root and continue!