The nation of Gridlandia is trying to draw voting districts for its upcoming elections. The rules are that there must be four districts and each district must be made up of four contiguous units. (Basically, each district looks like a tetris piece.) Since Gridlandia is laid out neatly in a four-by-four grid, it's not too hard to write down all of the valid plans. There turn out to be only 117 of them.
We can impose a graph or network structure to organize the collection of all of those 117 districting options. We'll let each valid plan be represented by a node in this network, and we'll connect two nodes with an edge if the plans they represent are related by a simple swap move, exchanging the district assignments of two cells from adjacent districts.
We call this structure the metagraph of districting plans. ("Metagraph" because it is a graph whose nodes represent ways of partitioning another graph.) Since Gridlandia is so symmetric, it might be useful to consider two districting plans to be the same if they are equivalent after a rigid motion like a rotation or a flip. For example,
If we do collapse the metagraph in this way (in mathematical terms, if we quotient by the action of the dihedral group D4) we are left with only 22 nodes, and we will call that smaller object a reduced metagraph.
All the ways to district Gridlandia
Below, you can interact with these mathematical objects— if your screen is big enough, they are side-by-side. On the left you can manipulate the full metagraph of Gridlandia. On the right you see the reduced metagraph where plans which are related by symmetry are merged into the same node, and two nodes are linked by an edge if any two of their representatives are adjacent in the full metagraph. Mouse over a node in the left-hand graph to see the corresponding plan and highlight all of the other nodes corresponding to symmetrically equivalent plans. Click a node to highlight all of its neighbors. Clicking a node in the right-hand graph will highlight all nodes in that symmetry class from the larger graph, plus their neighbors.
Nodes in the full metagraph are sized according to their degree, or number of neighbors. Nodes in the reduced metagraph are sized according to the number of representatives in that symmetry class.
Elections in Gridlandia
Now let's think about voting 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 grid unit votes the same way—either for the Purple candidate or the Orange candidate. Within each district, the party with the most votes wins the election, and ties are left ambiguous—nobody wins. Below, you can click each grid unit to toggle its vote between the parties. 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 gray if it has the same number of Purple- and Orange-favoring districts.
Let's make things a little more complicated. Instead of each unit voting entirely for one party, we will give it a balance of Purple and some Orange supporters, in 10% increments. The same electoral rules apply. Left- or right-click on each unit to adjust the balance of Orange and Purple supporters.
Play around with this!
- What happens when the Orange party has a slight majority in most of the cells but a few are heavily Purple?
- Can you find a distribution of voters where one party has less than half of the votes but still wins three out of four districts?
- Can you find a distribution of voters that creates a Purple-colored metagraph node surrounded entirely by Orange nodes?
If we're interested in studying redistricting in the real world, we'll need techniques that work on much, much more complicated graphs. We will develop some of these techniques using the 5x5 grid, which has a much larger universe of valid districting plans.