Эта публикация цитируется в
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