Welcome to Gridlandia!
Gridlandia is trying to draw legislative districts for its upcoming elections. The rules are that there must be four districts, they must be contiguous, and they must all be of the same size. Since Gridlandia is laid out neatly in a four-by-four grid, it’s not too hard to write all of the allowed districting plans down. There are only 117 of them.
We can impose a graph structure on the collection of all of these plans, where each node is a plan and two plans are connected if one can be transformed into the other by swapping a pair of cells in adjacent districts.
We can transfom the plan on the left into the plan on the right by swapping these two cells.
We call this structure the metagraph of districting plans. Below, you can interact with this mathematical object. The graph on the left is the complete metagraph. Since Gridlandia is so symmetric, it might be useful to consider two districting plans to be the same if one can be transformed into the other by rotating or flipping the plan. For example,
We can transfom the plan on the left into the plan on the right by rotating 90 degrees.
The graph on the right is the metagraph where plans which are symmetric are merged into the same node, and two nodes are linked if any two of their two constituent nodes are linked in the full metagraph. Mouse over a node in the graph on the left to see the corresponding plan and highlight all of the other nodes corresponding to symmetric plans. Click a node to highlight all of its neighbors. Clicking a node in the graph on the right will highlight all nodes in that symmetry class in the graph on the left as well as all of the neighbors of all of those plans.
Now let’s think about elections in Gridlandia. Gridlandia has plurality elections and two political parties, the Purple Party and the Orange Party. For simplicity, we’ll start by assuming that everyone in the same cell votes the same way – either for the Purple candidate or the Orange candidate. Within each district, the candidate which gets the most votes wins the election, and ties are not resolved. Below, click a cell once to change its color. On the left, the nodes in the metagraph will change color to indicate which party wins a legislative majority under the corresponding plan. A node will remain grey if the number of Purple- and Orange-favoring districts is equal.
Let’s make things a little more realistic. Instead of each cell voting entirely for one party, there are some Purple and some Orange supporters in each cell – a total of ten in each square. The same electoral rules apply, but now we can think about a distribution of votes in each cell. Left click on a square to increase the percentage of Orange voters, or right click it to decrease the percentage of Orange voters.
What happens when the Orange party has a slight majority in most of the cells but a few are 90 or 100 percent Purple? Under which configurations can the minority party still win three out of four districts? Are there any distributions of voters that cause there to be a Purple colored metagraph node surrounded entirely by Orange colored nodes?
If we’re interested in studying redistricting in the real-world, we’ll need techniques which work on cases which are more complex than a 4x4 grid. We will develop some of these techniques using the 5x5 grid, which has a much larger set of valid districting plans.