Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 494, № 1, стр. 30-34

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

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

В дискретной математике гиперграфом называется пара множеств $H = \left( {V,E} \right),$ где $V$ – это некоторое конечное множество, элементы которого называются вершинами гиперграфа, а E – это совокупность подмножеств множества вершин V, которые принято называются ребрами гиперграфа. Пусть $k$ – это натуральное число, тогда гиперграф называется k-однородным, если каждое его ребро состоит ровно из $k$ вершин. Раскраской f множества вершин гиперграфа $H = (V,E)$ в $r \in \mathbb{N}$ цветов мы будем называть произвольное отображение вида $f{\text{:}}\;V \to {\text{\{ }}1, \ldots ,r{\text{\} }}$. Раскраска вершин гиперграфа называется правильной, если в ней каждое его ребро не является одноцветным, а содержит вершины хотя бы двух различных цветов. Наконец, хроматическим числом $\chi (H)$ гиперграфа $H$ называется такое наименьшее количество цветов r, что для $H$ существует правильная раскраска вершин в r цветов.

В настоящей работе исследуются хроматические числа случайных гиперграфов. А именно, мы рассматриваем классическую биномиальную модель случайного гиперграфа $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)$, также известную как модель Эрдеша–Реньи. Нас будет интересовать асимптотическое поведение хроматического числа $H(n,k,p)$ при фиксированном $k \geqslant 2$, стремящемся к бесконечности $n$ и некоторой функции $p = p(n)$. Перейдем к обсуждению известных результатов относительно $\chi (H(n,k,p))$.

Одним из фундаментальных результатов о хроматическом числе случайного графа является известная теорема Т. Лучака 1991 г. (см. [1]), которая утверждает, что для любого фиксированного ε > 0 выполнено следующее: если функция $p = p(n)$ удовлетворяет условию $p \leqslant {{n}^{{ - 5/6 - \varepsilon }}}$, то существует такая функция $h = h(n,p)$ с натуральными значениями, что

Тем самым, при не слишком медленном убывании $p = p(n)$ хроматическое число случайного графа $G(n,p)$ с вероятностью, стремящейся к единице, сконцентрировано в некоторых двух соседних значениях. Однако, несмотря на силу теоремы Лучака, ее доказательство не позволяет явным образом найти значение $h = h(n,p)$ из (1). В дальнейшем поиску данной функции для различных функций $p = p(n)$ и вообще феномену концентрации значений были посвящены работы Н. Алона и М. Кривелевича [2], Д. Аклиоптаса и А. Наора [3], А. Коджа-Оглана с различными соавторами [4–6], С.А. Каргальцева, Д.А. Шабанова и Т.М. Шайхеевой [7].

Хроматическое число случайного гиперграфа $H(n,k,p)$ активно изучается с середины 80-х годов прошлого века. Наиболее общий результат об асимптотическом поведении $\chi (H(n,k,p))$ был получен М. Кривелевичем и Б. Судаковым в [8]. Однако вопрос о концентрации значений хроматического числа в работе [8] не изучался. Одни из первых результатов в этом направлении были получены в работе М. Дайера, А. Фриза и К. Гринхилл в 2015 г. [9]. Они рассматривали разреженный случай, когда число ребер в среднем линейно по числу вершин, т.е. $p\left( \begin{gathered} n \hfill \\ k \hfill \\ \end{gathered} \right) = cn$ для фиксированного c > 0. Авторами [9] было показано, что для фиксированного натурального $r \geqslant 2$ выполнено следующее:

1. Если $c > {{r}^{{k - 1}}}lnr - \tfrac{1}{2}lnr$, то

2. Если положить ${{u}_{r}} = {{r}^{{k - 1}}}lnr$, то существует такое ${{c}_{r}} \in ({{u}_{{r - 1}}},{{u}_{r}})$, что при любом $c < {{c}_{r}}$

3. Величину ${{c}_{r}}$ из предыдущего пункта можно выбрать равной

Тем самым, Дайер, Фриз и Гринхилл установили, что, как и для графов, в разреженном случае хроматическое число случайного гиперграфа сконцентрировано в одном или двух соседних значениях. Учитывая (2), видно, что при больших значениях r длина интервала, в котором указаны два значения хроматического числа, ${{u}_{r}} - \,\,\tfrac{1}{2}lnr - {{c}_{r}}$ имеет асимптотический порядок $\tfrac{1}{2}lnr$, т.е. растет с ростом r. В работах Д.А. Шабанова [10], а также П. Эйра, А. Коджа-Оглана и К. Гринхилл [11] было показано, что величину c_r можно выбрать равной ${{c}_{r}} = {{r}^{{k - 1}}}{\text{ln}}r - \tfrac{1}{2}{\text{ln}}r - O(1)$, что дает ограниченную длину отрезка неопределенности $\left[ {{{c}_{r}},{{u}_{r}} - \tfrac{1}{2}{\text{ln}}r} \right]$.

В заключении обзора имеющихся результатов авторы хотели бы обратить внимание читателя на работы о близких задачах о полноцветных и j-правильных раскрасках случайных гиперграфов, а также раскрасках случайных кнезеровских графов и гиперграфов (см. [12–15]).

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

Целью настоящей работы было установление феномена концентрации значений хроматического числа случайного гиперграфа $H(n,k,p)$ в неразреженном случае, т.е. при $p\left( \begin{gathered} n \\ k \\ \end{gathered} \right) \gg n$, и получение расширений результатов из [9–11] для разреженного случая.

Первый новый результат представлен в следующей теореме.

Теорема 1. Обозначим $c = c(n) = p\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)\tfrac{1}{n}$ и зафиксируем произвольное ε > 0. Если $c \to + \infty $ и $c = o(n)$, то для любой функции $r = r(n) \to + \infty $ с условием

выполнено

Вторым и центральным результатом настоящей работы является вторая теорема, позволяющая найти верхнюю оценку хроматического числа $H(n,k,p)$ при не слишком медленно убывающей функции $p = p(n)$.

Теорема 2. Пусть натуральное число $k \geqslant 4$ и $\gamma \in \left( {0,\frac{1}{8}} \right)$ фиксированы. Обозначим c = c(n) = = $p\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)\tfrac{1}{n}$. Если $c \leqslant {{n}^{{\frac{{k - 1}}{{2k + 4}} - \gamma }}}$ и $c \to + \infty $, то существует такая абсолютная константа $A > 0$, что для любой функции $r = r(n) \to + \infty $ с условием

выполнено

Поймем, как с помощью теорем 1 и 2 можно получить вывод о концентрации значений хроматического числа случайного гиперграфа. Во-первых, отметим, что параметр $c = \tfrac{1}{n}p\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)$ по сути заменяет собой вероятность p, однозначно ее определяя. Условие теоремы 2 на него жестче, требуется, чтобы $c \leqslant {{n}^{{\frac{{k - 1}}{{2k + 4}} - \gamma }}}$, т.е. $c = o(n)$ заведомо. Так что предположим, что выполнены условия теоремы 2.

Введем величину r_p = r_p(n) = $min{\text{\{ }}\ell \in \mathbb{N}$: $c\, < \,{{\ell }^{{k - 1}}}{\text{ln}}\ell {\text{\} }}$. Тогда, конечно, $c \in [{{({{r}_{p}} - 1)}^{{k - 1}}}ln({{r}_{p}}$ – 1), $r_{p}^{{k - 1}}{\text{ln}}{{r}_{p}}]$ и имеет место следующая картина.

1. В силу того, что $c \geqslant {{({{r}_{p}} - 1)}^{{k - 1}}}ln({{r}_{p}} - 1)$, из теоремы 1 сразу следует, что

2. В силу того, что c ≤ (r_p + 1)^{k – 1}${\text{ln}}({{r}_{p}}\, + \,1)\, - \,\tfrac{1}{2}$ln(r_p + + 1) – $\tfrac{{{{r}_{p}}}}{{{{r}_{p}} + 1}} - A\left( {\tfrac{{{{k}^{2}}ln{{r}_{p}}}}{{r_{p}^{{k/3 - 1}}}}} \right)$, из теоремы 2 следует, что

3. Далее, если $c > r_{p}^{{k - 1}}ln{{r}_{p}} - \tfrac{1}{2}ln{{r}_{p}} + \varepsilon $, то теорема 1 утверждает, что

4. Наконец, если c < $r_{p}^{{k - 1}}{\text{ln}}{{r}_{p}} - \tfrac{1}{2}{\text{ln}}{{r}_{p}} - \tfrac{{{{r}_{p}} - 1}}{{{{r}_{p}}}}$ –‒ $A\left( {\tfrac{{{{k}^{2}}{\text{ln}}{{r}_{p}}}}{{r_{p}^{{k/3 - 1}}}}} \right)$, то теорема 2 утверждает, что

В итоге мы получаем, что с вероятностью, стремящейся к 1,

1) на полуинтервале вида $c \in \left[ {{{{({{r}_{p}} - 1)}}^{{k - 1}}}{\text{ln}}{{{({{r}_{p}} - 1)}}_{{_{{_{{_{{_{{_{{}}}}}}}}}}}}}} \right.$, $\left. {r_{p}^{{k - 1}}{\text{ln}}{{r}_{p}} - \tfrac{1}{2}{\text{ln}}{{r}_{p}} - O(1)} \right)$ хроматическое число случайного гиперграфа сконцентрировано в двух значениях: r_p и r_p + 1;

2) на отрезке вида $c \in \left[ {r_{p}^{{k - 1}}{\text{ln}}{{r}_{p}} - \tfrac{1}{2}{\text{ln}}{{r}_{p}} - O(1)} \right.$, $\left. {r_{p}^{{k - 1}}{\text{ln}}{{r}_{p}} - \tfrac{1}{2}{\text{ln}}{{r}_{p}} + O(1)} \right]$ хроматическое число случайного гиперграфа сконцентрировано в трех значениях: r_p, r_p + 1 и r_p + 2;

3) на интервале вида $c \in \left[ {r_{p}^{{k - 1}}{\text{ln}}{{r}_{p}} - \tfrac{1}{2}{\text{ln}}{{r}_{p}} + O(1)} \right.$, $\left. {_{{_{{_{{_{{_{{_{{}}}}}}}}}}}}r_{p}^{{k - 1}}{\text{ln}}{{r}_{p}}} \right)$ хроматическое число случайного гиперграфа сконцентрировано снова в двух значениях: r_p + 1 и r_p + 2.

Тем самым, лишь в промежутке ограниченной длины мы имеем предельную концентрацию значений хроматического числа в трех числах, во всех остальных случаях доказана концентрация в двух.

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

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

Доказательства теорем 1 и 2 следуют общей схеме обоснования результатов из работы [6], которая, в свою очередь, опирается на идеи из [1]. Утверждение теоремы 1 использует переход к равномерной модели случайного гиперграфа, метод первого момента и аппроксимацию биномиального распределения. Поговорим более детально о доказательстве теоремы 2.

Важнейшим инструментом, который позволил доказать теорему 2, является следующий результат о дважды стохастических матрицах, полученный в [10]. Опишем данный результат. Пусть $r \geqslant 2$ – натуральное число. Рассмотрим множество ${{\mathcal{M}}_{r}}$ матриц размера r × r, которые удовлетворяют следующим свойствам: для любой M = (m_ij: $i,j = 1,\; \ldots ,\;r) \in {{\mathcal{M}}_{r}}$ и

1) для любых $i,j = 1,\;...\,,\;r$ выполнено ${{m}_{{ij}}} \geqslant 0$;

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

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

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

и ${{\mathcal{G}}_{d}}(M) = \mathcal{H}(M) + d \cdot \mathcal{E}(M)$, где d > 0 – некоторое положительное число. В работе [10] было получена следующая лемма (см. утверждение 1 в [10]).

Лемма 1. Существуют такие абсолютные константы ${{r}_{0}} > 0$ и A > 0, что для любых $r > {{r}_{0}}$, $k \geqslant 4$ и $d < {{r}^{{k - 1}}}lnr - \tfrac{1}{2}lnr - \tfrac{{r - 1}}{r} - A\left( {\tfrac{{{{k}^{2}}lnr}}{{{{r}^{{k/3 - 1}}}}}} \right)$ максимальное значение функции ${{\mathcal{G}}_{d}}(M)$ достигается при M = J_r, где J_r – это матрица размера r × r, все элементы которой равны 1/r².

Лемма 1 в сочетании с методом второго момента позволяет получить нижнюю оценку вероятности наличия правильной раскраски в r цветов у $H(n,k,p)$. Отметим, что теорему 2 достаточно доказать при r = r_p. Выполнена

Лемма 2. Пусть выполнены условия теоремы 2 и r = r_p. Тогда

Применяя дополнительно хорошо известные оценки вероятностей больших уклонений для мартингалов с ограниченными мартингальными разностями, можно показать, что большую часть гиперграфа $H(n,k,p)$ можно правильно раскрасить в r цветов. Более точно, выполнена

Лемма 3. Пусть выполнены условия теоремы 2 и r = r_p. Тогда с вероятностью, стремящейся к 1, существует такое подмножество вершин ${{U}_{0}} \subseteq V(H(n,k$, p)), что $\left| {{{U}_{0}}} \right| \leqslant {{n}^{{3/2}}}{{p}^{{1/(k - 1)}}}\sqrt {lnn} $ и подгиперграф, индуцированный на $V(H(n,k,p)){\backslash }{{U}_{0}}$, можно правильно раскрасить в $r$ цветов.

По сути, остается разобраться с раскраской “плохого” набора вершин U₀. В силу того, что мощность U₀ невелика, внутри него не найдется плотных подгиперграфов, и, значит, хроматическое число индуцированного подгиперграфа ограничено. Сформулируем точное утверждение.

Лемма 4. Пусть выполнены условия теоремы 2. Выберем фиксированное $\delta = \delta (k) > 0$ так, чтобы $1 - \delta k(k - 1) > 0$. Тогда с вероятностью, стремящейся к 1, любое подмножество вершин $U$ случайного гиперграфа $H(n,k,p)$ с условием

содержит внутри себя не более $\left( {\tfrac{{k + 1}}{{k(k - 1)}} - \delta } \right)\left| U \right|$ ребер $H(n,k,p)$.

С помощью лемм 2–4 несложно завершить доказательство. Мы строим такое множество U, удовлетворяющее лемме 4, которое, с одной стороны, включает в себя множество ${{U}_{0}}$ из леммы 3, а с другой – все вершины из $V(H(n,k,p)){\backslash }U$, которые содержатся в ребре хотя бы с одной вершиной из U, образуют независимое множество W. Тогда подгиперграф, индуцированный на U, можно правильно раскрасить в цвета {1, 2, 3}, вершины из независимого множества W в цвет r + 1, а оставшийся подгиперграф, индуцированный на $V(H(n,k,p)){\backslash }(U \cup W)$, можно правильно раскрасить в цвета {1, 2, …, r} в силу леммы 4.