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

1.1. Определения

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

В работе изучаются вершинные раскраски гиперграфов. Формально раскраской множества вершин гиперграфа $H = (V,E)$ в $r$ цветов называется отображение $f:V \to \{ 1, \ldots ,r\} $. Для раскраски $f$ вводятся множества ${{V}_{i}} = {{f}^{{ - 1}}}(i)$, $i = 1, \ldots ,r$, образующие разбиение $V$. Они называются цветовыми классами раскраски $f$. В теории графов широко известно понятие правильной раскраски графа, в которой любые две смежные вершины имеют разные цвета. Оно неоднозначно переносится на случай гиперграфов, здесь можно ввести целую серию $j$-правильных раскрасок, параметризуемую натуральной величиной $j$. А именно, для $j > 0$ раскраска множества вершин гиперграфа $H = (V,E)$ в $r$ цветов называется $j$-правильной, если в ней каждое ребро гиперграфа содержит не более $j$ вершин каждого из $r$ цветов. Например, при $j = 1$ это означает, что все вершины ребра должны быть покрашены в разные цвета. Если гиперграф $k$-однороден, то имеет смысл рассматривать только $1 \leqslant j \leqslant k - 1$, иначе любая раскраска будет $j$-правильной.

Минимальное число цветов $r$, необходимое для $j$-правильного раскрашивания вершин гиперграфа $H$, называется $j$-хроматическим числом $H$ и обозначается через ${{\chi }_{j}}(H)$. Отметим, что для графов (2-однородных гиперграфов) параметр $j$ может быть равен только 1. В теории гиперграфов классическому понятию хроматического числа гиперграфа, $\chi (H)$, введенному Эрдешем и Хайналом, соответствует ситуация $j = k - 1$.

В работе исследуется $j$-хроматическое число случайного $k$-однородного гиперграфа в биномиальной модели $H(n,k,p)$, где $n > k \geqslant 2$, $p \in (0,1).$ Напомним, что модель $H(n,k,p)$ представляет собой схему Бернулли на ребрах полного $k$-однородного гиперграфа на $n$ вершинах: каждое $k$-подмножество $n$-элементного множества вершин включается в $H(n,k,p)$ в качестве ребра независимо с вероятностью $p$. При $k = 2$ мы получаем хорошо известную модель случайного графа $G(n,p)$, также называемую моделью Эрдеша–Реньи. Перечисленные модели являются центральными объектами изучения вероятностной комбинаторики. В рамках статьи мы предполагаем, что $k > 2$ и $1 \leqslant j \leqslant k - 1$ фиксированы, $n$ стремится к бесконечности и $p = p(n) \in (0,1)$ является функцией от $n$.

1.2. История задачи

Исследования асимптотического поведения хроматического числа случайного графа $G(n,p)$ начались еще в 70-е годы прошлого века. Здесь стоит отметить работы Дж. Гримметта, К. Макдиармида [1], Б. Боллобаша [2], Т. Лучака [3, 4], Н. Алона и М. Кривелевича [5]. Из работ [4, 5] в частности, следовало, что при достаточно быстро стремящейся к нулю функции $p(n)$ (например, $p(n) \leqslant {{n}^{{ - 1/2 - \varepsilon }}}$ для некоторого фиксированного $\varepsilon > 0$) $\chi (G(n,p))$ с вероятностью, стремящейся к 1 с ростом $n$, принадлежит множеству из двух соседних значений $\{ h,h + 1\} $ для некоторой неизвестной функции $h = h(n,p)$. В дальнейшем поиску данной функции были посвящены работы Д. Аклиоптаса, А. Наора [6], А. Койя-Оглана, К. Панайоту, А. Штегер [7], С. Каргальцева, Д. Шабанова и Т. Шайхеевой [8]. В работе [6] искомая функция $h$ была найдена в так называемом разреженном случае, когда среднее число ребер линейно по числу вершин, т.е. когда $p(n) = cn{\text{/}}\left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right)$ для $c > 0$, не зависящего от $n$. А именно, если $c > 1$ задано и ${{r}_{c}} = \min \{ r \in \mathbb{N}$ : $c < r\ln r\} $, то при p = = $cn{\text{/}}\left( \begin{gathered} n \hfill \\ 2 \hfill \\ \end{gathered} \right)$

Тем не менее оказалось, что в разреженном случае для большинства значений параметра $c$ имеет место даже одноточечная предельная концентрация значения хроматического числа случайного графа. Связан подобный эффект с наличием точной пороговой вероятности для свойства наличия правильной раскраски в $r$ цветов при $r \geqslant 3$, ее наилучшие текущие оценки были получены в работах [9, 10].

Хроматические числа случайного гиперграфа $H(n,k,p)$ стали активно изучаться с 1980-х. В работах Дж. Шмидт, Э. Шамира и Э. Упфола [11–13] было найдено асимптотическое поведение ${{\chi }_{j}}(H(n,k,p))$ при определенных условиях на величину $p = p(n)$. В дальнейшем наиболее общий результат был получен в работе М. Кривелевича и Б. Судакова [14]. Для его формулировки введем величину $d = p\left( {\begin{array}{*{20}{c}} {n - 1} \\ {k - 1} \end{array}} \right)$, равную математическому ожиданию степени вершины в $H(n,k,p)$, и положим ${{d}_{j}} = j\left( {\begin{array}{*{20}{c}} {k - 1} \\ j \end{array}} \right)d$. Если $p{{n}^{{k - 1}}} \to \infty $ и $p{{n}^{{k - 1 - j}}}$ → 0, то для $j$-хроматического числа случайного гиперграфа выполнена следующая сходимость по вероятности:

Авторами [14] также было доказано, что в разреженном случае, когда снова среднее число ребер линейно по числу вершин, имеет место концентрация $j$-хроматического числа в ограниченном числе значений. А именно, если параметр ${{d}_{j}}$ фиксирован, но достаточно велик, то с вероятностью, стремящейся к 1 при $n \to \infty $, выполнены следующие неравенства

Дальнейшие продвижения в вопросе концентрации $j$-хроматического числа были сделаны в классическом случае $j = k - 1$, т.е. для обычного хроматического числа. Нам снова будет удобно ввести параметр $c$, отвечающий пропорции среднего числа ребер по отношению к числу вершин, т.е. пусть $p = cn{\text{/}}\left( \begin{gathered} n \hfill \\ k \hfill \\ \end{gathered} \right)$. В разреженном случае, когда $c$ не зависит от $n$, хроматическое число согласно (1) ограничено, но можно гораздо более точно указать его значения. Обозначим ${{r}_{c}} = \min \{ r \in \mathbb{N}:c$ < ${{r}^{{k - 1}}}\ln r\} $. Тогда, конечно, $c \in [({{r}_{c}} - {{1)}^{{k - 1}}}\ln ({{r}_{c}} - 1),r_{c}^{{k - 1}}\ln {{r}_{c}})$, но в зависимости от положения параметра $c$ на отрезке хроматическое число будет равно ${{r}_{c}}$ или ${{r}_{c}} + 1$. А именно, в работах М. Дайера, А. Фриза и К. Гринхилл [15], П. Эйра, А. Койя-Оглана, К. Гринхилл [16] и Д. Шабанова [17] было доказано, что

• если $c > r_{c}^{{k - 1}}\ln {{r}_{c}} - \frac{1}{2}\ln {{r}_{c}}$, то

• если $c < r_{c}^{{k - 1}}\ln {{r}_{c}} - \frac{1}{2}\ln {{r}_{c}} - \psi (k,r)$, где $\psi (k,r)$ – некоторая ограниченная функция, которую можно выбрать равной $\psi (k,r)$ = $\frac{{r - 1}}{r} + {{o}_{{k,r}}}(1)$ и которую можно уменьшить до $\psi (k,r)$ = $\ln 2 + {{o}_{{k,r}}}(1)$ при $r > {{r}_{0}}(k)$, то

Внутри же небольшого отрезка $\left[ {r_{c}^{{k - 1}}\ln {{r}_{c}} - \frac{1}{2}\ln {{r}_{c}}} \right.$ – – $\psi (k,r)$, $r_{c}^{{k - 1}}\ln {{r}_{c}}$ – $\left. {\frac{1}{2}\ln {{r}_{c}}} \right]$ известно лишь, что хроматическое число с вероятностью, стремящейся к 1, равно ${{r}_{c}}$ или ${{r}_{c}} + 1$. Концентрация ${{\chi }_{{k - 1}}}(H(n,k,p))$ в неразреженном случае изучалась в работе [18], где было доказано, что при не слишком медленно убывающей функции $p(n)$ хроматическое число случайного гиперграфа сконцентрировано в некоторых двух соседних значениях, а также были найдены эти два значения в определенных случаях.

В общем случае, когда $j < k - 1$, концентрация $j$-хроматического числа изучалась, помимо уже упомянутого результата (1), только в разреженном случае. В работе [19] исследовалась пороговая вероятность $j$-правильной $r$-раскрашиваемости случайного гиперграфа $H(n,k,p)$ в ситуации, когда значение параметра однородности $k$ сильно превышает значение числа цветов $r$. Авторы [19] показали, что в разреженном случае, когда $p = cn{\text{/}}\left( \begin{gathered} n \hfill \\ k \hfill \\ \end{gathered} \right)$ и где $c > 0$ не зависит от $n$, для любого $r > 2$ существуют такие положительные числа ${{C}_{l}} = {{C}_{l}}(r)$, ${{C}_{u}} = {{C}_{u}}(r)$ и ${{k}_{0}} = {{k}_{0}}(r)$, что при $k > {{k}_{0}}$ и $1 < k - j < {{k}^{{1/4}}}$ выполнено следующее: если

то $P({{\chi }_{j}}\left( {H\left( {n,k,p} \right)} \right) > r) \to 1$ при $n \to + \infty $, а если то $P({{\chi }_{j}}\left( {H\left( {n,k,p} \right)} \right)\;\leqslant \;r) \to 1$ при $n \to \infty $.

Отметим несколько моментов относительно этой теоремы. Во-первых, параметр $j$ должен быть примерно равен $k$, $j \sim k$, но, все-таки, $j$ должно быть меньше $k - 1$. Во-вторых, зазор между оценками (2) и (3) стремится к нулю с ростом $k$. В-третьих, параметр $r$, отвечающий за ограничение на $j$-хроматическое число, должен быть заметно меньше $k$. Тем самым, данная теорема не позволяет сделать выводы о концентрации хроматического числа, но дает очень точные оценки пороговой вероятности для $j$-правильной $r$-раскрашиваемости при больших $k$.

Целью настоящей работы было получение схожих результатов, но для обратного случая, когда параметр однородности $k$ фиксирован, а параметр $r$ может быть сколь угодно большим. Единственный подобный результат был ранее получен также А. Семеновым и Д. Шабановым в [20] для случая $j = k - 2$. Авторами [20] было показано, что если $p = cn{\text{/}}\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$, $c > 0$ не зависит от $n$, $k \geqslant 9$ и $r > {{r}_{0}}(k)$, то при

выполнено $P({{\chi }_{{k - 2}}}(H(n,k,p)) > r) \to 1$ при $n \to \infty $, а при выполнено $P({{\chi }_{{k - 2}}}(H(n,k,p)) \leqslant r) \to 1$ при $n \to \infty $. Тем самым, при фиксированном $k$ и растущем $r$, получается зазор порядка $1{\text{/}}k + {{o}_{r}}(1)$. Целью нашей работы было получить аналоги результатов (4)–(5) для общей ситуации, когда $k{\text{/}}2 \leqslant j < k - 2$.

3.1. Идеи доказательств теорем 1 и 2

Доказательство теоремы 1 следует методу первого момента. Мы переходим к равномерной модели случайного гиперграфа $H{\kern 1pt} '(n,k,m)$, где $m\, = \,\left\lfloor {p\left( \begin{gathered} n \hfill \\ k \hfill \\ \end{gathered} \right)} \right\rfloor $ и $c > 0$ удовлетворяет неравенству (6). В модели $H{\kern 1pt} '(n,k,m)$ независимо, равновероятно и с возвращением выбираются $m$ ребер из всевозможных $k$-подмножеств множества вершин. С помощью метода каплинга можно показать, что при $p{\kern 1pt} ' = c{\kern 1pt} '{\kern 1pt} n{\text{/}}\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$, где $c{\kern 1pt} ' > c$, будет выполнено неравенство

Следовательно, для доказательства теоремы достаточно показать, что левая часть неравенства стремится к 1. Далее, рассматривается случайная величина ${{X}_{n}}$, равная числу $j$-правильных раскрасок $H{\kern 1pt} '(n,k,m)$ в $r$ цветов. С помощью нижеприведенной комбинаторной леммы можно оценить математическое ожидание ${{X}_{n}}$.

Лемма 1. Пусть $k \geqslant 7$, $k{\text{/}}2 \leqslant j < k$. Существует такое ${{r}_{0}} = {{r}_{0}}(k)$, что при $r \geqslant {{r}_{0}}$ и всех достаточно больших $n$ выполнено: для любых ${{v}_{1}}, \ldots ,{{v}_{r}}$ с условием $\sum\nolimits_{i = 1}^r {{{v}}_{i}}$ = n верно неравенство

Применяя лемму 1, можно показать, что при условии (6) выполнено $E{\kern 1pt} {{X}_{n}} \to 0$ при $n \to + \infty $, что завершает доказательство теоремы 1.

Утверждение теоремы 2 обосновывается с помощью метода второго момента. Возможность применения данного метода следует из наличия точной пороговой вероятности для свойства $j$-правильной раскрашиваемости в заданное число цветов у случайного гиперграфа $H(n,k,p)$. По определению функция ${{\hat {p}}_{{r,k,j}}} = {{\hat {p}}_{{r,k,j}}}(n)$ является точной пороговой вероятностью для свойства $j$-правильной раскрашиваемости в $r$ цветов, если для любого фиксированного $\varepsilon > 0$ выполнено, что

Существование точной пороговой вероятности в нашей задаче вытекает из работы Х. Хатами и М. Моллоя из [22], в которой утверждается, что любое свойство, выражаемое как наличие гомоморфизма из изучаемого гиперграфа в некоторый фиксированный (может быть, содержащий неправильные ребра) связный гиперграф, имеет точную пороговую вероятность. Существование точной пороговой вероятности заметно облегчает нашу задачу. Теперь нам не нужно доказывать напрямую, что вероятность наличия искомой раскраски стремится к единице, достаточно лишь показать, что в условиях теоремы 2 она отделена от нуля.

Как и в доказательстве теоремы 1, нам снова будет удобно перейти к равномерной модели случайного гиперграфа. Но в этот раз модель будет немного другая, а именно, мы вводим случайный гиперграф $H{\kern 1pt} '{\kern 1pt} '(n,k,m)$, где , состоящий из $m$ независимых случайных $k$-подмножеств множества вершин, причем и в каждом таком $k$-подмножестве все $k$ вершин выбираются случайно, независимо и равновероятно. Конечно, в подобном гиперграфе мы можем получить и совпадающие ребра, и ребра размера меньше, чем $k$, когда нам выпали повторяющиеся вершины. Поясним, как будем раскрашивать ребра, в которых встречаются повторяющиеся вершины: по-прежнему будет говорить, что ребро раскрашено $j$-правильно, если оно с учетом кратности повторяющихся вершин содержит не более $j$ вершин каждого цвета. Снова с помощью техники каплинга можно показать при $c{\kern 1pt} ' < c$ и $p{\kern 1pt} ' = c{\kern 1pt} 'n{\text{/}}\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$ будет выполнено соотношение

Следовательно, остается проверить, что в модели $H{\kern 1pt} '{\kern 1pt} '(n,k,m)$

Остается свести задачу к вычислению моментов некоторой случайной величины. В этом качестве качестве мы будем использовать ${{X}_{n}}$ – число $j$-правильных сбалансированных раскрасок случайного гиперграфа $H{\kern 1pt} '{\kern 1pt} '(n,k,m)$. Напомним, что раскраска называется сбалансированной, если все ее цветовые классы имеют одинаковую мощность. В лемме 1.4 работы [15] было доказано, что соотношение (10) достаточно проверить только по подпоследовательности тех $n$, что делятся на $r$, так что всюду далее мы будем считать, что $n$ делится на $r$.

Применяя неравенство Пэли–Зигмунда, мы получаем следующую цепочку неравенств

В итоге остается проверить, что в условиях теоремы имеет место следующее соотношение между моментами случайной величины ${{X}_{n}}$:

Комбинаторными вычислениями и применением формулы Стирлинга можно получить следующее выражение для отношения моментов случайной величины ${{X}_{n}}$:

где функция ${{G}_{c}}$ определялась в теореме 3, как ${{G}_{c}}(M) = \mathcal{H}(M) + c \cdot \mathcal{E}(M)$, а функции $\mathcal{H}$ и $\mathcal{E}$ были определены в (8). Кроме того, ${{{\mathbf{T}}}_{r}}$ в формуле (12) обозначает множество матриц размера $r \times r$, у которых все элементы являются целыми неотрицательными числами, а сумма в каждой строке и в каждом столбце равна $n{\text{/}}r$. Для завершения обоснования соотношения (11) остается применить теорему 3 и аппроксимировать получившуюся сумму гауссовским интегралом.

3.2. Идеи доказательств теоремы 3

Итак, пусть дана матрица $M \in {{{\mathbf{M}}}_{r}}$. Несложными преобразованиями можно получить следующее представление исследуемого выражения:

Для каждого $i = 1, \ldots ,r$ введем следующие функции:

Тогда в силу (8) будут выполнены следующие соотношения:

В связи с этим удобно рассматривать разности ${{\mathcal{H}}_{i}}(M) - c{{\mathcal{E}}_{i}}(M)$ для всех $i = 1, \ldots ,r$. Отметим очень важный факт: функции ${{\mathcal{H}}_{i}}(M)$ и ${{\mathcal{E}}_{i}}(M)$ зависят не от всей матрицы, а только лишь от ее $i$-й строки.

Основная идея анализа состоит в разбиении множества строк матрицы $M$ на центральные, хорошие и плохие в зависимости от максимального значения элемента. Строку с номером $i$ будем называть

• центральной, если

• хорошей, если

• плохой, если

Следующие три леммы оценивают разности ${{\mathcal{H}}_{i}}(M) - c \cdot {{\mathcal{E}}_{i}}(M)$ для разных типов строк.

Лемма 2. Если $r$ достаточно велико, то для любой центральной строки с номером $i$ выполнено

Лемма 3. Если $r$ достаточно велико, то для любой хорошей строки с номером $i$ выполнено

Лемма 4. Если $r$ достаточно велико, то для любой плохой строки с номером $i$ выполнено

где $f(k) > 0$ – некоторая положительная функция от $k$.

С помощью лемм 2–4 можно вывести необходимое неравенство (9), если в матрице $M$ есть хотя бы одна центральная строка или одна хорошая. Единственный непокрываемый ими случай – это одни плохие строки в матрице $M$. Данный случай рассматривается отдельно и именно в нем выводится ограничение (6).