Interlacements, Uniform Spanning Forests and the Aldous-Broder Algorithm.
In the 1980’s, Aldous and Broder independently proved that the collection of first-entry edges of a random on a finite graph is distributed as a uniform spanning tree of the graph; using this fact to sample the uniform spanning tree of a finite graph is known as the Aldous-Broder algorithm. In this talk, I will review the theorem of Aldous and Broder and discuss an extension of the Aldous-Broder algorithm to infinite graphs, in which the random walk is replaced by Sznitman’s random interlacement process. Time permitting, I will also show how this extension can be used to prove a few things about the wired uniform spanning forest.