Small-set edge isoperimetry in a square grid
= Small-set edge isoperimetry in a square grid
{title2=$f_n(a)=2b-1$}
For the $n\times n$ <grid graph>, if $b$ is an integer, $b<n/2$, and $(b-1)^2<a\leq b(b-1)$, the minimum <edge boundary> of an $a$-vertex set is $2b-1$. A corner $(b-1)\times(b-1)$ square with a nonempty partial adjacent column attains it. The lower bound counts occupied rows and columns; full rows or columns are treated separately because they contribute no boundary in their own direction.