Markov chains and sampling methods for contiguous partitions

Combinatorics Seminar
Friday, November 18, 2022 - 3:00pm for 1 hour (actually 50 minutes)
Skiles 202
Wesley Pegden – Carnegie Mellon University –
Anton Bernshteyn

With applications in the analysis of political districtings, Markov chains have become and essential tool for studying contiguous partitions of geometric regions. Nevertheless, there remains a dearth of rigorous results on the mixing times of the chains employed for this purpose. In this talk we'll discuss a sub-exponential bound on the mixing time of the Glauber dynamics chain for the case of bounded-size contiguous partition classes on certain grid-like classes of graphs.