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