RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2019, том 31, выпуск 2, страницы 84–113 (Mi dm1504)

Эта публикация цитируется в 5 статьях

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

Д. А. Кравцовa, Н. Е. Крохмальa, Д. А. Шабановbac

a МГУ имени М.В. Ломоносова
b МФТИ
c НИУ "Высшая школа экономики"

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

Ключевые слова: случайный гиперграф, полноцветные раскраски, пороговые вероятности, метод второго момента.

УДК: 519.174+519.179.1+519.179.4

Статья поступила: 11.02.2018

DOI: 10.4213/dm1504


 Англоязычная версия: Discrete Mathematics and Applications, 2021, 31:1, 19–41

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


© МИАН, 2025