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

Матем. заметки, 1981, том 29, выпуск 1, страницы 83–94 (Mi mzm10050)

Эта публикация цитируется в 2 статьях

Локально-турановское свойство для $k$-графов

Б. С. Стечкинa, П. Франклb

a Математический институт им. В. А. Стеклова АН СССР
b Математический институт АН ВНР, Будапешт

Аннотация: Исследуются $k$-графы $G^k$ на множестве $n$ вершин $S_n$, обладающие свойством
$$ \forall S_p\subset S_n\quad \exists S_q\subset S_p\quad \forall S_k\subset S_q\quad S_k\in G^k. $$
В частности показано, что для таких графов
$$ \min|G^k|=\dbinom{n-p+q}{k},\text{ если } p\leqslant\frac{k}{k-1}(q-1), $$
и
$$ \min|G^k|=(n-p+1)\dbinom{q}{k},\text{ если } n\leqslant\frac{q}{q-1}(p-1) \text{ и } 2k\geqslant q+1. $$
Библ. 11 назв.

УДК: 519.1

Поступило: 15.12.1977


 Англоязычная версия: Mathematical Notes, 1981, 29:1, 45–51

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


© МИАН, 2024