|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О двух предельных значениях хроматического числа случайного гиперграфа
Ю. А. Демидовичa, Д. А. Шабановbc a Московский физико-технический институт (национальный исследовательский университет), кафедра дискретной математики и лаборатория продвинутой комбинаторики и сетевых приложений, г. Долгопрудный, Московская область, Россия
b Московский физико-технический институт (национальный исследовательский университет), лаборатория комбинаторных и геометрических структур, г. Долгопрудный, Московская область, Россия
c Московский государственный университет имени М. В. Ломоносова, механико-математический факультет, Москва, Россия
Аннотация:
Работа посвящена изучению предельной концентрации значений хроматического числа случайного гиперграфа $H(n,k,p)$ в биномиальной
модели. Доказано, что при фиксированном $k\ge 3$ и не слишком быстро растущем значении $n^{k-1}p$ хроматическое число гиперграфа $H(n,k,p)$ с вероятностью, стремящейся к $1$, принадлежит множеству из некоторых двух соседних значений. Кроме того, показано, что при чуть более сильных ограничениях на рост $n^{k-1}p$ данные значения можно отыскать явным образом как функции от $n$ и $p$.
Ключевые слова:
случайный гиперграф, хроматическое число, метод второго момента.
Поступила в редакцию: 18.11.2020 Исправленный вариант: 22.10.2021 Принята в печать: 24.10.2021
Образец цитирования:
Ю. А. Демидович, Д. А. Шабанов, “О двух предельных значениях хроматического числа случайного гиперграфа”, Теория вероятн. и ее примен., 67:2 (2022), 223–246; Theory Probab. Appl., 67:2 (2022), 175–193
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tvp5458https://doi.org/10.4213/tvp5458 https://www.mathnet.ru/rus/tvp/v67/i2/p223
|
Статистика просмотров: |
Страница аннотации: | 271 | PDF полного текста: | 39 | Список литературы: | 30 | Первая страница: | 16 |
|