Keith Frankston, Rutgers University

Abstract

Cayley's formula states that the number of labeled spanning trees of K_n is n^{n-2}. How many of those spanning trees contain a fixed forest? Can you generate a uniformly random spanning tree algorithmically? Can you generate a uniformly random spanning tree containing a fixed forest? We will answer some subset of these questions; come to the talk to find out which ones!