The number and cardinalities of components of solutions of a discrete isoperimetric problem in the Hamming space

B. E. Torosyan

Diskretnaya Matematika, Tome 3 (1991) no. 4, pp. 28-46

Résumé

We consider the problem of describing multicomponent subsets of the set $\{0, 1 \}^n$ having a minimal boundary in the Hamming metric. In the framework of this metric and of a natural understanding of components of a set, we establish 1) conditions for the existence of such subsets of a given cardinality with a given number of components; 2) attainable and other upper bounds for the number of components and their cardinalities depending on the cardinality of these subsets. In particular, we show that for $k\geq \sqrt{n-1}-1$ as $n\to \infty $ almost all points of such a subset of cardinality not less than $\sum^k_{i=0} (^n_i)$ are contained in a unique component.