ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2009, ТОМ 15, ВЫПУСК 7, СТР. 141-163

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

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

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

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

Полнотекстовая версия статьи в формате PDF (202 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k09/k097/k09707h.htm
Изменения вносились 19 апреля 2010 г.