Half-cube vertex-boundary extrema

ID: half-cube-vertex-boundary-extrema

For , a family of 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.

New to topics? Read the docs here!