Odd and even Hamming spheres also have minimum boundary (Q798656): Difference between revisions

The Hamming space \(X^ n\) is the set of all \(0,1\) sequences of length \(n\) with the distance ``number of different digits''. For two subsets \(A,B\subseteq X^ n\) define \(d(A,B)\) as the smallest distance \(d(x,y)\) between any pair of sequences \(x\in A\), \(y\in B\). The hole-diameter \(d(A)\) of \(A\) is the minimum distance among different elements of \(A\). For every positive integer \(k\), \(\Gamma^ k(A)\) is the set \(\{x\in X^ n\mid d(\{x\},A)\leq k\}\). The set \(\Gamma^ k\{x\}\) is called a Hamming sphere with radius \(k\) and center \(x\). The \(k\)-neighborhood of a set \(A\subseteq X^ n\) is the set \(\Gamma^ k(A)-A\). This paper is concerned with the following problem: Given positive integers \(d', d<n\) and \(m<2^ n\), what is the smallest possible size of the \(d\)-neighborhood of sets \(A\subseteq X^ n\) with hole-diameter \(d'\) and \(| A| =m\). The case of \(d'=1\) and arbitrary \(d\) is settled by the Harper-Kruskal-Katona theorem (see \textit{L. H. Harper} [J. Comb. Theory 1, 385--393 (1966; Zbl 0158.20802)], \textit{J. B. Kruskal} [Math. Optimization Techn. 251--278 (1963; Zbl 0116.35102)] and \textit{G. O. H. Katona} [Stud. Sci. Math. Hung. 10, 131--140 (1977; Zbl 0366.05003)]. In the paper under review, the above problem for an arbitrary \(d\) in the case \(d'\geq 2\) is solved. The authors show that among all the sets with the minimizing property are the sets of all the sequences with an even (odd) number of 1's in a Hamming sphere.