Electrical Networks, Random Spanning Trees, and Correlation Inequalities
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1