AIM Workshop: Mathematical Foundations of Sampling Connected Balanced Graph Partitions

This workshop, sponsored by AIM and the NSF, 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.