RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 1983, том 34, выпуск 2, страницы 291–295 (Mi mzm5796)

Некоторые простые следствия из Теории кодов для комбинаторных задач упаковок и покрытий

Л. А. Бассалыго, В. А. Зиновьев


Аннотация: Изучается асимптотическое поведение функций $M(n,k,l)$ и $m(n,k,l)$, равных соответственно мощности минимального покрытия и максимальной упаковки всех $l$-подмножеств множества из $n$ элементов его $k$-подмножествами. Показано, что
$$ \varlimsup_{n\to\infty}m(n,k,k-2) \begin{pmatrix} k\\2 \end{pmatrix}\biggl/ \begin{pmatrix} n\\k-2 \end{pmatrix}=1 $$
при $k=o(n)$ и
$$ \varliminf_{n\to\infty}m(n,k,k-2) \begin{pmatrix} k\\2 \end{pmatrix}\biggl/ \begin{pmatrix} n\\k-2 \end{pmatrix}=1 $$
при $k=o(n^{1/3})$, что доказывает справедливость известного предположения Эрдеша и Ханани и для этого случая в несколько более слабой форме. Библ. 9 назв.

УДК: 519.1

Поступило: 20.10.1980


 Англоязычная версия: Mathematical Notes, 1983, 34:2, 629–631

Реферативные базы данных:


© МИАН, 2024