|
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.
Received: 21.03.1990
Citation:
B. E. Torosyan, “The number and cardinalities of components of solutions of a discrete isoperimetric problem in the Hamming space”, Diskr. Mat., 3:4 (1991), 28–46
Linking options:
https://www.mathnet.ru/eng/dm817 https://www.mathnet.ru/eng/dm/v3/i4/p28
|
Statistics & downloads: |
Abstract page: | 287 | Full-text PDF : | 115 | First page: | 1 |
|