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

Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика). 2023. Т. 512. № 1. С. 52–57.

Тяпкин Д. Н., Шабанов Д. А.

В работе исследуется структура множества полноцветных раскрасок в три цвета у случайного гиперграфа в равномерной модели $H(n,k,m)$. Хорошо известно, что свойство наличия полноцветной раскраски в заданное число цветов $r$ имеет точную пороговую функцию, такое пороговое значение $\widehat{m}_r=\widehat{m}_r(n)$, что для любого $\varepsilon>0$ при $m\leqslant (1-\varepsilon)\widehat{m}_r$ случайный гиперграф $H(n,k,m)$ с вероятностью, стремящейся к 1 при $n\to\infty$, обладает подобной раскраской, а при $m\geqslant (1+\varepsilon)\widehat{m}_r$ --- наоборот, не обладает подобной раскраской с вероятностью, стремящейся к 1. Мы исследуем алгоритмическую границу для свойства полноцветной раскраски в три цвета и доказываем, что если параметр $m$ принимает значения несколько меньше, чем $\widehat{m}_3$, то множество трехцветных полноцветных раскрасок $H(n,k,m)$ хоть и не пусто с вероятностью, стремящейся к 1, но при этом подчиняется эффекту шаттеринга, впервые описанного в работе Д. Аклиоптаса и А. Койя-Оглана 2008 года.

Ключевые слова: случайные гиперграфы, раскраски гиперграфов, panchromatic colorings, random hypergraphs, Colorings of hypergraphs, полноцветные раскраски, shattering, шаттеринг