Redistricting in Triangular and Square Grids

We study the configuration space of connected graph partitions over sections of the triangular and square grids. In application domains, the partition of a geographical region into smaller regions is modeled by a graph \(M = (V,E)\), called a map. A \(k\)-district map is a map \(M\) together with a partition \(V = V_{1} \cup \cdots \cup V_{k}\) into nonempty subsets, called districts, such that each district \(V_i\) induces a connected subgraph \(M[V_i]\). We are interested in the configuration space, where the nodes are the \(k\)-district maps on \(M\), and two nodes are adjacent if they are connected by a so-called recombination move, where two districts \(V_i, V_j\) are replaced by two new districts \(V_i', V_j'\) such that \(V_i \cup V_j = V_i' \cup V_j'\). Navigating the configuration space, even for small and highly structured graphs, is computationally infeasible. Practitioners use Markov chains to analyze the quality of district maps. The critical question for the theoretical underpinning of this approach is whether the configuration space is connected.