Abstract

Generating Random Spanning Trees

Nick Weininger
Mon Feb. 16 at 1:10pm in Hill 423

A natural question in probabilistic combinatorics is: how can we efficiently pick a spanning tree of a graph uniformly at random? Relatively recent (1996) work of Propp and Wilson yields an elegant algorithm for generating random spanning trees, distributed either uniformly or according to a set of edge weights. The algorithm is based on Markov chains, and illuminates some nice connections between random walks and spanning trees; in particular, it gives a probabilistic proof of Cayley's formula for the number of spanning trees of a complete graph. I will present the algorithm and its proof of correctness, and discuss some applications.