Odd and even hamming spheres also have minimum boundary

Combinatorial problems with a geometric flavor arise if the set of all binary sequences of a fixed length n, is provided with the Hamming distance. The Hamming distance of any two binary sequences is the number of positions in which they differ. The (outer) boundary of a set A of binary sequences is the set of all sequences outside A that are at distance 1 from some sequence in A. Harper 6] proved that among all the sets of a prescribed volume, the ‘sphere’ has minimum boundary.We show that among all the sets in which no pair of sequences have distance 1, the set of all the sequences with an even (odd) number of 1's in a Hamming ‘sphere’ has the same minimizing property. Some related results are obtained. Sets with more general extremal properties of this kind yield good error-correcting codes for multi-terminal channels.