The (homological) persistence of gerrymandering

Figure 1.  This paper studies the aggregation of votes from geographic units to districts, which is intractable to study by complete enumeration of possibilities. We develop persistent homology techniques to summarize the districting problem. This figure shows a precinct map of Pennsylvania with key cities identified. The precincts are colored by voting results from the 2016 Presidential election (blue for Democratic, red for Republican). Current districts in Pennsylvania are shown with the same coloring. Note that the Congressional districts are balanced to within one-person population deviation (by 2010 Census count)

Figure 2.  Abstract graph representations of three 18-district plans for Pennsylvania

Figure 3.  The main method: turning a districting plan into a persistence diagram. The persistence diagram captures both the adjacency information and the vote shares for the districts in a plan

Figure 4.  Pairing each plan in a districting ensemble with PRES16 vote data gives an ensemble of persistence diagrams. These plots show overlays of the diagram ensembles for $ k = 18, 50, 203 $ respectively. In the second row, we add the Fréchet mean $ \mathcal{F} $ for each ensemble, shown in red, representing an "average" persistence diagram for the ensemble

Figure 5.  Overlaid persistence diagrams with Fréchet mean (in red) for each of the NC ensembles (with PRES16 vote data)

Figure 6.  Overlaid Fréchet means for various elections in PA. In all three levels of redistricting, the geographic localization is strong enough to label the Pittsburgh feature (circled)

Figure 7.  Comparison for the weighted ensembles of Senate plans, with Democratic-favoring in blue and Republican-favoring in red. The simple weighting adjustment to the Markov chain has successfully created a difference of 3-4 seats between the ensemble means. Despite the significant change in the partisan outcome, we see only small movement in the Fréchet means

Figure 8.  Geographical localization of Fréchet features in Pennsylvania Congressional and Senate plans $ (k = 18, k = 50) $ with respect to PRES16 voting. The Senate features fairly clearly capture the medium-sized cities of Pennsylvania

Figure 9.  We isolate the Fréchet means for two successive Presidential elections in PA. The mean for PRES12 has a third off-diagonal feature at Scranton, while PRES16 does not. A uniform partisan swing would show each red point displaced by $ (.03, .03) $ relative to its paired green point, so the diagram summarizes the non-uniformity of the electoral shift

Figure 10.  Comparison of point plots for the successive Fréchet features in the PA Senate ensembles that are biased for Democratic and Republican safe seats, respectively. Note the contrast between the rigidity of the Erie feature (similar placement for both ensembles) and the manipulability of the Harrisburg feature, though both anchor competitive districts

Figure 11.  Maps of North Carolina. Top: results from the 2016 Presidential election (blue for Democratic, red for Republican). Bottom: North Carolina has a significant rural Black population, unlike Pennsylvania. Greenville and Wilson are the largest towns in the Northeast, but they are not the hubs of Black population

Figure 12.  Geographical localization of Fréchet features in North Carolina Congressional and Senate plans $ (k = 13, k = 50) $ with respect to PRES16 voting

Figure 13.  Overlaid Fréchet means for various elections in NC. In all three levels of redistricting, the geographic localization is strong enough to label the second and third features, shown circled, as Charlotte (left) and Asheville (right)

Figure 14.  Comparing two enacted Congressional plans for North Carolina with the ensemble mean, against the PRES16 vote pattern in all three cases

Figure 15.  Comparison of point plots for the successive Fréchet features in the NC Senate ensembles that are biased for Democratic and Republican safe seats, respectively

Figure 16.  A small change to districts can cause a large change in persistence. In this example (closely modeled on the enacted NC Congressional plan from 2012) we have changed the assignment of only one geographic unit (a precinct of 3, 300 people), and it removes a highly persistent off-diagonal feature

Figure 17.  Maps of enacted plans before and after perturbation by 1000 flip steps; district adjacencies changed in both cases (e.g., blue/lavender for Congress, and purple/purple for state Senate districts in the Southeast). Nonetheless we see only a small change in persistence, which is typical for repetitions of this experiment

Figure 18.  Effect of iterating small geographic perturbations (single-unit flip steps) on persistence. The red line indicates the average bottleneck distance over the $ {100 \choose 2} $ plans in a ReCom ensemble $ \mathcal{E} = \{P^{(1)}, \dots, P^{(100)}\} $, shown as a baseline for the distance between approximately independent plans. For each $ i = 1, \dots, 100 $, we run 1000 flip steps from $ P^{(i)} $ and track the bottleneck distance to $ P^{(i)} $. For $ k = 18 $, the persistence diagrams are seen to be stable. The same is true for most 50-district plans, but not all

Figure 19.  Histograms of statistics of the dual graphs for the ensemble of 1000 18-district plans for Pennsylvania. (Density is the ratio of the number of edges to the number of possible edges, $ {18 \choose 2} = 153 $.)

Figure 20.  Geographical localization of eleven Fréchet features in Pennsylvania House plans $ (k = 203) $ with respect to PRES16 voting. These now pinpoint small cities, all the way down to Hermitage (population 16, 220)

Figure 21.  Expanding on Figure 10. Point plots and heat maps for the successive Fréchet features in the PA Senate ensembles that are biased for Democratic and Republican safe seats, respectively. Note the contrast between the rigidity of the Erie feature (similar placement for both ensembles) and the manipulability of the Harrisburg feature, though both anchor competitive districts

Figure 22.  Geographical localization of ten Fréchet features in North Carolina Senate plans $ (k = 50) $ with respect to PRES16 voting

Figure 23.  Comparison of point plots and heat maps for the successive Fréchet features in the NC Senate ensembles that are biased for Democratic and Republican safe seats, respectively

Figure 24.  Location and average number of districts in connected components of Democratic-won districts for Pennsylvania Congressional plans ($ k = 18 $) with respect to PRES16 voting

Figure 25.  Location and average number of districts in connected components of Democratic-won districts for Pennsylvania state Senate plans ($ k = 50 $) with respect to PRES16 voting

Figure 26.  Location and average number of districts in connected components of Democratic-won districts for Pennsylvania state House plans ($ k = 203 $) with respect to PRES16 voting

Figure 27.  Location and average number of districts in connected components of Democratic-won districts for North Carolina Congressional plans ($ k = 13 $) with respect to PRES16 voting

Figure 28.  Location and average number of districts in connected components of Democratic-won districts for North Carolina state Senate plans ($ k = 50 $) with respect to PRES16 voting

Figure 29.  Location and average number of districts in connected components of Democratic-won districts for North Carolina state House plans ($ k = 120 $) with respect to PRES16 voting

Figure 30.  Distribution of pairwise bottleneck distances in the Pennsylvania ReCom ensembles. The distances help contextualize the size of the displacement by Flip steps

Figure 31.  Effect of iterating ReCom steps (merging and resplitting pairs of adjacent districts) on bottleneck distance. We choose 100 starting plans $ P^{(i)} $ from our Pennsylvania ensembles. For each of $ i = 1, \dots, 100 $, we run 1000 ReCom steps (with no subsampling) from $ P^{(i)} $ and track the bottleneck distance to $ P^{(i)} $ on the $ y $-axis