МАТЕМАТИКА
О концентрации значений $j$-хроматических чисел случайных гиперграфов
И. О. Денисовa,
Д. А. Шабановbc a Московский государственный университет имени М. В. Ломоносова, Москва, Россия
b Национальный исследовательский университет "Высшая школа экономики", Москва, Россия
c Московский физико-технический институт (национальный исследовательский университет), Долгопрудный, Московская обл., Россия
Аннотация:
Работа посвящена изучению предельного поведения
$j$-хроматических чисел случайного
$k$-однородного гиперграфа в биномиальной модели
$H(n,k,p)$. Рассматривается разреженный случай, когда среднее число ребер является линейной функцией от числа вершин
$n$, т.е. равно
$cn$, где
$c>$ 0 не зависит от
$n$. Доказано, что при всех достаточно больших значениях
$c$ величина
$j$-хроматического числа
$H(n,k,p)$ с вероятностью, стремящейся к
$1$, концентрируется в одном или двух соседних значениях.
Ключевые слова:
случайный гиперграф, раскраски гиперграфов,
$j$-хроматическое число, пороговые вероятности, метод второго момента.
УДК:
519.179.1 Статья представлена к публикации: А. Н. ШиряевПоступило: 15.12.2022
После доработки: 20.12.2022
Принято к публикации: 28.12.2022
DOI:
10.31857/S2686954322600756