Abstract (click to read)

The problem of constructing "fair" political districts and related disputes around detecting intentional gerrymandering have received a significant amount of attention in recent years. A key question in this area is determining the expected properties of a representative districting plan as a function of the input geographic and demographic data. One 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.