The ACO Seminar (2023–2024)

There has been a surge in interest in algorithms that sample balanced contiguous partitions of geometric regions, due to the use of such algorithms in the analysis of political districtings. Most approaches to the problem use Markov chains of various types, which in almost no practical case are known to be rapidly mixing. But recent breakthroughs in matroid theory enable highly efficient sampling of random forests, and Charikar, Liu, Liu, and Vuong conjectured that at least for grid graphs, a 1/poly fraction of random forests on k components (k a constant) have balanced component sizes. The key implication of their conjecture is that for grid graphs, there is a polynomial-time algorithm to sample from the /spanning-tree distribution/ on balanced partitions, which weights each balanced partition according to the product of the number of spanning trees of each partition class. We confirm their conjecture, and also prove that random forests of grid-like graphs have a 1/poly chance of having approximately balanced component sizes. The proofs make use of Wilson's random spanning tree algorithm, and leverage geometric properties of random walk in lattices.