pith. sign in

arxiv: 2606.10152 · v1 · pith:4DYDDPXPnew · submitted 2026-06-08 · 🧮 math.CO · cs.CG· cs.DM

Connectivity of Districting Metagraphs

Mehmet Emre , Daniel C. Jerison , Ellen Veomett This is my paper

Pith reviewed 2026-06-27 15:39 UTC · model grok-4.3

classification 🧮 math.CO cs.CGcs.DM
keywords redistrictingReCom movesMarkov chain irreducibilitytriangular latticedistricting metagraphsgrid graphs
0
0 comments X

The pith

The ReCom Markov chain is irreducible when the dual graph is a triangular subset of the triangular lattice and each district has two regions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves irreducibility for ReCom Markov chains on specific districting maps, meaning any valid plan can reach any other via ReCom moves. This holds precisely when the dual graph forms a triangular subset of the triangular lattice and districts each merge two units. The result enlarges the short list of maps where the chain is known to connect the full space of districtings. The authors also build infinite families of nearby graphs where the chain fails to be irreducible, including maps that return to themselves after one move, and prove irreducibility separately for the 3 by n grid with three districts of size n.

Core claim

When the underlying dual graph is a triangular subset of the triangular lattice and each district consists of two merged geographic regions, the associated ReCom chain is irreducible. The authors construct an infinite family of maps, arising as subdivisions of the triangular lattice with maximum degree at most 8, for which the ReCom chain is not irreducible. They prove irreducibility for the further special case of the ReCom chain on a 3 by n grid graph partitioned into three districts of size n.

What carries the argument

The districting metagraph whose vertices are all valid partitions of the dual graph into the required number of districts and whose edges are the possible ReCom moves that merge two adjacent districts and split the merged region along a new cut.

Load-bearing premise

The dual graph must be a triangular subset of the triangular lattice and every district must consist of exactly two merged units.

What would settle it

A pair of valid districtings on such a triangular lattice graph with no sequence of ReCom moves connecting them would falsify the irreducibility result.

read the original 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 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves irreducibility of the ReCom Markov chain on dual graphs that are triangular subsets of the triangular lattice when every district has size exactly two. It also constructs an infinite family of counterexamples on subdivisions of the triangular lattice (maximum degree at most 8) on which the chain is reducible, including explicit maps fixed by a single ReCom move, and proves a separate irreducibility result for the 3×n grid graph partitioned into three districts of size n each.

Significance. If the proofs are correct, the work enlarges the very small list of rigorously established irreducibility results for ReCom chains, which directly supports the validity of MCMC ensemble methods used in redistricting litigation. The positive results are scoped to precise combinatorial settings, while the counterexamples usefully delineate the fragility of irreducibility under modest structural perturbations of the same lattice family.

minor comments (2)
  1. [Abstract] The abstract and introduction would benefit from a single sentence clarifying that the positive irreducibility theorems apply only to the stated lattice subsets and fixed district size two (or the 3×n case), to avoid any risk of over-generalization by readers.
  2. Notation for the dual graph and the precise definition of a ReCom move could be collected in a short preliminary section or table for easier reference when reading the proofs.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The report accurately captures the scope of our irreducibility results and the counterexamples, and we appreciate the recognition that these enlarge the limited collection of rigorously proven cases for ReCom chains.

Circularity Check

0 steps flagged

No circularity; direct combinatorial proofs on scoped graph families

full rationale

The manuscript establishes irreducibility via explicit case analysis on triangular-lattice dual graphs with fixed district size 2, supplies an infinite family of counterexamples on nearby subdivisions (max degree ≤8), and proves a separate positive result for the 3×n grid. All arguments are self-contained combinatorial constructions with no fitted parameters, no load-bearing self-citations, and no reduction of a claimed prediction to its own inputs by definition. The scope is narrow and the counterexamples demonstrate the result is not claimed to hold more generally.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the combinatorial properties of triangular-lattice dual graphs and the restriction to districts of size exactly two; these are domain assumptions rather than free parameters or invented entities.

axioms (2)
  • domain assumption The dual graph is a triangular subset of the triangular lattice.
    Invoked as the setting in which the positive irreducibility result holds.
  • domain assumption Each district consists of exactly two merged geographic regions.
    Fixed district size used throughout the positive results.

pith-pipeline@v0.9.1-grok · 5783 in / 1380 out tokens · 14097 ms · 2026-06-27T15:39:35.639361+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 2 canonical work pages

  1. [1]

    https://mggg.org/

    Metric Geometry Gerrymandering Group: MGGG Webpage. https://mggg.org/

  2. [2]

    https://sites.duke.edu/quantifyinggerrymandering/

    Quantifying Gerrymandering Group: Quantifying Gerrymandering Webpage. https://sites.duke.edu/quantifyinggerrymandering/

  3. [3]

    https://gerrymander.princeton

    Wang, S., Podowitz-Thomas, A., Wheelen, H., Rhode, J., Cervas, J., Clark, J., Brewer, H., Ober, R., Sippy, Z., Chen, S., Kmetz, A., Goldbloom-Helzner, A., Purohit, I.: Princeton Gerrymandering Project. https://gerrymander.princeton. edu/redistricting-report-card

  4. [4]

    33 colorado

    Clelland, J., Colgate, H., DeFord, D., Malmskog, B., Sancier-Barbosa, F.: Col- orado in context: Congressional redistricting and competing fairness criteria in 3See Step 3 in the proof of Theorem 2 for details. 33 colorado. Journal of Computational Social Science (2021)

    2021

  5. [5]

    Statistics and Public Policy (2020)

    Herschlag, G., Kang, H.S., Luo, L., Graves, C.V., Bangia, S., Ravier, R., Mat- tingly, J.C.: Quantifying gerrymandering in north carolina. Statistics and Public Policy (2020)

    2020

  6. [6]

    Journal of Computational Social Science (2026)

    McWhorter, A., DeFord, D.: Free elections in the free state: ensemble analysis of redistricting in new hampshire. Journal of Computational Social Science (2026)

    2026

  7. [7]

    Harvard Data Science Review (2021)

    DeFord, D., Duchin, M., Solomon, J.: Recombination: A family of markov chains for redistricting. Harvard Data Science Review (2021)

    2021

  8. [8]

    org/metagraph/ (2025)

    Metric Geometry Gerrymandering Group: Welcome to Gridlandia! https://mggg. org/metagraph/ (2025)

    2025

  9. [9]

    https://arxiv.org/abs/2307.15996 (2023)

    Tucker-Foltz, J.: Locked Polyomino Tilings. https://arxiv.org/abs/2307.15996 (2023)

    arXiv 2023

  10. [10]

    Discrete Applied Mathematics347(2024)

    Cannon, S.: Irreducibility of recombination markov chains in the triangular lattice. Discrete Applied Mathematics347(2024)

    2024

  11. [11]

    SciPost Physics Core6(3), 054 (2023)

    Røising, H.S., Zhang, Z.: Ergodic archimedean dimers. SciPost Physics Core6(3), 054 (2023)

    2023

  12. [12]

    Discrete mathematics310(13-14), 1918–1931 (2010)

    Nakano, F., Ono, H., Sadahiro, T.: Local move connectedness of domino tilings with diagonal impurities. Discrete mathematics310(13-14), 1918–1931 (2010)

    1918

  13. [13]

    The American Mathematical Monthly 97(8), 757–773 (1990) https://doi.org/10.1080/00029890.1990.11995660

    Thurston, W.P.: Conway’s tiling groups. The American Mathematical Monthly 97(8), 757–773 (1990) https://doi.org/10.1080/00029890.1990.11995660

    work page doi:10.1080/00029890.1990.11995660 1990

  14. [14]

    Discrete Mathematics152(1), 191–210 (1996) https://doi.org/10.1016/0012-365X(94) 00304-2

    Kenyon, C., R´ emila, E.: Perfect matchings in the triangular lattice. Discrete Mathematics152(1), 191–210 (1996) https://doi.org/10.1016/0012-365X(94) 00304-2

    work page doi:10.1016/0012-365x(94 1996

  15. [15]

    Physical Review Letters86(9), 1881 (2001)

    Moessner, R., Sondhi, S.L.: Resonating valence bond phase in the triangular lattice quantum dimer model. Physical Review Letters86(9), 1881 (2001)

    2001

  16. [16]

    https://www.ncsl.org/redistricting-and-census/ nested-and-multi-member-state-legislative-districts (2025) 34

    State Legislatures, N.C.: Nested and Multi-Member State Leg- islative Districts. https://www.ncsl.org/redistricting-and-census/ nested-and-multi-member-state-legislative-districts (2025) 34

    2025

  17. [17]

    Graph theory and theoretical physics, 43–110 (1967)

    Kasteleyn, P.: Graph theory and crystal physics. Graph theory and theoretical physics, 43–110 (1967)

    1967

  18. [18]

    https://arxiv.org/abs/ math/0310326

    Kenyon, R.: An introduction to the dimer model (2003). https://arxiv.org/abs/ math/0310326

    Pith/arXiv arXiv 2003

  19. [19]

    invariants

    Chen, A., Stephens, S., Udell, G., Webb, J.: Exploring Metagraphs and Dual Graphs Via Tilings and Curvature. Unpublished (2024) Appendix A Invariants Chen et al explored the application of invariants in the context of the metagraph of redistricting maps [19]. They explored these invariants specifically for the 6×6 grid graph, which was already known to ha...

    2024

  20. [20]

    The total number of tiles

  21. [21]

    The number ofatiles with even second coordinate minus the number ofatiles with odd second coordinate

  22. [22]

    The number ofbtiles whose coordinate sums are even minus the number ofbtiles whose coordinate sums are odd

  23. [23]

    This results in a nullspace of dimension 5, with basis vectors of invariants described as follows:

    The number ofctiles with even first coordinate minus the number ofctiles with odd first coordinate We can also consider ReCom combinations over the fieldZ 2 in order to find IZ2(TZ2). This results in a nullspace of dimension 5, with basis vectors of invariants described as follows:

  24. [24]

    The parity of all tiles of typea

  25. [25]

    The parity of all tiles of typeb

  26. [26]

    The parity of all tiles of typec

  27. [27]

    The parity of the number of tiles of typeawith odd first coordinate plus the number of tiles of typebwith odd first coordinate

  28. [28]

    The parity of the number of tiles of typeawith sum of coordinates odd, plus the parity of the number of tiles of typebwith sum of coordinates even, plus the parity of the number of tiles of typecwith odd first coordinate We conclude with a bit of speculation. Our overall goal is to answer the question: Given two tilings, is it possible to get from one to ...