= Half-cube vertex-boundary extrema
{title2=$\min|\partial A|=\binom n{\lfloor n/2\rfloor},\quad\max|\partial A|=2^{n-1}$}
For $n\geq1$, a family of $2^{n-1}$ vertices in the <Boolean hypercube> has these minimum and maximum external <vertex boundary> sizes. The <Harper theorem> gives the minimum: in odd dimension take the lower half of the levels, and in even dimension add the middle-level sets containing coordinate one to all lower levels. The family of even <Hamming weight> attains the maximum, since every remaining vertex has an adjacent even-weight vertex.
Back to article page
