RUS  ENG
Полная версия
ЖУРНАЛЫ // Фундаментальная и прикладная математика // Архив

Фундамент. и прикл. матем., 2009, том 15, выпуск 7, страницы 141–163 (Mi fpm1275)

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

О половинных раскрасках гиперграфов

А. П. Розовская, М. В. Титова, Д. А. Шабанов

Московский государственный университет им. М. В. Ломоносова

Аннотация: Рассматривается экстремальная задача о раскрасках гиперграфов. Пусть $k$ – натуральное число. Требуется найти величину $m_k(n)$, равную минимальному количеству рёбер $n$-равномерного гиперграфа, не допускающего таких двухцветных раскрасок множества вершин, что в каждом ребре гиперграфа содержится по $k$ вершин каждого цвета. В работе получены точные значения величин $m_2(5)$ и $m_2(4)$, а также верхние оценки для $m_3(7)$ и $m_4(9)$.

Ключевые слова: гиперграф, свойство $B$, половинные раскраски.

УДК: 519.179.1+519.157


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2010, 169:5, 654–670

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


© МИАН, 2024