• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Полноцветные раскраски случайных гиперграфов

Дискретная математика. 2019. Т. 31. № 2. С. 84-113.
Шабанов Д. А., Крохмаль Н. Е., Кравцов Д. А.

Работа посвящена изучению пороговой вероятности наличия полноцветной раскраски в r цветов у случайного k-однородного гиперграфа в биномиальной модели H(n,k,p), т.е. такой раскраски, что каждое ребро гиперграфа содержит вершины всех r цветов. Показано, что данная пороговая вероятность при фиксированных r<k и растущем n отвечает разреженному случаю, т.е. случаю линейного среднего числа ребер cn для положительного фиксированного c. Найдены ее очень близкие оценки в виде ограничений значения параметра c, где разность между оценками экспоненциально быстро стремится к нулю при заданном r и растущем k.