Доклады Российской академии наук. Математика, информатика, процессы управления, 2022, T. 502, № 1, стр. 37-41

1. ВВЕДЕНИЕ И ИСТОРИЯ ЗАДАЧИ

В работе изучается проблема теории случайных гиперграфов, связанная с сильным хроматическим числом. Прежде чем обсуждать детали задачи, мы приведем ряд необходимых определений из теории гиперграфов.

В дискретной математике гиперграфом называется пара множеств $H = \left( {V,E} \right),$ где $V$ – это некоторое конечное множество, элементы которого называются вершинами гиперграфа, а $E$ – это совокупность подмножеств множества вершин $V,$ которые принято называются ребрами гиперграфа. Если каждое ребро гиперграфа состоит ровно из $k$ вершин, то гиперграф называется k-однородным. Раскраска f множества вершин гиперграфа $H = \left( {V,E} \right)$ в $q \in \mathbb{N}$ цветов – это отображение $f{\kern 1pt} :\;V \to \{ 1, \ldots ,q\} $. Раскраска вершин гиперграфа называется сильной, если в ней две вершины раскрашены в разные цвета всегда, когда они вместе принадлежат некоторому общему ребру. Формально, раскраска f – сильная, если для любого ребра $A \in E$ и любых различных вершин $u,v \in A$ выполнено $f(v) \ne f(u)$. Сильным хроматическим числом, ${{\chi }_{s}}(H)$, гиперграфа $H$ называется такое наименьшее количество цветов $q$, что для $H$ существует сильная раскраска вершин в $q$ цветов. Отметим, что если $H$ – это 2-однородный гиперграф, т.е. обычный граф без петель и кратных ребер, то для него понятие сильной раскраски совпадает с понятием обычной правильной раскраски, а сильное хроматическое число равняется хроматическому числу.

В настоящей работе исследуются сильные хроматические числа случайных гиперграфов в классической биномиальной модели $H(n,k,p)$. Случайный k-однородный гиперграф на $n$ вершинах $H(n,k,p)$ представляет собой схему Бернулли на множестве ребер полного k-однородного гиперграфа $K_{n}^{{(k)}}$ на $n$ вершинах: каждое ребро $K_{n}^{{(k)}}$ включается в $H(n,k,p)$ в качестве ребра независимо от других с вероятностью $p \in (0,1)$. В случае k = 2 случайный гиперграф $H(n,2,p)$ есть в точности широко известная модель случайного графа $G(n,p)$, также называемой моделью Эрдеша–Реньи. В рамках работы мы считаем, что k ≥ 2 фиксировано, $n \to + \infty $, а $p = p(n)$ есть некоторая функция от $n$. Перейдем к обсуждению известных результатов относительно ${{\chi }_{s}}(H(n,k,p))$.

Сильное хроматическое число случайного гиперграфа $H(n,k,p)$ активно изучается с середины 80-х годов прошлого века. Первые результаты были найдены в работах Дж. Шмидт [1] и Э. Шамира [2], а наиболее общий результат об асимптотическом поведении ${{\chi }_{s}}(H(n,k,p))$ был получен М. Кривелевичем и Б. Судаковым в [3]. Обсудим последний результат более детально. Обозначим d = = $(k - 1)\left( \begin{gathered} n - 1 \hfill \\ k - 1 \hfill \\ \end{gathered} \right)p$. Авторы [3] показали, что если $d$ достаточно велико, но при этом $d = o(n)$, то

Отметим, что результат (1) обобщает ранее известный результат Т. Лучака [4] для случайных графов. В случае, когда параметр $d$ неограниченно растет, как функция от $n$, соотношение (1) дает асимптотику (закон больших чисел) сильного хроматического случайного гиперграфа $H(n,k,p)$. Если же $d$ – это фиксированная величина, то мы получаем некоторые оценки ${{\chi }_{s}}(H(n,k,p))$, которое в этом случае с вероятностью, стремящейся к 1, будет ограничено. Целью настоящей работы является получение гораздо более сильных результатов в данной “разреженной” ситуации, т.е. в ситуации, когда среднее число ребер $H(n,k,p)$ линейно по числу вершину, что и соответствует фиксированному параметру d.

Исследования предельного распределения сильного хроматического числа случайного гиперграфа в разреженном случае тесно связаны с поиском точных пороговых вероятностей для свойств сильное хроматическое число не превосходит q. Напомним, что для заданного натурального числа $q \geqslant 3$ функция ${{\hat {p}}_{q}} = {{\hat {p}}_{q}}(n)$ называется точной пороговой для свойства сильное хроматическое число не превосходит q, если для любого фиксированного $\varepsilon > 0$ выполнено

Существование точной пороговой вероятности для произвольного свойства, вообще говоря, не гарантировано. Но для изучаемого нами свойства наличия сильной раскраски в заданное число цветов оно следует из общего результата Х. Хатами и М. Моллоя [5] о существовании точных пороговых вероятностей для свойств, выражаемых в виде наличия гомоморфизма в заданный гиперграф.

Для изложения результатов о точных пороговых вероятностях удобно использовать следующую параметризацию. Положим $c = p\left( \begin{gathered} n \hfill \\ k \hfill \\ \end{gathered} \right){\text{/}}n$, тогда в разреженном случае среднее число ребер линейно по $n$, $p\left( \begin{gathered} n \hfill \\ k \hfill \\ \end{gathered} \right) = cn$, и, значит, c не зависит от $n$. Оценки пороговых вероятностей наиболее наглядно и удобно формулировать как раз в виде ограничений на параметр c. Для сильных раскрасок $H(n,k,p)$ наиболее исследованным является, конечно, случай $k = 2$, случай графов. Здесь первые интересные результаты были получены в известной работе Д. Аклиоптаса и А. Наора [6]. Они, с одной стороны, показали, что при c > > $q{\text{ln}}q - \frac{1}{2}{\text{ln}}q$ выполнено

а с другой, что при $c < (q - 1)\ln (q - 1)$ выполнено обратное

Тем самым, имеется лишь относительно небольшой зазор (порядка $\frac{1}{2}\ln q$ при больших q), в котором может находиться пороговое значение. В дальнейшем, данные оценки были заметно усилены в работах А. Койя-Оглана [7] и А. Койя-Оглана и Д. Виленчика [8]. Авторы [7] и [8] показали, что при $c > q\ln q - \frac{1}{2}\ln q - 1{\text{/}}2 + {{o}_{q}}(1)$ также верно, что

но уже при $c < q\ln q - \frac{1}{2}\ln q - \ln 2 + {{o}_{q}}(1)$ выполнено обратное

Полученные оценки крайне близки, зазор составляет лишь ограниченную величину ${\text{ln}}2 - 1{\text{/}}2$ + + o(1). Отметим, что под ${{o}_{q}}(1)$ мы понимаем некоторую функцию от q, которая стремится к нулю с ростом q.

Сильные раскраски случайных гиперграфов изучены заметно хуже. Хорошо исследован только случай 3-однородных гиперграфов, для которых близкие оценки пороговых вероятностей были получены в работе А.Е. Балобанова и Д.А. Шабанова [9]. Ими была доказана следующая

Теорема 1 [9]. Пусть $p\left( \begin{gathered} n \hfill \\ 3 \hfill \\ \end{gathered} \right) = cn$, $c > 0$ не зависит от $n$.

1. Для фиксированного $q \geqslant 3$ если

то выполнено $\mathop {\lim }\limits_{n \to + \infty } {\text{P}}\left( {{{\chi }_{s}}\left( {H\left( {n,3,cn{\text{/}}\left( \begin{gathered} n \hfill \\ 3 \hfill \\ \end{gathered} \right)} \right)} \right) > q} \right) = 1$.

2. Существует такое ${{q}_{0}}$, что при $q > {{q}_{0}}$ и

выполнено $\mathop {\lim }\limits_{n \to + \infty } {\text{P}}\left( {{{\chi }_{s}}\left( {H\left( {n,3,cn{\text{/}}\left( \begin{gathered} n \hfill \\ 3 \hfill \\ \end{gathered} \right)} \right)} \right) \leqslant q} \right) = 1$.

Видно, что, как и для случая графов, зазор есть некоторая ограниченная функция от q. При $k > 3$ единственная попытка получить содержательные оценки пороговых вероятностей сильной раскрашиваемости случайного гиперграфа была предпринята в работе А.Э. Хузиевой [10], где было доказано, что при

выполнено

2. НОВЫЕ РЕЗУЛЬТАТЫ

Целью настоящей работы было получение новых оценок точных пороговых вероятностей для свойства наличия сильной раскраски случайного гиперграфа в заданное число цветов. Нами было получено полное обобщение результата Балобанова и Шабанова для 3-однородных гиперграфов на общий случай, которое сформулировано в следующей теореме.

Теорема 2. Пусть $p\left( \begin{gathered} n \hfill \\ k \hfill \\ \end{gathered} \right) = cn$, $c > 0$, не зависит от $n$, k ≥ 4 фиксировано. Существует такое ${{q}_{0}} = {{q}_{0}}(k)$, что если $q > {{q}_{0}}(k)$ и

1)

то выполнено $\mathop {\lim }\limits_{n \to + \infty } {\text{P}}\left( {{{\chi }_{s}}(H(n,k,p)) > q} \right) = 1$;

2)

то выполнено $\mathop {\lim }\limits_{n \to + \infty } {\text{P}}\left( {{{\chi }_{s}}(H(n,k,p)) \leqslant q} \right) = 1$.

Прокомментируем полученные результаты. Во-первых, оценки (4), (5) при $k = 3$ совпадают в точности с (2) и (3). Тем самым, мы действительно получили полное обобщение. Во-вторых, нижняя оценка (5) при k = 4 улучшает результат Хузиевой из [10]. В-третьих, зазор между оценками (4), (5) является ограниченной функцией от $q$ и, кроме того, при больших $k$ и $q$ может стать сколько угодно малым. Отметим, что последнее свойство важно и на сегодняшний день оно отсутствует, например, в случае слабых раскрасок гиперграфов. Более подробно со слабыми раскрасками читатель может ознакомиться в работах [11–13]. Некоторые недавние результаты об оценках пороговых вероятностей для других свойств раскрасок можно найти, например, в [14, 15]. Наконец, наши результаты показывают, что сильное хроматическое число случайного гиперграфа в разреженном случае сконцентрировано в одном или двух значениях.

В следующем разделе мы приведем идеи доказательства теоремы 2.

3. ИДЕИ ДОКАЗАТЕЛЬСТВА

Доказательство теоремы 2 следует общей схеме применения метода второго момента из работы М. Дайера, А. Фриза и К. Гринхилл [11]. Оно состоит из обоснования двух утверждений. Первое говорит, что при условии (4) случайный гиперграф с вероятностью, стремящейся к 1, не допускает сильной раскраски в $q$ цветов. Здесь мы переходим к равномерной модели случайного гиперграфа и применяем метод первого момента. В рамках последнего необходимо показать, что среди всех раскрасок наибольшую вероятность того, что случайное ребро будет правильно раскрашено в сильном смысле, дают так называемые сбалансированные раскраски, в которых в каждый цвет раскрашено $\left\lceil {n{\text{/}}q} \right\rceil $ или $\left\lfloor {n{\text{/}}q} \right\rfloor $ вершин. Поговорим более детально о доказательстве второго утверждения теоремы 2.

Вторая часть теоремы 2 говорит, что при условии (5) с вероятностью, стремящейся к 1, сильная раскраска случайного гиперграфа $H(n,k,p)$ существует. Метод второго момента является стандартным методом решения в подобных задачах, но технически это очень трудный способ, упирающийся в решение разных оптимизационных проблем. Первый шаг – это использование существования точной пороговой вероятности. Данный факт позволяет доказывать лишь отделимость искомой вероятности от нуля. Действительно, если для некоторого $c$ мы покажем, что

то для любого c' < c" будет выполнено ведь величина $p = c{\kern 1pt} 'n{\text{/}}\left( \begin{gathered} n \hfill \\ k \hfill \\ \end{gathered} \right)$ будет заведомо меньше точной пороговой вероятности.

Второй шаг состоит в переходе к подпоследовательности чисел, делящихся на q, ${{n}_{t}} = tq$, $t \in \mathbb{N}$. Мы показываем, что достаточно проверять отделимость от нуля только по этой подпоследовательности. Далее, считаем, что $n$ делится на $q$.

Третий шаг – это переход к равномерной модели случайного гиперграфа. Обозначим через $H(n,k,m)$, $m = \left\lceil {cn} \right\rceil $, модель случайного гиперграфа с $m$ ребрами, которые выбираются независимо среди ${{n}^{k}}$ упорядоченных (с повторениями) наборов из $k$ вершин гиперграфа. В таком гиперграфе могут встречаться как повторяющиеся по составу вершин ребра, так и ребра с менее $k$ различными вершинами. С помощью метода каплинга несложно проверить, что для любого $c{\kern 1pt} ' < c$ будет выполнено

Тем самым, нам достаточно проверить, что вероятность ${\text{P}}\left( {{{\chi }_{s}}(H(n,k,m)) \leqslant q} \right)$ отделена от нуля при всех достаточно больших $n$.

Последний шаг состоит в рассмотрении множества сбалансированных сильных раскрасок случайного гиперграфа $H(n,k,m)$. Обозначим через X_n количество таких раскрасок. Тогда в силу неравенства Пэли–Зигмунда

Остается лишь показать, что отношение $\frac{{{{{({\text{E}}{{X}_{n}})}}^{2}}}}{{{\text{E}}X_{n}^{2}}}$ отделено от нуля или, эквивалентно, что существует такая положительная функция $A(k,q) > 0$, что для всех достаточно больших $n$ выполнено

В рамках вычисления отношения в левой части (6) естественным образом возникает сумма по некоторому семейству дважды стохастических матриц, которую нужно оценивать. Оценка требует решения следующей оптимизационной задачи.

Пусть $q \geqslant 2$ – натуральное число. Рассмотрим множество ${{\mathcal{M}}_{q}}$ матриц размера q × q с неотрицательными элементами, которые удовлетворяют следующим свойствам сумм элементов по столбцам и строкам: для любой M = $({{m}_{{ij}}}{\kern 1pt} :\;i,j = 1 \ldots ,r) \in {{\mathcal{M}}_{q}}$ выполнено

1) для любого $i = 1, \ldots ,\,\,q$ выполнено $\sum\limits_{j = 1}^r {{m}_{{ij}}} = \frac{1}{q}$;

2) для любого $j = 1, \ldots ,\,\,q$ выполнено $\sum\limits_{i = 1}^r {{m}_{{ij}}} = \frac{1}{q}$.

Далее, для каждой $M \in {{\mathcal{M}}_{q}}$ введем функции:

и ${{\mathcal{G}}_{{q,c}}}(M) = {{\mathcal{H}}_{q}}(M) + c \cdot {{\mathcal{E}}_{q}}(M)$, где $c > 0$ – некоторое положительное число. Очень важной и имеющей самостоятельный интерес является следующая

Лемма 1. Для любого $k \geqslant 4$ существует такое ${{q}_{0}} = {{q}_{0}}(k)$, что для всех $q > {{q}_{0}}$ и всех c, удовлетворяющих неравенству (5), максимальное значение функции ${{\mathcal{G}}_{{q,c}}}(M)$ достигается при $M = {{J}_{q}}$, где ${{J}_{q}}$ – это матрица размера q × q, все элементы которой равны $1{\text{/}}{{q}^{2}}$. Более того, в тех же условиях существует такая функция $b(k,q) > 0$, что для всех $M \in {{\mathcal{M}}_{q}}$ выполнено

Отметим, что доказательство леммы 1 в отличие от аналогичных утверждений из работ [9] и [13] сильно затруднено невозможностью проводить “построчный” анализ, когда разность ${{\mathcal{G}}_{{q,c}}}({{J}_{q}}) - {{\mathcal{G}}_{{q,c}}}(M)$ распадается в сумму слагаемых, каждое из которых зависит только от одной строки матрицы M. С помощью леммы 1 несложно устанавливается неравенство (6), что завершает доказательство теоремы 2.