Previous: 5th May 2008 — no meeting

Next: 19th May 2008 — no meeting

# 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

Dilan Görür