  In the United States, regions are frequently divided into districts for the
purpose of electing representatives. How the districts are drawn can affect
who's elected, and drawing districts to give an advantage to a certain group is
known as gerrymandering. It can be surprisingly difficult to detect
gerrymandering, but one algorithmic method is to compare a current districting
plan to a large number of randomly sampled plans to see whether it is an
outlier. Recombination Markov chains are often used for this random sampling:
randomly choose two districts, consider their union, and split this union in a
new way. This works well in practice, but the theory behind it remains
underdeveloped. For example, it's not known if recombination Markov chains are
irreducible, that is, if recombination moves suffice to move from any
districting plan to any other.
  Irreducibility of recombination Markov chains can be formulated as a graph
problem: for a graph $G$, is the space of all partitions of $G$ into $k$
connected subgraphs ($k$ districts) connected by recombination moves? We
consider three simply connected districts and district sizes $k_1\pm 1$
vertices, $k_2\pm 1$ vertices, and $k3\pm 1$ vertices. We prove for arbitrarily
large triangular regions in the triangular lattice, recombination Markov chains
are irreducible. This is the first proof of irreducibility under tight district
size constraints for recombination Markov chains beyond small or trivial
examples.
