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\).

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 |