December  2019, 14(4): 771-788. doi: 10.3934/nhm.2019031

A discrete districting plan

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

Received  January 2019 Revised  June 2019 Published  October 2019

Fund Project: 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.

Citation: Alberto Saracco, Giorgio Saracco. A discrete districting plan. Networks & Heterogeneous Media, 2019, 14 (4) : 771-788. doi: 10.3934/nhm.2019031
References:
[1]

N. ApollonioR. I. BeckerI. LariF. 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.  Google Scholar

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

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

[5]

R. Barnes and J. Solomon, Gerrymandering and compactness: Implementation flexibility and abuse, arXiv: 1803.02857v1. Google Scholar

[6]

J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.  Google Scholar

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

[8]

A. BuluçH. MeyerhenkeI. SafroP. Sanders and C. Schulz, Recent advances in graph partitioning, Algorithm Engineering, Lecture Notes in Comput. Sci., Springer, Cham, 9220 (2016), 117-158.   Google Scholar

[9]

R. Cerf, The Wulff Crystal in Ising and Percolation Models, Lecture Notes in Mathematics, 1878. Springer-Verlag, Berlin, 2006.  Google Scholar

[10]

D. De Ford, H. Lavenant, Z. Schutzman and J. Solomon, Total variation isoperimetric profiles, arXiv: 1809.07943. Google Scholar

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

[12]

M. Duchin and B. Tenner, Discrete geometry for electoral geography, arXiv: 1808.05860. Google Scholar

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

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

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

[16]

G. Herschlag, R. Ravier and J. Mattingly, Evaluating partisan gerrymandering in Wisconsin, 2017, arXiv: 1709.01596. Google Scholar

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

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

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

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

[21]

J. Mattingly and C. V. Graves, Redistricting and the will of the people, arXiv: 1410.8796v1. Google Scholar

[22]

A. Pratelli and G. Saracco, The ε - εβ property in the isoperimetric problem with double density, and the regularity of isoperimetric sets, arXiv: 1910.06307. Google Scholar

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

[24]

F. RiccaA. 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.  Google Scholar

[25]

G. Saracco, Weighted Cheeger sets are domains of isoperimetry, Manuscripta Math., 156 (2018), 371-381.  doi: 10.1007/s00229-017-0974-z.  Google Scholar

[26]

J. Steiner, Einfacher Beweis der isoperimetrischen Hauptsätze, J. Reine Angew. Math., 18 (1838), 281-296.  doi: 10.1515/crll.1838.18.281.  Google Scholar

[27]

R. J. Wilson, Introduction to Graph Theory, Fourth edition, Longman Group Ltd., Longman, Harlow, 1996.  Google Scholar

show all references

References:
[1]

N. ApollonioR. I. BeckerI. LariF. 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.  Google Scholar

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

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

[5]

R. Barnes and J. Solomon, Gerrymandering and compactness: Implementation flexibility and abuse, arXiv: 1803.02857v1. Google Scholar

[6]

J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.  Google Scholar

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

[8]

A. BuluçH. MeyerhenkeI. SafroP. Sanders and C. Schulz, Recent advances in graph partitioning, Algorithm Engineering, Lecture Notes in Comput. Sci., Springer, Cham, 9220 (2016), 117-158.   Google Scholar

[9]

R. Cerf, The Wulff Crystal in Ising and Percolation Models, Lecture Notes in Mathematics, 1878. Springer-Verlag, Berlin, 2006.  Google Scholar

[10]

D. De Ford, H. Lavenant, Z. Schutzman and J. Solomon, Total variation isoperimetric profiles, arXiv: 1809.07943. Google Scholar

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

[12]

M. Duchin and B. Tenner, Discrete geometry for electoral geography, arXiv: 1808.05860. Google Scholar

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

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

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

[16]

G. Herschlag, R. Ravier and J. Mattingly, Evaluating partisan gerrymandering in Wisconsin, 2017, arXiv: 1709.01596. Google Scholar

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

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

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

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

[21]

J. Mattingly and C. V. Graves, Redistricting and the will of the people, arXiv: 1410.8796v1. Google Scholar

[22]

A. Pratelli and G. Saracco, The ε - εβ property in the isoperimetric problem with double density, and the regularity of isoperimetric sets, arXiv: 1910.06307. Google Scholar

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

[24]

F. RiccaA. 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.  Google Scholar

[25]

G. Saracco, Weighted Cheeger sets are domains of isoperimetry, Manuscripta Math., 156 (2018), 371-381.  doi: 10.1007/s00229-017-0974-z.  Google Scholar

[26]

J. Steiner, Einfacher Beweis der isoperimetrischen Hauptsätze, J. Reine Angew. Math., 18 (1838), 281-296.  doi: 10.1515/crll.1838.18.281.  Google Scholar

[27]

R. J. Wilson, Introduction to Graph Theory, Fourth edition, Longman Group Ltd., Longman, Harlow, 1996.  Google Scholar

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]

Annalisa Cesaroni, Matteo Novaga. The isoperimetric problem for nonlocal perimeters. Discrete & Continuous Dynamical Systems - S, 2018, 11 (3) : 425-440. doi: 10.3934/dcdss.2018023

[2]

Yong Lin, Gábor Lippner, Dan Mangoubi, Shing-Tung Yau. Nodal geometry of graphs on surfaces. Discrete & Continuous Dynamical Systems - A, 2010, 28 (3) : 1291-1298. doi: 10.3934/dcds.2010.28.1291

[3]

Len G. Margolin, Roy S. Baty. Conservation laws in discrete geometry. Journal of Geometric Mechanics, 2019, 11 (2) : 187-203. doi: 10.3934/jgm.2019010

[4]

Tatiana Odzijewicz. Generalized fractional isoperimetric problem of several variables. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2617-2629. doi: 10.3934/dcdsb.2014.19.2617

[5]

Ihsan Topaloglu. On a nonlocal isoperimetric problem on the two-sphere. Communications on Pure & Applied Analysis, 2013, 12 (1) : 597-620. doi: 10.3934/cpaa.2013.12.597

[6]

Stan Alama, Lia Bronsard, Rustum Choksi, Ihsan Topaloglu. Droplet phase in a nonlocal isoperimetric problem under confinement. Communications on Pure & Applied Analysis, 2020, 19 (1) : 175-202. doi: 10.3934/cpaa.2020010

[7]

Gyula Csató. On the isoperimetric problem with perimeter density $r^p$. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2729-2749. doi: 10.3934/cpaa.2018129

[8]

Joachim von Below, José A. Lubary. Isospectral infinite graphs and networks and infinite eigenvalue multiplicities. Networks & Heterogeneous Media, 2009, 4 (3) : 453-468. doi: 10.3934/nhm.2009.4.453

[9]

Fabio Camilli, Adriano Festa, Silvia Tozza. A discrete Hughes model for pedestrian flow on graphs. Networks & Heterogeneous Media, 2017, 12 (1) : 93-112. doi: 10.3934/nhm.2017004

[10]

Joshua E.S. Socolar. Discrete models of force chain networks. Discrete & Continuous Dynamical Systems - B, 2003, 3 (4) : 601-618. doi: 10.3934/dcdsb.2003.3.601

[11]

Regino Criado, Julio Flores, Alejandro J. García del Amo, Miguel Romance. Structural properties of the line-graphs associated to directed networks. Networks & Heterogeneous Media, 2012, 7 (3) : 373-384. doi: 10.3934/nhm.2012.7.373

[12]

Christina Knox, Amir Moradifam. Electrical networks with prescribed current and applications to random walks on graphs. Inverse Problems & Imaging, 2019, 13 (2) : 353-375. doi: 10.3934/ipi.2019018

[13]

Seunghee Lee, Ganguk Hwang. A new analytical model for optimized cognitive radio networks based on stochastic geometry. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1883-1899. doi: 10.3934/jimo.2017023

[14]

Jorge A. Becerril, Javier F. Rosenblueth. Necessity for isoperimetric inequality constraints. Discrete & Continuous Dynamical Systems - A, 2017, 37 (3) : 1129-1158. doi: 10.3934/dcds.2017047

[15]

Annalisa Iuorio, Christian Kuehn, Peter Szmolyan. Geometry and numerical continuation of multiscale orbits in a nonconvex variational problem. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1-22. doi: 10.3934/dcdss.2020073

[16]

Sungwoo Ahn, Winfried Just. Digraphs vs. dynamics in discrete models of neuronal networks. Discrete & Continuous Dynamical Systems - B, 2012, 17 (5) : 1365-1381. doi: 10.3934/dcdsb.2012.17.1365

[17]

Gerhard Knieper, Norbert Peyerimhoff. Ergodic properties of isoperimetric domains in spheres. Journal of Modern Dynamics, 2008, 2 (2) : 339-358. doi: 10.3934/jmd.2008.2.339

[18]

Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A model problem for Mean Field Games on networks. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4173-4192. doi: 10.3934/dcds.2015.35.4173

[19]

V.N. Malozemov, A.V. Omelchenko. On a discrete optimal control problem with an explicit solution. Journal of Industrial & Management Optimization, 2006, 2 (1) : 55-62. doi: 10.3934/jimo.2006.2.55

[20]

Davide Bellandi. On the initial value problem for a class of discrete velocity models. Mathematical Biosciences & Engineering, 2017, 14 (1) : 31-43. doi: 10.3934/mbe.2017003

2018 Impact Factor: 0.871

Article outline

Figures and Tables

[Back to Top]