RUS  ENG
Полная версия
ЖУРНАЛЫ // Доклады Российской академии наук. Математика, информатика, процессы управления // Архив

Докл. РАН. Матем., информ., проц. упр., 2023, том 509, страницы 28–35 (Mi danma357)

МАТЕМАТИКА

О концентрации значений $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


 Англоязычная версия: Doklady Mathematics, 2023, 107:1, 21–27

Реферативные базы данных:


© МИАН, 2024