Spanning trees and intersection properties of random walk

Supervisor: Tyler Helmuth

Research area: probability.

Description:

A tree is a connected graph with the property that deleting any edge results in a disconnected graph. Given a finite connected graph, there is associated a finite set of spanning trees: connected subgraphs of the graph that are trees. What does a uniformly chosen such tree look like? This could be of recreational interest for generating a maze, but it is also of interest for various algorithmic applications, and as a theoretical model in statistical mechanics. For the latter topic it turns out to be of interest to look at uniformly chosen spanning trees of infinite graphs. The definition of such an object is not at all obvious, and turns out to be related to properties of simple random walk.

Individual Project:

The individual project will revolve around your interests. Some core topics will include:

  • Wilson’s algorithm for generating a uniform spanning tree. Alternative algorithms.
  • The construction of infinite-volume spanning tree measures on recurrent graphs.
  • The construction of infinite-volume spanning tree measures on transient graphs.

From here you might decide to investigate:

  • Partial rejection sampling algorithms for other combinatorial structures.
  • The connectivity properties of infinite-volume spanning trees.
  • The intersection properties of simple random walk and their use in studying loop-erased random walk and spanning trees.
  • The geometry of uniformly chosen spanning trees, e.g., on the complete graph.
  • Other topics of your interest concerning random walks and/or spanning trees.

Mode of Operation and Evidence of Learning for the individual project

The project will revolve around learning by reading, with a focus on theory, mathematical rigour, and the development of conceptual understanding. Students will demonstrate their understanding by: solving relevant problems; exploring examples and theoretical applications of the material; clearly communicating in both written and oral formats.

Prerequisites and Co-requisites

Probability II

Resources (in progress)