Random Sampling of Connected Balanced Graph Partitions

Zoom Link

This talk will consider various methods for sampling connected balanced graph partitions, a problem that has applications to understanding political districting and gerrymandering. The most widely-used approach is a recombination Markov chain, but there remain many open questions about this chain, such as whether it’s irreducible and what its mixing time is. Another approach is to use an up-down Markov chain, but this frequently produces unbalanced partitions, where there are wildly unequal numbers of vertices in each part. However, in a recent result, we prove that in grid graphs and lattice-like graphs, at least a polynomial fraction of the time, a partition sampled with this method will be balanced. The proof involves a careful study of the properties of random spanning trees via Wilson’s Algorithm.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.