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

Матем. заметки, 1997, том 61, выпуск 6, страницы 873–883 (Mi mzm1571)

Оценки числа независимости гиперграфа и гипотеза Райзера

В. Е. Тараканов

Математический институт им. В. А. Стеклова РАН

Аннотация: Пусть $H$ – гиперграф с $n$ вершинами, $m$ ребрами, числом вершин в ребре не больше $r\ge2$ и степенью вершины $\delta\ge2$; $\tau(H)$ – его трансверсальное число, $\mu(H)$ – число независимости (максимальное число попарно не пересекающихся ребер с $r$ вершинами в ребре). Известная оценка $\mu\ge(\delta n-(r-1)m)/(\delta r-r+1)$ усиливается в случае, когда $H$ – псевдограф с максимальной степенью вершины $\Delta$ при $2\delta-2\ge\Delta$ (аналог соответствующего результата для графов), и применяется для доказательства известной гипотезы Райзера для $r$-дольных $r$-равномерных гиперграфов $H$: $\tau(H)\le(r-1)\mu(H)$, а именно, устанавливается справедливость этого неравенства в случае, когда $H$ $\delta$-регулярен, $2\le\delta\le r-1$.
Библиография: 6 названий.

УДК: 519.17

Поступило: 19.09.1996

DOI: 10.4213/mzm1571


 Англоязычная версия: Mathematical Notes, 1997, 61:6, 731–738

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


© МИАН, 2024