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

B. E. Torosyan


Abstract: 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.

UDC: 519.1

Received: 21.03.1990

Bibliographic databases:

• 
•