## On the construction of solutions of a discrete isoperimetric problem in Hamming space.(English. Russian original)Zbl 0741.05037

Math. USSR, Sb. 63, No. 1, 81-96 (1989); translation from Mat. Sb., Nov. Ser. 135(177), No. 1, 80-95 (1988).
Denote by $$B^ n$$ the $$n$$-dimensional unit cube, i.e., the collection of all $$n$$-dimensional vectors with each coordinate equal to 0 or 1, and by $$\rho(\tilde\alpha,\tilde\beta)$$ the Hamming distance between vertices in $$B^ n$$. Let $$A\subseteq B^ n$$. Then $$\tilde\alpha\in A$$ is called an interior point of $$A$$ if $$S^ n_ 1(\tilde\alpha)\subseteq A$$, and a boundary point otherwise (where $$S^ n_ r(\tilde\alpha)$$ is the ball about a point $$\tilde\alpha\in B^ n$$ with radius $$r$$ in the metric $$\rho$$). The collection of all interior points of a set $$A$$ is denoted by $$P(A)$$, and the set of boundary points by $$\Gamma(A)$$. A set $$A\subseteq B^ n$$ is said to be optimal if $$|\Gamma(A)|\leq|\Gamma(B)|$$ for any $$B\subseteq B^ n$$ such that $$| B|=| A|$$.
This article is a study of the collection of optimal subsets of the cube $$B^ n$$. It is known that one of the $$m$$-element optimal sets is the standard arrangement $$L^ n_ m$$, defined as the initial segment of length $$m$$ of the following numbering (denoted below by $${\mathfrak L}_ n$$) of the vertices of $$B^ n$$. The vector $$\tilde 0=(0,\dots,0)$$ is given the number 1. Suppose that all the vectors in $$B^ n$$ with coordinate sum (norm) less than $$k$$ have already been numbered, along with some vectors of norm $$k$$. We give the next largest natural number to the lexicographically highest unnumbered vertex in $$B^ n$$ of norm $$k$$.
Let $$S(A)=\{\tilde\alpha\in A: S^ n_ 1(\tilde\alpha)\cap P(A)=\emptyset\}$$ be the collection of free points of $$A$$. A set $$A\subseteq B^ n$$ is said to be critical if $$S(A)=\emptyset$$. The empty set will be regarded as a critical set. Denote by $${\mathfrak N}^ n_ m$$ the collection of all optimal noncritical $$m$$-element subsets of $$B^ n$$. It is shown in $$\S 2$$ that the construction of the sets in this class reduces to the construction of the optimal critical sets.
It is known that if $$L^ n_ m$$ is a critical set, then any $$m$$-element optimal set is also critical. Such numbers $$m$$ are called critical cardinalities. Denote by $${\mathfrak M}^ n_ m$$ the collection of all optimal subsets with the critical cardinality $$m$$. A description of all the sets in the class $${\mathfrak M}^ n_ m$$ is given in [the author, Dokl. Akad. Nauk SSSR 279, 521-524 (1984); English translation in Soviet Math. Dokl. 30, 667-670 (1984; Zbl 0591.05017)]. It is not hard to show that the number of critical cardinalities is equal to $$2^{n-1}$$.
Denote by $${\mathfrak K}^ n_ m$$ the collection of optimal critical $$m$$- element sets with noncritical cardinality. It is not true that $${\mathfrak K}^ n_ m\neq\emptyset$$ for all $$m$$ with $$1\leq m\leq 2^ n$$. One of our main results is Theorem 3.1, proved in $$\S 3$$, in which it is shown that if $$A$$ is an optimal set, then so is $$P(A)$$. On the basis of this theorem and results of L. A. Aslanyan [Probl. Kibern. 36, 85-127 (1979; Zbl 0445.05020)] we obtain a sufficient condition for $${\mathfrak K}^ n_ m=\emptyset$$ in $$\S 4$$. Thus, all the solutions of the isoperimetric problem are found for such cardinalities $$m$$. In the same section it is shown that the number of these cardinalities is asymptotically equal to $$2^{n-3}$$. Moreover, a necessary and sufficient condition for $${\mathfrak K}^ n_ m=\emptyset$$ is found. It is shown in $$\S 5$$ that for any subset of $$B^ n$$ there exists an optimal subset of a cube of higher dimension that in a certain sense is analogous to it in structure. This result reflects well the difficulties arising in the description of $$m$$- element optimal subsets of $$B^ n$$, and at the same time gives a method for constructing certain sets in the class $${\mathfrak K}^ n_ m$$.

### MSC:

 05C35 Extremal problems in graph theory 52A40 Inequalities and extremum problems involving convexity in convex geometry

### Citations:

Zbl 0591.05017; Zbl 0445.05020
Full Text: