12th May 2008 — Matrix Tree Lemma

Yee Whye is going to go over the proof of the "Matrix Tree Lemma"

The matrix tree theorem, also called Kirchhoff's matrix-tree theorem (Buekenhout and Parker 1998), states that the number of nonidentical spanning trees of a graph G is equal to any cofactor of the degree matrix of G minus the adjacency matrix of G (Skiena 1990, p.235). (from MathWorld)

For a proof, see Lecture notes by L. Babai and T. Schelder

A reference related also to the previous MLJC meeting:
M. Meila and T. Jaakkola, Tractable Bayesian Learning of Tree Belief Networks, UAI 2000