  The space of connected graph partitions underlies statistical models used as
evidence in court cases and reform efforts that analyze political districting
plans. In response to the demands of redistricting applications, researchers
have developed sampling methods that traverse this space, building on
techniques developed for statistical physics. In this paper, we study
connections between redistricting and statistical physics, and in particular
with self-avoiding walks. We exploit knowledge of phase transitions and
asymptotic behavior in self avoiding walks to analyze two questions of crucial
importance for Markov Chain Monte Carlo analysis of districting plans. First,
we examine mixing times of a popular Glauber dynamics based Markov chain and
show how the self-avoiding walk phase transitions interact with mixing time. We
examine factors new to the redistricting context that complicate the picture,
notably the population balance requirements, connectivity requirements, and the
irregular graphs used. Second, we analyze the robustness of the qualitative
properties of typical districting plans with respect to score functions and a
certain lattice-like graph, called the state-dual graph, that is used as a
discretization of geographic regions in most districting analysis. This helps
us better understand the complex relationship between typical properties of
districting plans and the score functions designed by political districting
analysts. We conclude with directions for research at the interface of
statistical physics, Markov chains, and political districting.
