Mathematics of Nested Districts: The Case of Alaska
This paper analyzes a pairing rule that eight states require of their state legislative districting plans—that state Senate districts must be formed by joining adjacent pairs of House districts. From a mathematical perspective, this is a question of constructing perfect matchings on the dual graph of the House districts. We focus mainly on the state of Alaska, where it is possible to generate the full set of matchings and evaluate the expected partisan behavior of the associated Senate plans. To get a sense of the scale of this problem, the table below shows the number of districts and perfect matchings for each of the relevant states.
| State | # House Districts | # Dual Graph Edges | # Perfect Matchings |
|---|---|---|---|
| Alaska | 40 | 100 | 108,765 |
| Illinois | 118 | 326 | 9,380,573,911 |
| Iowa | 100 | 251 | 1,494,354,140,511 |
| Minnesota | 134 | 260 | 6,156,723,718,225,577,984 |
| Montana | 100 | 269 | 11,629,786,967,358 |
| Nevada | 42 | 111 | 313,698 |
| Oregon | 60 | 158 | 229,968,613 |
| Wyoming | 60 | 143 | 920,864 |
You can find all of the code and data used in the report, as well as technical
instructions for reproducing our work, in our
Alaska GitHub repo.