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

Рассматривается обобщение классической задачи Эрдеша–Хайнала в теории гиперграфов на случай предписанных раскрасок. Изучается величина $m_{pr}(n,r)$, равная минимальному числу ребер гиперграфа в классе $n$-равномерных гиперграфов, предписанное хроматическое число которых больше $r$. Получена нижняя оценка данной величины, которая улучшает ранее известные результаты для $r\ge3$. Кроме того, указано достаточное условие существования предписанной $r$-раскрашиваемости $n$-равномерного гиперграфа в терминах ограничений на пересечение ребер. В качестве следствия получена новая нижняя оценка величины $m_{pr}^*(n,r)$, равной минимальному числу ребер гиперграфа в классе $n$-равномерных простых гиперграфов (в которых любые два ребра имеют не более одной общей вершины), предписанное хроматическое число которых больше $r$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант 06–01–00383, и программы Президента Российской Федерации поддержки ведущих научных школ, грант НШ 691.2008.1.