- The book
“Random Walks and Electrical Networks”
by Doyle and Snell
is available for free from
Peter Doyle's homepage.
“Probability on Trees and Networks”
by Lyons and Peres covers many topics
related to this course. Chapter 4 contains an excellent discussion
of random spanning trees, Wilson's algorithm for sampling them,
and connections between random spanning trees, electrical networks,
If you want to understand some more about the combinatorics
underlying Kirchhoff's matrix-tree theorem, the paper
Chip-firing games, potential theory on graphs, and spanning trees
by Baker and Shokrieh is an excellent place to start. They give
an “efficient bijective” proof of the theorem.
A different combinatorial proof of Kirchhoff's Theorem,
working directly with the definition of the determinant
as a sum over permutations, can be found in
these lecture notes by Lionel Levine.
A different proof of Kirchhoff's Theorem, using the Cauchy-Binet
formula, is presented in
Chapter 9 of Richard Stanley's course notes for
Yet another proof of Kirchhoff's Theorem, using an algebraic fact
that looks similar to Cauchy-Binet but is slightly different, is in
these lecture notes by Nikhil Srivasatava.
Lecture notes on Cheeger's Inequality
by Dan Spielman.
We will be discussing Spielman and Teng's paper
Spectral partitioning works: Planar graphs and finite element meshes
(Linear Algebra and its Applications 421 (2-3), 2007, original
version appeared in FOCS 1996).
We will also be discussing the planar separator theorem of Lipton and
These notes by Jeff Erickson contain
an elementary proof due to Alon, Seymour, and Thomas, as well as a
proof based on circle packing due to Spielman and Teng. The
circle packing proof depends on a non-trivial result by Miller, Teng,
Thurston, and Vavasis from their paper
Separators for sphere-packings and nearest neighbor graphs
(J. ACM 44(1), 1997).