О двух предельных значениях хроматического числа случайного гиперграфа

Теория вероятностей и ее применения. 2022. Т. 67. № 2. С. 223–246.

Демидович Ю. А., Шабанов Д. А.

Работа посвящена изучению предельной концентрации значений хроматического числа случайного гиперграфа в биномиальной модели H(n,k,p). Доказано, что при фиксированном k>2 и не слишком быстро растущем значении n^{k-1}p хроматическое число H(n,k,p) с вероятностью, стремящейся к 1, принадлежит множеству из некоторых двух соседних значений. Кроме того, показано, что при чуть более сильных ограничениях на рост n^{k-1}p данные значения можно отыскать явным образом, как функции от n и p.

Ключевые слова: Chromatic number, случайные гиперграфы, second moment method, random hypergraphs, метод второго момента, хроматическое число