How do you sample a random graph partition?Speaker: Jamie
Title: How do you sample a random graph partition?
Date: 12 Nov 2021 11:30-13:00 EST
Location: SEC Level 3 NW Terrace
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. In this talk, I’ll introduce the growing literature on balanced graph partition sampling that is motivated by applications to fairness in political redistricting. I’ll focus on a recent paper of mine 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.