Article Contents
Article Contents

# A discrete districting plan

• * Corresponding author: G. Saracco

A. Saracco was partially supported by INdAM-GNSAGA. G. Saracco was partially supported by the INdAM-GNAMPA 2019 project "Problemi isoperimetrici in spazi Euclidei e non"

• The outcome of elections is strongly dependent on the districting choices, making thus possible (and frequent) the gerrymandering phenomenon, i.e. politicians suitably changing the shape of electoral districts in order to win the forthcoming elections. While so far the problem has been treated using continuous analysis tools, it has been recently pointed out that a more reality-adherent model would use the discrete geometry of graphs or networks. Here we propose a parameter-dependent discrete model for choosing an "optimal" districting plan. We analyze several properties of the model and lay foundations for further analysis on the subject.

Mathematics Subject Classification: Primary: 91D20; Secondary: 49Q10, 52C99.

 Citation:

• Figure 1.  Removing or adding a vertex; numbers correspond to the weight of the vertexes; all edges are supposed to have weight $1$

Figure 2.  Removing or adding an edge; numbers correspond to the weight of the related vertexes and edges

Figure 3.  Splitting two vertexes is not always possible by simply modifying the weight of their common edge

Figure 4.  A graph where the optimal $4$-partition is not a $2$-refining of the optimal $2$-partition

Figure 5.  A graph where the optimal $4$-partition is a $2$-refining of the optimal $2$-partition, but does not induce the optimal $2$-partitions on its components

Figure 6.  A graph where the optimal $4$-partition is not a $2$-refining of the optimal $2$-partition for suitable choices of $\alpha = \alpha(p)$

Figure 7.  A graph where the optimal $4$-partition is not a $2$-refining of the optimal $2$-partition

•  [1] N. Apollonio, R. I. Becker, I. Lari, F. Ricca and B. Simeone, Bicolored graph partitioning, or: Gerrymandering at its worst, Discrete Appl. Math., 157 (2009), 3601-3614.  doi: 10.1016/j.dam.2009.06.016. [2] K. J. Arrow, Social Choice and Individual Values, Cowles Commission Monograph No. 12, John Wiley & Sons, Inc., New York, N. Y., Chapman & Hall, Ltd., London, 1951. [3] M. L. Balinski and  H. P. Young,  Fair Representation: Meeting the Ideal of One Man, One Vote, Yale University Press, New Haven, Conn., 1982. [4] S. Bangia, C. V. Graves, G. Herschlag, H. S. Kang, J. Luo, J. Mattingly and R. Ravier, Redistricting: Drawing the line, arXiv: 1704.03360v2. [5] R. Barnes and J. Solomon, Gerrymandering and compactness: Implementation flexibility and abuse, arXiv: 1803.02857v1. [6] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976. [7] A. Braides, P. Cermelli and S. Dovetta, Γ-limit of the cut functional on dense graph sequences, ESAIM Control Optim. Calc. Var., (2019). doi: 10.1051/cocv/2019029. [8] A. Buluç, H. Meyerhenke, I. Safro, P. Sanders and C. Schulz, Recent advances in graph partitioning, Algorithm Engineering, Lecture Notes in Comput. Sci., Springer, Cham, 9220 (2016), 117-158. [9] R. Cerf, The Wulff Crystal in Ising and Percolation Models, Lecture Notes in Mathematics, 1878. Springer-Verlag, Berlin, 2006. [10] D. De Ford, H. Lavenant, Z. Schutzman and J. Solomon, Total variation isoperimetric profiles, arXiv: 1809.07943. [11] E. De Giorgi, Su una teoria generale della misura (r-1)-dimensionale in uno spazio ad r dimensioni, Ann. Mat. Pura Appl., 36 (1954), 191-213.  doi: 10.1007/BF02412838. [12] M. Duchin and B. Tenner, Discrete geometry for electoral geography, arXiv: 1808.05860. [13] O. Goldschmidt and D. Hochbaum, A polynomial algorithm for the k-cut problem for fixed k, Math. Oper. Res., 19 (1994), 24-37.  doi: 10.1287/moor.19.1.24. [14] P. Grilli di Cortona, C. Manzi, A. Pennisi, F. Ricca and B. Simeone, Evaluation and Optimization of Electoral Systems, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. doi: 10.1137/1.9780898719819. [15] G. Herschlag, H. S. Kang, J. Luo, C. Vaughn Graves, S. Bangia, R. Ravier and J. Mattingly, Quantifying gerrymandering in North Carolina, (2018), arXiv: 1801.03783. [16] G. Herschlag, R. Ravier and J. Mattingly, Evaluating partisan gerrymandering in Wisconsin, 2017, arXiv: 1709.01596. [17] G. P. Leonardi and G. Saracco, Two examples of minimal Cheeger sets in the plane, Ann. Mat. Pura Appl. (4), 197 (2018), 1511–1531. doi: 10.1007/s10231-018-0735-y. [18] G. P. Leonardi and G. Saracco, The prescribed mean curvature equation in weakly regular domains, Nonlinear Differ. Equ. Appl., 25 (2018), Art. 9, 20 pp. doi: 10.1007/s00030-018-0500-3. [19] L. Lovász, Large Networks and Graph Limits, American Mathematical Society Colloquium Publications, 60. American Mathematical Society, Providence, RI, 2012. doi: 10.1090/coll/060. [20] L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B, 96 (2006), 933-957.  doi: 10.1016/j.jctb.2006.05.002. [21] J. Mattingly and C. V. Graves, Redistricting and the will of the people, arXiv: 1410.8796v1. [22] A. Pratelli and G. Saracco, The ε - εβ property in the isoperimetric problem with double density, and the regularity of isoperimetric sets, arXiv: 1910.06307. [23] A. Pratelli and G. Saracco, On the isoperimetric problem with double density, Nonlinear Anal., 177 (2018), 733-752.  doi: 10.1016/j.na.2018.04.009. [24] F. Ricca, A. Scozzari and B. Simeone, Political districting: From classical models to recent approaches, Ann. Oper. Res., 204 (2013), 271-299.  doi: 10.1007/s10479-012-1267-2. [25] G. Saracco, Weighted Cheeger sets are domains of isoperimetry, Manuscripta Math., 156 (2018), 371-381.  doi: 10.1007/s00229-017-0974-z. [26] J. Steiner, Einfacher Beweis der isoperimetrischen Hauptsätze, J. Reine Angew. Math., 18 (1838), 281-296.  doi: 10.1515/crll.1838.18.281. [27] R. J. Wilson, Introduction to Graph Theory, Fourth edition, Longman Group Ltd., Longman, Harlow, 1996.

Figures(7)