|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Полноцветные раскраски случайных гиперграфов
Д. А. Кравцов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$.
Ключевые слова:
случайный гиперграф, полноцветные раскраски, пороговые вероятности, метод второго момента.
Статья поступила: 11.02.2018
Образец цитирования:
Д. А. Кравцов, Н. Е. Крохмаль, Д. А. Шабанов, “Полноцветные раскраски случайных гиперграфов”, Дискрет. матем., 31:2 (2019), 84–113; Discrete Math. Appl., 31:1 (2021), 19–41
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1504https://doi.org/10.4213/dm1504 https://www.mathnet.ru/rus/dm/v31/i2/p84
|
Статистика просмотров: |
Страница аннотации: | 388 | PDF полного текста: | 38 | Список литературы: | 37 | Первая страница: | 17 |
|