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

1.1. Основные определения

Гиперграфом H в дискретной математике называется пара $H = (V,E)$, где $V = V(H)$ – это множество вершин, а $E = E(H) \subseteq {{2}^{V}}$ – это семейство подмножеств вершин, называемых ребрами. Гиперграф называется k-однородным, если всякое ребро является k-подмножеством вершин. В частности, 2-однородные гиперграфы – это в точности обычные графы без петель и кратных ребер.

В настоящей работе мы изучаем классическую модель случайного гиперграфа $H(n,k,m)$, являющуюся случайным элементом с равномерным распределением на всех k-однородных гиперграфах с n вершинами и m ребрами. Также $H(n,k,m)$ называется равномерной моделью случайного гиперграфа. В рамках статьи мы предполагаем, что $k\; \geqslant \;3$ фиксировано, $n \to + \infty $, а $m = m(n)$ некоторым образом зависит от $n$.

Раскраской гиперграфа H в r цветов называется отображение $\sigma :H \to [r] = \{ 1, \ldots ,r\} $. Раскраска называется правильной, если в ней всякое ребро гиперграфа не является одноцветным. Раскраска называется полноцветной, если в ней всякое ребро содержит вершины всех r цветов.

Для двух гиперграфов $A,\;B$ обозначим через ${\text{Hom}}(A,B)$ множество гомоморфизмов из гиперграфа в $A$ в гиперграф B. Для двух раскра- сок $\tau $ и $\sigma $ гиперграфа H обозначим через ${\text{dist}}(\sigma ,\tau )$  расстояние Хэмминга между ними: ${\text{dist}}(\sigma ,\tau ) = {\text{|}}\{ v \in V(H)\,{\text{|}}\,\sigma (v) \ne \tau (v)\} {\text{|}}$.

Наконец, будем говорить, что последовательность событий ${{\mathcal{E}}_{n}}$ на вероятностном пространстве выполняется асимптотически почти наверное (а.п.н.), если $\mathop {\lim }\limits_{n \to + \infty } \,{\text{P}}[{{\mathcal{E}}_{n}}] = 1$.

1.2. История и постановка задачи

Раскраски графов и гиперграфов имеют широкое применение не только в теоретической информатике как пример вычислительно-сложной задачи, но и в статистической физике [1]. Известно, что задача нахождения хроматического числа графа является NP-трудной [2, 3]. Более того, в случае графов искать сложно даже приближенное решение [4].

Ситуация становится заметно более интересной, когда мы рассматриваем “случайный” граф или гиперграф и допускаем некоторую вероятность ошибки. В самых естественных моделях случайных графов и гиперграфов – равномерной и биномиальной, возникает эффект пороговых функций и вероятностей, когда асимптотика вероятности наличия раскраски быстро меняется от 1 до 0 при увеличении среднего числа ребер. Тем самым мы можем сразу говорить о наличии (с большой вероятностью) искомой раскраски, если среднее число ребер находится ниже порогового значения. Обсудим данный феномен более детально на примере проблемы правильной 2-раскрашиваемости случайного k-однородного гиперграфа $H(n,k,m)$.

Задаче о нахождении точной пороговой функции для свойства 2-раскрашиваемости случайного гиперграфа $H(n,k,m)$ была поставлена Алоном и Спенсером в [5]. Они показали, что пороговому значению отвечает так называемый разреженный случай, когда число ребер $m = cn$ является линейной функцией от числа вершин, т.е. $c > 0$ не зависит от $n$. Сформулируем результаты [5] в виде теоремы.

Теорема 1 (Н. Алон, Дж. Спенсер, [5]). 1) Если

то а.п.н. случайный гиперграф не допускает правильной раскраски в два цвета.

2) Существует такая абсолютная константа $\delta > 0$, что если

то а.п.н. для существует правильная раскраска в два цвета.

В дальнейшем оценки (1), (2) неоднократно улучшались (см. [6–8]). Наилучший из известных результат был получен А. Койя-Огланом и К. Панайоту [9].

Теорема 2 (А. Койя-Оглан, К. Панайоту, [9]). Существует такая функция $\varepsilon (k{{) = 2}^{{ - k(1 + {{o}_{k}}(1))}}}$, что если

то а.п.н. случайный гиперграф не допускает правильной раскраски в два цвета. А еслито а.п.н. для существует правильная раскраска в два цвета.

Оценки (3), (4) показывают, что пороговое значение параметра c весьма хорошо локализовано. Однако даже эти результаты не позволяют решить проблему алгоритмического нахождения раскраски в ситуации, когда число ребер меньше порога правильной 2-раскрашиваемости и мы знаем, что такая раскраска для случайного гиперграфа существует с вероятностью, близкой к 1. На рубеже веков в ряде работ были предложены полиномиальные алгоритмы для поиска правильной раскраски у случайных графов и гиперграфов. Но эти результаты показывали, что предложенный алгоритм работает, только если число ребер заметно меньше порогового значения. Например, в работе Д. Аклиоптаса, Дж. Кима, М. Кривелевича, П. Тетали [6] была доказана следующая теорема.

Теорема 3 (Д. Аклиоптас, Дж. Ким, М. Криве-левич, П. Тетали, [6]). Если

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

Отметим, что оценка (5) по порядку в k раз меньше, чем пороговое значение (см. (3), (4)). Аналогична ситуация и для свойств раскраски случайных графов в заданное $r$ цветов (см. [10–12]): между значениями числа ребер графа, при котором существует раскраска, и при котором ее способен найти алгоритм, существует зазор примерно в 2 раза. Данное наблюдение привело исследователей к простому выводу: около порогового значения сама структура множества правильных раскрасок графа или гиперграфа препятствует построению быстрого алгоритма для поиска хотя бы одного из ее элементов. В математическое утверждение подобное наблюдение было оформлено в прорывной работе Д. Аклиоптаса и А. Койя-Оглана [13]. Авторы [13] доказали, что при значении $c$, достаточно близком к (4), происходит некоторый фазовый переход пространства правильных 2-раскрасок : оно дробится на экспоненциально большое число маленьких областей, и чтобы пройти между ними, нужно перекрасить очень много вершин, при этом во время перекраски по одной вершине мы гарантированно попадем в ситуацию, когда будет неправильно покрашено большое число ребер. Этот эффект был назван шаттерингом, так как в этом случае пространство решений буквально рассыпается на маленькие осколки. Более точное описание шаттеринга мы дадим в следующем параграфе, а пока лишь отметим, что авторы [13] доказали его возникновение при

Тем самым нижняя граница (6) практически совпадает с алгоритмической (5), а верхняя очень близка с пороговой (3)–(4).

Целью настоящей работы было исследование феномена шаттеринга для другого вида раскрасок гиперграфов, который является естественным обобщением правильных 2-раскрасок, а именно – для полноцветных раскрасок в 3 цвета. Полноцветные раскраски гиперграфов были впервые предложены для изучения в классической работе П. Эрдеша и Л. Ловаса [14] и с тех пор активно изучаются. Известно (см. [15]), что задача о поиске полноцветной раскраски ${\text{NP}}$-трудна, поэтому задача нахождения барьеров в случайных гиперграфах для вычисления этих раскрасок на случайных данных также крайне интересна.

Пороговая функция для свойства полноцветной 3-раскрашиваемости случайного гиперграфа хорошо изучена. Имеет место следующая теорема, доказанная Д. Кравцовым, Н. Крохмалем и Д. Шабановым [16].

Теорема 4 (Д. Кравцов, Н. Крохмаль, Д. Шабанов, [16]). Существует такое ${{k}_{0}} \in \mathbb{N}$, что для любого $k > {{k}_{0}}$ выполнено следующее. Если

то а.п.н. для случайного гиперграфа существует полноцветная раскраска в 3 цвета. А еслито а.п.н. случайный гиперграф не допускает полноцветных раскрасок в 3 цвета.

В заключение обзора литературы отметим, что обобщение теоремы 4 на случай полноцветных r-раскрасок, $r\; \geqslant \;4$, было найдено в работе [17], а некоторые результаты о структуре множества правильных раскрасок в r цветов около порогового значения были получены в [18].

3.1. Теорема о переносе

Наша основная задача – исследовать “типичное” поведение множества почти всех полноцветных 3-раскрасок с большой вероятностью, поэтому разумно исследовать “типичные раскраски”. Формально это можно описать при помощи равномерного распределения на множестве полноцветных 3-раскрасок случайного гиперграфа.

Обозначим через Λ_{n, m} = {(H, σ) : : $H\, \in \,{{\mathcal{H}}_{{n,m}}},\sigma \, \in \,\mathcal{S}(H)\} $, где ${{\mathcal{H}}_{{n,m}}}$ – множество всех k‑однородных гиперграфов на $n$ вершинах с $m$ ребрами. Это интересующее нас множество пар. На этом множестве можно рассмотреть распределение ${{\mathcal{U}}_{{n,m}}}$, задающееся следующим образом:

1. выберем $H \in {{\mathcal{H}}_{{n,m}}}$ равновероятно;

2. если $\mathcal{S}(H) \ne \emptyset $, то выберем $\sigma \in \mathcal{S}(H)$ равновероятно.

Но исследовать подобный объект крайне сложно. Вместо этого существует другая, более простая для анализа модель, которая называется planted model и обозначается ${{\mathcal{P}}_{{n,m}}}$, и задается она перестановкой выбора раскраски и гиперграфа:

1. выберем $\sigma \in {{\mathcal{C}}_{3}}(n)$ равновероятно;

2. выберем $H \in {{\mathcal{H}}_{{n,m}}}$ равновероятно среди всех таких гиперграфов, что $\sigma \in \mathcal{S}(H)$.

Но тогда нам нужно уметь переносить результаты, которые мы сможем доказать для ${{\mathcal{P}}_{{n,m}}}$, в модель ${{\mathcal{U}}_{{n,m}}}$. Для этого нами доказана следующая теорема, являющаяся обобщением теоремы из [13] на случай полноцветных раскрасок.

Теорема 6 [о переносе]. Существует такое ${{\varepsilon }_{k}} = {{o}_{k}}(1)$, что если

то существует такая функция $f(n) = o(n)$, что для всякого свойства $\mathcal{E}$ пар $(H,\sigma )$ с условиемвыполнено .

Ключевым фактом, необходимым для доказательства теоремы 6, является следующая лемма.

Лемма 1. Существуют такие функция $g(n)$ = = o(n) и последовательность ${{\varepsilon }_{k}} = {{o}_{k}}(1)$, что при

а.п.н. верно

Доказательство леммы 1, в свою очередь, требует использования результатов о методе второго момента из работы [16], а также обоснования существования точной пороговой функции для свойства существования хотя бы $N$ гомоморфизмов (при $0 < N < o{{(3}^{n}})$) в случайном гиперграфе $H(n,k,m)$.

Для этого мы обобщили результат Х. Хатами и М. Моллоя [19] о точном пороге существования гомоморфизма между гиперграфами до точного порога для свойства существования хотя бы $N$ гомоморфизмов.

Лемма 2. Пусть $R$ – фиксированный $k$-однородный гиперграф с $r$ вершинами, а $N = N(n)$ – некоторая функция с условиями $0 < N < o({{r}^{n}})$. Тогда свойство ${{\mathcal{A}}_{N}} = \{ H:{\text{|Hom}}(H,R){\text{|}}\;\leqslant \;N\} $ имеет точную пороговую функцию в модели $H(n,k,m)$, т.е. существует такая функция $\hat {m} = \hat {m}(n)$, что для любого $\delta > 0$ при $m\;\leqslant \;(1 - \delta )\hat {m}$ выполнено

а при $m\; \geqslant \;(1 + \delta )\hat {m}$ выполнено

Прямым следствием леммы 2 является существование точной пороговой функции для свойства наличия хотя бы $N$ полноцветных 3-раскрасок. Отметим, что лемма 2 имеет самостоятельный интерес.

3.2. Анализ planted model

Согласно определению модели ${{\mathcal{P}}_{{n,m}}}$ она состоит из случайной раскраски $\sigma $ и выбираемой по ней случайного гиперграфа $H$. Рассмотрим их как функции $\sigma = \sigma ({{\mathcal{P}}_{{n,m}}})$, $H = H({{\mathcal{P}}_{{n,m}}})$.

Для любой раскраски $\tau \in {{\mathcal{C}}_{3}}(n)$ введем матрицу ${{A}_{{\sigma ,\tau }}} = ({{a}_{{ij}}}(\sigma ,\tau ):\;i,j = 1,2,3)$, где

– число вершин, покрашенных в цвет $i$ в раскраске $\sigma $ и в цвет $j$ в раскраске $\tau $. Если раскраски были заранее фиксированы, то будем опускать зависимость от них: ${{a}_{{ij}}} = {{a}_{{ij}}}(\sigma ,\tau )$, $A = {{A}_{{\sigma ,\tau }}}$. Рассмотрим далее следующую функцию:

Эта функция будет в некотором смысле играть роль оценки расстояния, однако эта мера будет вырожденной: слагаемые могут быть отрицательными, но по-прежнему мы можем сформулировать важные технические утверждения, которые по сути будут переформулировкой условий шаттеринга в терминах функции $q$. Для этого рассмотрим следующую случайную величину:

Выполнена следующая лемма.

Лемма 3. Пусть $c > {{c}_{{{\text{shat}}}}} = (3{\text{/}}{{2)}^{k}}\ln (2k){\text{/}}(3k)$ и $c\;\leqslant \;(1 - {{\varepsilon }_{k}})(3{\text{/}}{{2)}^{k}}$ для ${{\varepsilon }_{k}} \to 0$ при $k \to + \infty $. Тогда найдутся такие $ - 1\, < \,{{y}_{1}}\, < \,{{y}_{2}}\, < \,{{3(2}^{k}}\, + \,1)$ и $\lambda ,\gamma > 0$, что пара $(H,\sigma )$, выбранная по схеме , обладает следующими свойствами с вероятностью 1 – $\exp ( - \Omega (n))$:

1. для всех $x \in [{{y}_{1}},{{y}_{2}}]:{{\Gamma }_{{\sigma ,\lambda }}}(x) = 0$;

2. количество раскрасок $\tau \in \mathcal{S}(H)$ таких, что $q(\sigma ,\tau ) > {{y}_{2}}$ не больше, чем

3.3. Завершение доказательства

При помощи теоремы о переносе 6, леммы 1 и известного значения математического ожидания (см. [16]) мы выводим аналог леммы 3 для модели .

Лемма 4. Пусть $c > {{c}_{{{\text{shat}}}}} = (3{\text{/}}{{2)}^{k}}\ln (2k){\text{/}}(3k)$ и $c\;\leqslant \;(1 - {{\varepsilon }_{k}})(3{\text{/}}{{2)}^{k}}$ для ${{\varepsilon }_{k}} \to 0$ при $k \to + \infty $. Тогда найдутся такие $ - 1 < {{y}_{1}} < {{y}_{2}}{{ < 3(2}^{k}} + 1)$ и константы $\lambda ,\gamma > 0$, что пара $(H,\sigma )$, выбранная по схеме , обладает следующими свойствами а.п.н.:

1. для всех $x \in [{{y}_{1}},{{y}_{2}}]:{{\Gamma }_{{\sigma ,\lambda }}}(x) = 0$;

2. количество раскрасок $\tau \in \mathcal{S}(H)$ таких, что $q(\sigma ,\tau ) > {{y}_{2}}$ не больше, чем ${{e}^{{ - \gamma n}}}|\mathcal{S}(H)|$.

Наконец, лемма 4 позволяет доказать основную теорему 5. Назовем раскраску $\sigma $ типичной, если для нее верны оба пункта леммы 4. Для всякой типичной раскраски $\sigma $ рассмотрим соответствующий ей регион:

Будем разбивать $\mathcal{S}(H)$ на такие соответствующие регионы. Согласно второму утверждению леммы 4, в каждом таком регионе содержится не более чем экспоненциально маленькая доля всех правильных раскрасок, откуда напрямую следует, что для того, чтобы покрыть все $\mathcal{S}(H)$, их нужно экспоненциально много. Нетрудно показать, что для всякой :

• ${\text{dist}}(\sigma ,\tau )\; \geqslant \;\delta n$ для некоторого $\delta > 0$;

• для всякого пути из $\sigma $ в $\tau $ найдется $\sigma {\kern 1pt} '$ из этого пути, такая что $q(\sigma ,\sigma {\kern 1pt} ') \in [{{y}_{1}},{{y}_{2}}]$.

В силу первого утверждения леммы 4 и определения ${{\Gamma }_{{\sigma ,\lambda }}}$ мы сразу получаем утверждение теоремы.