Title: Hardness results for sampling connected graph partitions with applications to redistricting
Speaker: Daryl DeFord, MIT
Abstract: The problem of constructing ”fair'' political districts and the related problem of detecting intentional gerrymandering has received a significant amount of attention in recent years. A key problem in this area is determining the expected properties of a representative districting plan as a function of the input geographic and demographic data. A natural approach is to generate a comparison ensemble of plans using MCMC and I will present successful applications of this approach in both court cases and legislative reform efforts. However, our recent work has demonstrated that the commonly used boundary-node flip proposal can mix poorly on real-world examples. In this talk, I will present some new proposal distributions for this setting and discuss some related open problems concerning mixing times and spanning trees. I will also discuss some generic hardness results for sampling problems on partitions of planar graphs.
Seminar URL: https://tgda.osu.edu