Аннотация:
В работе рассматриваются экстремальные задачи о раскрасках частичных систем Штейнера. Получено новое достаточное условие $r$-раскрашиваемости для некоторого класса подобных систем в терминах ограничения на максимальную степень вершины. Кроме того, в качестве следствия получена новая нижняя оценка для пороговой вероятности $r$-раскрашиваемости случайного гиперграфа в биномиальной модели.
Ключевые слова:раскраски гиперграфов, разреженные гиперграфы, метод случайной перекраски, частичные системы Штейнера, случайный гиперграф.
Полный текст:
PDF файл (344 kB)