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

Теория вероятн. и ее примен., 2022, том 67, выпуск 2, страницы 223–246 (Mi tvp5458)

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

DOI: 10.4213/tvp5458


 Англоязычная версия: Theory of Probability and its Applications, 2022, 67:2, 175–193

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


© МИАН, 2024