The University of Michigan Mathematics Colloquium
Fall 2001
October 23, 4:10-5:00, 1360 East Hall





Random Spanning Trees, Random Walks, and Electric Networks

Russell Lyons

Indiana University and Georgia Tech




Abstract

The topics of the title are intimately connected to each other, and to a host of other topics, in beautiful ways. It has been known since the time of Kirchhoff (1847) that one can solve electrical network problems by using various probabilities associated to choosing a spanning tree at random (uniformly) from a finite graph. Algorithms for generating a random spanning tree are connected to generation and counting of states in arbitrary Markov chains. A ``thermodynamic'' limit defines the model on infinite graphs. Here, the connections to potential theory deepen and allow one to resolve many questions, such as the number of components and the topology of components. We will describe work on random spanning trees of Aldous, Benjamini, Broder, Burton, Kenyon, Kesten, Kirchhoff, Pemantle, Peres, Schramm, Wilson, and the speaker. Because of connections to other areas such as domino tilings, matroids, amenability, percolation, L^2-Betti numbers, Brownian motion, and conformal maps, a lot is known, yet there are still an enormous number of fascinating open questions. No background in any area will be assumed for the talk.