Mathematical foundations of sampling connected balanced graph partitions
June 2 to June 6, 2025
at the
American Institute of Mathematics,
Pasadena, California
organized by
Sarah Cannon and Daryl DeFord
Original Announcement
This workshop will be devoted to providing formal analysis and theoretical justification of Markov chain methods for sampling graph partitions. While these methods have seen significant use in empirical projects motivated by political redistricting, there are still many open questions about standard properties of the Markov chain proposals. This includes determining sets of parameters for the random walks and underlying graphs under which we can provide rigorous guarantees about irreducibility, mixing time, and more. Additionally, recent work has further shown the importance of understanding the properties of random spanning trees and tree-weighted partitions used in these methods. The goal of this workshop is to bring together experts in Schramm–Loewner evolution and related processes (including loop-erased random walks), Markov chain theory, spanning tree methods, computational geometry, and graph theory (planar/near-planar graphs and their random substructure) to address these fundamental problems.
The main topics for the workshop are:
- Proving rigorous guarantees about the performance of the most commonly used Markov chains for sampling connected graph partitions (such as irreducibility, mixing time, rejection rates, and more).
- Determining the properties of randomly constructed spanning trees of a fixed graph, beginning with the probability they can be split into balanced pieces, and how these relate to properties of tree-weighted partitions.
- Studying and classifying the class of graphs that we want to partition, which arise as dual graphs in the redistricting application that motivated the development of these sampling algorithms and related hardness results.
Material from the workshop
A list of participants.
The workshop schedule.
A report on the workshop activities.
