Asymptotics of Redistricting the $n\times n$ Grid

Abstract

Redistricting is the act of dividing a region into districts for electoral representation. Motivated by this application, we study two questions. How many ways are there to partition the $n\times n$ grid into $n$ contiguous districts of equal size? How many of these partitions are ``compact"? We give asymptotic bounds on the number of plans: a lower bound of roughly $1.41^{n^2}$ and an upper bound of roughly $3.21^{n^2}$. We then use the lower bound to show that most plans are not compact.

11 pages, 9 figures