Algorithms, Combinatorics and Optimization Seminar
— 4:00pm
Location:
In Person
-
Wean Hall 8220
Speaker:
WESLEY PEGDEN
,
Associate Professor, Department of Mathematics, Carnegie Mellon University
https://www.math.cmu.edu/~wes/
Finding balance in random forests
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.
Tea and cookies after the talk in Wean 6220 (bring your own mug if you have one).
Event Website:
https://aco.math.cmu.edu/abs-23-24/jan25.html