Extremal Sets Minimizing Dimension-normalized Boundaryin Hamming Graphs

We prove that the set of first m vertices of a Hamming graphin reverse-lexicographic order constitutes an extremal set minimizing the dimension-normalized edge-boundary over all m-vertex subsets of the graph. This generalizes a result of Lindsey and can be used to prove a tight lower bound for the isoperimetric number and the bisection width of arrays.