Connectivity of Districting Metagraphs
Abstract
In this article, we prove irreducibility results for a family of Markov chains arising in the study of redistricting and detecting gerrymandering. These chains use ReCom moves as their transition mechanism and are commonly employed in Markov chain Monte Carlo methods to generate ensembles of districting plans. Such ensembles are frequently used for outlier analysis, in which a proposed districting map is compared against the ensemble to determine whether it behaves atypically; this methodology often appears in expert testimony in redistricting litigation. We show that when the underlying dual graph is a triangular subset of the triangular lattice with side length 5 or larger, and each district consists of two merged geographic regions, the associated ReCom chain is irreducible. This provides another entry in the very small list of known classes of ReCom chains for which irreducibility has been established. We also demonstrate the fragility of this phenomenon by constructing an infinite family of maps for which the corresponding ReCom chain is not irreducible. Indeed, we produce a districting map that, after implementing a single ReCom move, always yields the same original map. These examples remain structurally close to the triangular lattice: they arise as subdivisions of the triangular lattice, and the resulting graphs have maximum degree at most 8. Finally, we prove irreducibility for a further special case: the ReCom chain on a 3 x n grid graph partitioned into three districts of size n.
Related
- Population fragmentation and the weak Allee effect: critical transitions caused by increased connectivity
- Wavelet analysis in biomedical research: A versatile tool for multiscale signal characterization and functional connectivity analysis
- Asymptotic connectivity, hamiltonicity and toughness
- Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case
- Fiber-Connectivity of Almost-Toric Systems in Four-Dimension
BibTeX
@misc{emre2026connectivity,
title = {{Connectivity of Districting Metagraphs}},
author = {Mehmet Emre and Daniel C. Jerison and Ellen Veomett},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.10152},
eprint = {2606.10152},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.10152},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Connectivity of Districting Metagraphs
AU - Mehmet Emre
AU - Daniel C. Jerison
AU - Ellen Veomett
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2606.10152
UR - https://arxiv.org/abs/2606.10152
AB - In this article, we prove irreducibility results for a family of Markov chains arising in the study of redistricting and detecting gerrymandering. These chains use ReCom moves as their transition mechanism and are commonly employed in Markov chain Monte Carlo methods to generate ensembles of districting plans. Such ensembles are frequently used for outlier analysis, in which a proposed districting map is compared against the ensemble to determine whether it behaves atypically; this methodology often appears in expert testimony in redistricting litigation. We show that when the underlying dual graph is a triangular subset of the triangular lattice with side length 5 or larger, and each district consists of two merged geographic regions, the associated ReCom chain is irreducible. This provides another entry in the very small list of known classes of ReCom chains for which irreducibility has been established. We also demonstrate the fragility of this phenomenon by constructing an infinite family of maps for which the corresponding ReCom chain is not irreducible. Indeed, we produce a districting map that, after implementing a single ReCom move, always yields the same original map. These examples remain structurally close to the triangular lattice: they arise as subdivisions of the triangular lattice, and the resulting graphs have maximum degree at most 8. Finally, we prove irreducibility for a further special case: the ReCom chain on a 3 x n grid graph partitioned into three districts of size n.
ER -