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

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