Friday, December 14, 2007
3:30 pm, MC 5158

David Wagner
University of Waterloo

Electrical Networks, Random Spanning Trees, and Correlation Inequalities

In 1847 Kirchhoff derived a beautiful formula for the effective conductance of an electrical network $G$: it is a rational function of the edge conductances, and both the numerator and the denominator are generating functions for spanning trees of graphs related to $G$. Physically intuitive properties of an electrical network thus acquire meaning as probabilistic or analytic statements about the set of spanning trees of a graph. These statements can be generalized in several ways --- by considering spanning forests (or spanning connected subgraphs) instead of spanning trees, or by considering matroids more general than graphs.
A myriad of conjectures and open problems arise. I'll give a non-technical overview of the subject, emphasizing the big unsolved problems and the progress that has recently been made towards settling them.

Three students at Waterloo -- Mike LaCroix, Stephanie Phillips, and Yehua Wei --- have made substantial contributions to this progress.