Sampling Balanced Forests of Grids in Polynomial Time

Sarah Cannon, Wesley Pegden, Jamie Tucker-Foltz

We prove that a polynomial fraction of the set of $k$-component forests in the $m\times n$ grid graph have equal numbers of vertices in each component, for any constant $k$. This…