- This event has passed.
Online Undergraduate Research Seminar – Greg Herschlag (Duke) and Andrew Sun
February 25 @ 3:30 pm - 4:30 pm
A Spectral Analysis of Tree Based Markov Chains for Redistricting Problems
Abstract. Optimal graph partitioning is a long-studied problem, however, there has recently been a flurry of activity in understanding typical (and atypical) graph partitions: Given a graph along with a probability measure on partitions, how can we determine whether certain partition properties are typical or atypical of the measure? This problem has close applications to understanding fairness in redistricting (i.e. detecting gerrymandering).
We will begin with a general introduction to ties between understanding typical graph partitions and fairness in redistricting. These problems have led to the development of novel Markov chains on balanced random forests. We analyze these Markov Chains from a spectral graph theory perspective. Working with graphs on which we can completely enumerate the space of partitions — including real-world datasets consisting of counties in North Carolina, as well as synthetic counterparts — we observe and analyze mixing properties related to the state space and target measures. We also show empirical evidence that our findings generalize to larger non-enumerable graphs. Our findings give insights into the efficacy of existing methods for auditing congressional gerrymanders.
