Sampling Balanced Forests of Grids in Polynomial Time

Motivated by a potential sampling method for districting problems, Charikar, Liu, Liu, and Vuong conjectured that for constant k, random k-component spanning forests of grid graphs on n vertices have balanced component sizes with probability at least 1/poly(n). In this talk we’ll give a proof of this conjecture, which provides the first polynomial-time algorithm to sample random partitions of grid graphs from the balanced spanning tree distribution.