Andrew Sun Research Project

Andrew Sun (Duke/UNC Robertson Scholar)

Title: Applications of spectral graph theory to the problem of quantifying gerrymandering.

Summary: Every 10 years, the U.S. distributes a census that updates the country’s population and determines the reallocation of representative seats in legislatures. As part of this process, in most states, state legislatures are entrusted with the power to redraw districting plans in accordance with updated census data, as well as a slew of other non-partisan criteria. Partisan gerrymandering is the process by which legislatures draw maps that are biased toward one political party over another. In doing so, the party in power can effectively ensure they are re-elected to the majority party, even if a non-partisan map would have resulted in a shift of power.

The problem of gerrymandering and its structurally perverse incentives has inhabited the political system for the last few centuries, and the rise of computational mathematics has prompted an increased focus on their intersection. There are several normative measures that have been proposed that simplify gerrymandering to some characteristic feature. For instance, one can naively argue that if a state with a 55 percent blue vote elects only a 45 percent blue seat count to its state legislature, the redistricting plan is a gerrymander due to its violation of a natural sense of proportionality.

Increasingly, mathematicians have turned to empirical methods of evaluating gerrymandering, spearheaded by, among others, those in the Duke Mathematics Department. The ensemble method involves formalizing the non-partisan criteria in a state’s constitution, sampling a critical mass from the larger, innumerable population, and comparing features of the numerically derived, average reasonable map to the map proposed by the legislature [9]. These methods were presented by expert witness testimony in court cases such as Common Cause v Lewis, which resulted in the overturning of North Carolina’s Congressional map ahead of the 2020 general election.

Much of the deliberation around the ensemble method and its effectiveness has centered around the ways in which one can accurately sample from an innumerable population of ”reasonable” maps. Mathematicians model the problem by reducing a districting plan to a graph, where each node represents a district and an edge between two nodes represents the adjacency between two districts. To sample random districts, one might execute different variations of a random walk on the graph of the entire state, using what are called MCMC (Markov Chain Monte Carlo) methods.

One natural question arising from such a direction is as follows: how can one ensure that the sampling scheme is representative of the larger population? For instance, random walks can often encounter high energy thresholds or energy bottlenecks. Do barriers like these simply slow down the convergence time, or do they prevent MCMC algorithms from producing a representative ensemble?

Examining the spectral properties of graphs will first and foremost reveal more about the state spaces: the presence of clustering, energy thresholds, and other properties related to graph connectivity. These are important characteristics because they allow researchers to learn more about a relatively unknown space, which can motivate future work and prevent errors previously unknowable to modelers.

In addition, spectral graph theory can motivate the comparison between different algorithms used to generate ensembles, which has been a focal point of redistricting literature. One natural comparison is the mixing time of a particular algorithm. Characterizing the connection between mixing time and the connectivity of the state space will generate conclusions about the feasibility of an algorithm both in general and specifically with regard to the space being analyzed.

The research project ”Spectral Gerrymandering” entailed two semesters: one at Duke, and one at UNC. The intention is to thoroughly analyze an enumerable state space in order to develop the machinery necessary to analyze more complicated, innumerable examples (such as an entire state), which will ultimately advance the rigorous understanding of the representativeness of ensembles used to indict proposed maps as partisan gerrymanders in state court.