RUS  ENG
Полная версия
ЖУРНАЛЫ // Доклады Российской академии наук. Математика, информатика, процессы управления // Архив

Докл. РАН. Матем., информ., проц. упр., 2020, том 494, страницы 30–34 (Mi danma112)

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

МАТЕМАТИКА

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

Ю. А. Демидовичa, Д. А. Шабановabc

a Московский физико-технический институт (национальный исследовательский университет), Московская обл., Долгопрудный, Россия
b Московский государственный университет имени М. В. Ломоносова, Москва, Россия
c Национальный исследовательский университет "Высшая школа экономики", Москва, Россия

Аннотация: В работе изучается асимптотическое поведение хроматического числа биномиального случайного гиперграфа $H(n,k,p)$ при фиксированном $k\ge4$, стремящемся к бесконечности $n$ и некоторой функции $p=p(n)$. Доказано, что при не слишком медленном убывании к нулю функции $p=p(n)$ хроматическое число случайного гиперграфа $H(n,k,p)$ с вероятностью, стремящейся к 1, сконцентрировано в двух или трех соседних значениях, которые могут быть явно найдены как функции от $n$, $p$, $k$.

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

УДК: 519.174, 519.179.1, 519.179.4

Статья представлена к публикации: А. Н. Ширяев
Поступило: 26.11.2019
После доработки: 26.11.2019
Принято к публикации: 23.06.2020

DOI: 10.31857/S2686954320050331


 Англоязычная версия: Doklady Mathematics, 2020, 102:2, 380–383

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


© МИАН, 2024