Projects

This post is going to be less mathematical than usual for me – this is essentially how I explain Single Transferable Vote elections to people who have never heard about them before. There are many great explanations of STV already out there; two of my favorite are this series by CGP Grey, and this voter education video out of Portland.

My angle for this post is that I’m going to explain STV the same way as I would to my mother. Rather than just explain the mechanics of the rules, I’ll take my time to motivate everything, and explain why we would want to make elections so complicated in the first place, with plenty of examples along the way.

Ok, I know I sound like a broken record, but I really really want to figure out a way to count the districtings of the 10 x 10 grid graph. And this problem feels within reach!

See here for context and a previous attempt at this.

Genealogy of this Idea.

The idea for this chain was partially inspired by section 14.4 of Levin & Peres [1], which itself attributes the original idea to Jerrum & Sinclair [2]. These publications gave a method to “approximately count” the number of proper \(q\)-colorings of a graph \(G\) of \(n\) vertices with maximal degree \(Δ\). They name \(𝒳\) the set of all proper \(q\)-colorings of \(G\), and they name the vertices of \(G\) as \( \lbrace v_1,…,v_n\rbrace\). Then, fixing a coloring \(x_0 \in 𝒳\), they define

Given a planar graph \(G = (V,E)\) and district sizes \(\lbrace k_i\rbrace_{i=1}^n\), a political districting of \(G = (V,E)\) is a partition \(\lbrace P_i\rbrace_{i=1}^n\) of \(G\) into (simply-)connected subgraphs (called districts) satisfying \(|P_i|=k_i\).

For the purposes of this project, I’ve usually taken \(G\) be an \(n\times n\) grid graph and \(k_i=n\) for all \(i\); but this was a choice made of convenience, not necessity. This project explores a method to stochastically estimate the number of districtings of \(G\) when enumerating them is not computationally viable.