Handouts
- The book
“Random Walks and Electrical Networks”
by Doyle and Snell
is available for free from
Peter Doyle's homepage.
-
The book
“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,
and determinants.
-
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
Algebraic Combinatorics.
-
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
Tarjan.
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).