Wednesday, August 7, 2019 - 2:00pm
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 representative districting plans as a function of the available 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-edge 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 and an application of isoperimetry to measuring compactness.