Random Spanning Trees, Random Walks, and Electric Networks

Russell Lyons

Indiana University and Georgia Tech, visiting UC Berkeley

May 7,



  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, there are still an enormous number of
fascinating open questions. No background in any area will be assumed for
the talk.

Return to Applied Math Colloquium home page