Graduation Year
2025
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Arts
Department
Mathematics
Reader 1
Sarah Cannon
Reader 2
Winston Ou
Abstract
This work expands a recently proven conjecture that a polynomial fraction of all uniform spanning trees (USTs) are splittable into k balanced partitions on grid graphs to real-world political districting plans. We investigate whether similar structural properties hold for the planar dual graphs of U.S. counties (cnty) and tracts (t), using Wilson’s algorithm to generate uniform random spanning trees and Breadth- First Search (BFS) to check for splitability into balanced partitions. Our empirical findings suggest that real-world districting plans can be split into 2-balanced, connected partitions in a fraction of polynomial time. This result highlights the potential for scalable redistricting algorithms that preserve connectivity and balance while improving computational efficiency. By bridging the gap between theoretical guarantees and practical applications, this work contributes to the broader computational redistricting community, providing empirically driven results that advance efficient, unbiased partitioning techniques for electoral districting.
Recommended Citation
Feinberg, Brooke C., "Empirical Analysis of Political Districting Splitability via Uniform Spanning Trees in Polynomial Time" (2025). Scripps Senior Theses. 2691.
https://scholarship.claremont.edu/scripps_theses/2691
Included in
Data Science Commons, Discrete Mathematics and Combinatorics Commons, Theory and Algorithms Commons
