A discrete districting plan

Alberto Saracco; Giorgio Saracco

doi:10.3934/nhm.2019031

Article Contents

2019, Volume 14, Issue 4: 771-788. Doi: 10.3934/nhm.2019031

This issue Previous Article Remarks on the Schrödinger-Lohe model Next Article Emergent behavior of Cucker-Smale model with normalized weights and distributed time delays

A discrete districting plan

Alberto Saracco^1, and
Giorgio Saracco^2, ,

1.
Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università di Parma, Parco Area delle Scienze 53/A, I-43124 Parma, Italy
2.
Dipartimento di Matematica, Università di Pavia, via Ferrata 5, I-27100 Pavia, Italy

^* Corresponding author: G. Saracco
^* Corresponding author: G. Saracco

Received: January 2019

Revised: June 2019

Published: December 2019

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"

Abstract / Introduction Full Text(HTML) Figure(7) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

FullText(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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) $

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[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.