for this workshop
Mathematical foundations of sampling connected balanced graph partitions
at the
American Institute of Mathematics, Pasadena, California
organized by
Sarah Cannon and Daryl DeFord
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.
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.
This event will be run as an AIM-style workshop. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.
Space and funding is available for a few more participants. If you would like to participate, please apply by filling out the on-line form no later than January 12, 2025. Applications are open to all, and we especially encourage women, underrepresented minorities, junior mathematicians, and researchers from primarily undergraduate institutions to apply.
Before submitting an application, please read the description of the AIM style of workshop.
For more information email workshops@aimath.org
