Political Redistricting, Graph Partition Sampling, and Counting Spanning Trees

Abstract: Say you are handed a 10 X 10 grid graph and are asked to "randomly" partition the vertices into 10 connected subgraphs of 10 vertices each. How do you do it? From a complexity perspective, the asymptotic version of this question is largely unanswered, and even for these small specific parameters there are some very basic things we don't know how to do efficiently.

The primary motivation for these questions comes from an increasingly popular paradigm for fairness in political redistricting whereby electoral maps are judged in comparison to ensembles of randomly generated maps. This is a truly amazing area where mathematical theorems are actually having a positive societal impact, and the primary goal of this talk will be to inspire more interest in it. I'll focus on a recent paper of mine (https://arxiv.org/abs/2109.13394) that sheds light on one particular angle, but I will also discuss several tantalizing questions I was unable to answer, and are still very widely open.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456