ИСТИНА

В докладе рассматривается задача экстремальной комбинаторики, связанная со спра- ведливыми раскрасками гиперграфов. Напомним, что раскраска множества вершин ги- перграфа H = (V, E) называется правильной для гиперграфа H, если в этой раскраске все ребра H не являются одноцветными. Раскраска в r цветов называется справедли- вой, если она является правильной и все цветовые классы имеют почти одинаковую мощности, отличающиеся максимум на единицу. Для гиперграфа H = (V, E) введем величину f(H) по правилу f(H) = P e∈E 2 1−|e| , т.е. f(H) — это математическое ожидание числа одноцветных ребер гиперграфа в слу- чайной раскраске в два цвета. В 1973 году П. Эрдешем и Л. Ловасом был поставлен вопрос о поиске максимальной границы значения величины f(H) для гиперграфов с минимальной мощностью ребра n, которая гарантирует существование правильной рас- краски в два цвета. В статье [1] Й. Бек показал, что соотношение f(H) 6 log∗ (n) − 100 7 , гарантирует 2-раскрашиваемость гиперграфа H, имеющего минимальную мощность ребра n. Здесь через log∗ (n) обозначена функция, обратная башне из n двоек. Недавно Д.А. Шабановым была получен аналог результата Бека для случая про- стых гиперграфов, т.е. гиперграфов, различные ребра которых имеют не более одной общей вершины. Он показал, что условие f(H) = O( √ n) обеспечивает существование правильной раскраски в два цвета. Мы же усиливаем этот результат, показывая, что при тех же ограничениях можно получить и справедливую раскраску в нужное число цветов. Теорема 1. Пусть H = (V, E) — простой гиперграф с минимальной мощностью ребра n = min e∈E |e| и |V | делится на r. Тогда если fr(H) = X e∈E r 1−|e| 6 c √ n, где c > 0 — некоторая абсолютная константа, то для H существует справедливая раскраска в r цветов.