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

Докл. РАН. Матем., информ., проц. упр., 2022, том 502, страницы 37–41 (Mi danma235)

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

МАТЕМАТИКА

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

Т. Г. Матвееваa, А. Э. Хузиеваb, Д. А. Шабановabc

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

Аннотация: Работа посвящена изучению пороговой вероятности для свойства наличия сильной раскраски в заданное число цветов у случайного $k$-однородного гиперграфа в биномиальной модели $H(n,k,p)$. Раскраска множества вершин гиперграфа называется сильной, если в ней в каждом ребре не найдется двух вершин одинакового цвета. Исследуется вопрос о нахождении точной пороговой вероятности наличия сильной раскраски в $q$ цветов у $H(n,k,p)$. В работе с помощью метода второго момента получены весьма точные оценки этой величины при условии, что $q$ велико по отношению к $k$.

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

УДК: 519.174, 519.179.1, 519.179.4

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

DOI: 10.31857/S268695432201009X


 Англоязычная версия: Doklady Mathematics, 2022, 105:1, 31–34

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


© МИАН, 2024