Lawler-Kozdron-Richards-Stroock’s combined Proof for the Matrix-Tree theorem and Wilson’s Theorem

wilson  curvature

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 Kirchho ff 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 c_2, \dots, c_n are the nonzero  eigenvalues of the Laplacian, then the number k of spanning trees is k= (1/n)c_2\cdots c_n. 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 i \ne j 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.

We considered a high dimensional generalization of the matrix tree theorem in these posts (I, II, III, IV).

How to generate a random spanning tree for a graph G?

Using the matrix-tree theorem

Method A: Start with an edge e \in G, use the matrix-tree theorem to compute the probability p_e that e belongs to a random spanning tree of G, take e with probability p_e. If e is taken consider the contraction G/e and if G is not taken consider the deletion G \backslash e 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!

Here is a link to Wilson’s paper! Here is a nice presentation by Chatterji  and Gulwani.

About these ads
This entry was posted in Combinatorics, Computer Science and Optimization, Probability and tagged , , . Bookmark the permalink.

4 Responses to Lawler-Kozdron-Richards-Stroock’s combined Proof for the Matrix-Tree theorem and Wilson’s Theorem

  1. Michael Kozdron says:

    The proof of Wilson’s algorithm that we present is due to Greg Lawler and can be found in his paper “Loop-Erased Random Walk” in “Perplexing Problems in Probability: Festschrift in Honor of Harry Kesten” (Birkhauser, 1999, p 197-217). Our original goal was an expository account of how Kirchhoff’s matrix tree theorem follows from Lawler’s proof of Wilson’s algorithm. While working on that write-up, however, we discovered that the proof techniques lead to an explicit computational formula for the stationary distribution of certain Markov chains and processes (Theorem 4.2 in the preprint). Here is a talk that Larissa Richards gave recently to undergrads about this proof of Kirchhoff’s theorem.

    http://stat.math.uregina.ca/~kozdron/Research/UgradTalks/KRS_MTT.pdf

  2. Jernej says:

    A very cute and short proof of Kirchhoff theorem is to use induction http://mathoverflow.net/a/73400/1737

  3. Another interesting algorithm for generating random spanning trees is via chip-firing/the abelian sandpile model; see for instance this paper: http://arxiv.org/pdf/1107.1313v2.pdf.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s