Odd and even Hamming spheres also have minimum boundary
type: Item
instance of: scholarly article
title: Odd and even Hamming spheres also have minimum boundary
zbMATH Open document ID: 0547.05004
DOI: 10.1016/0012-365X(84)90068-2
author: Victor K. Wei
author: János Körner
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 94B25
zbMATH DE Number: 3871366
zbMATH Keywords: Hamming space
zbMATH Keywords: Hamming sphere
zbMATH Keywords: Kruskal-Katona theorem
zbMATH Keywords: isoperimetric problem
MaRDI profile type: Publication
cites work: Correction to bounds on conditional probabilities with applications
cites work: Q3858140
cites work: Q3686615
cites work: Über einen Satz von Kruskal
cites work: A short proof for a theorem of Harper about Hamming-spheres
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: Q4071752
cites work: Q4140999
cites work: Q5726070
cites work: Q4083487
cites work: Q4146667
cites work: New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
description: scientific article; zbMATH DE number 3871366