A discrete districting plan

Alberto Saracco; Giorgio Saracco; Alberto Saracco; Giorgio Saracco

doi:10.3934/nhm.2019031

Networks and Heterogeneous Media

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

Previous Article Next Article

A discrete districting plan

Alberto Saracco ^{1
,},
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

Received: 01 January 2019 Revised: 01 June 2019
Primary: 91D20; Secondary: 49Q10, 52C99

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.
- Isoperimetric problem,
- graphs,
- networks,
- discrete geometry,
- gerrymandering
Citation: Alberto Saracco, Giorgio Saracco. A discrete districting plan[J]. Networks and Heterogeneous Media, 2019, 14(4): 771-788. doi: 10.3934/nhm.2019031

Related Papers:

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.

References

[1]	Bicolored graph partitioning, or: Gerrymandering at its worst. Discrete Appl. Math. (2009) 157: 3601-3614.
[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]	(1982) Fair Representation: Meeting the Ideal of One Man, One Vote. New Haven, Conn.: Yale University Press.
[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).
[8]	Recent advances in graph partitioning. Algorithm Engineering, Lecture Notes in Comput. Sci., Springer, Cham (2016) 9220: 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]	Su una teoria generale della misura (r-1)-dimensionale in uno spazio ad r dimensioni. Ann. Mat. Pura Appl. (1954) 36: 191-213.
[12]	M. Duchin and B. Tenner, Discrete geometry for electoral geography, arXiv: 1808.05860.
[13]	A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. (1994) 19: 24-37.
[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.
[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.
[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.
[19]	L. Lovász, Large Networks and Graph Limits, American Mathematical Society Colloquium Publications, 60. American Mathematical Society, Providence, RI, 2012.
[20]	Limits of dense graph sequences. J. Combin. Theory Ser. B (2006) 96: 933-957.
[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]	On the isoperimetric problem with double density. Nonlinear Anal. (2018) 177: 733-752.
[24]	Political districting: From classical models to recent approaches. Ann. Oper. Res. (2013) 204: 271-299.
[25]	Weighted Cheeger sets are domains of isoperimetry. Manuscripta Math. (2018) 156: 371-381.
[26]	Einfacher Beweis der isoperimetrischen Hauptsätze. J. Reine Angew. Math. (1838) 18: 281-296.
[27]	R. J. Wilson, Introduction to Graph Theory, Fourth edition, Longman Group Ltd., Longman, Harlow, 1996.

Reader Comments

Your name:*

Email:*
© 2019 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)