Projects

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.