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

1. ВВЕДЕНИЕ

Настоящая работа посвящена задачам теории Рамсея. Для начала напомним определение классического числа Рамсея в одном из наиболее естественных случаев. Пусть ${{K}_{n}}$ – полный граф на $n$ вершинах (граф обыкновенный, т.е. не содержит петель и кратных ребер, а также не имеет ориентации). Для обыкновенного графа $G$ на тех же $n$ вершинах обозначим ${{K}_{n}}{{\backslash }}G$ дополнение графа $G$, т.е. остовный подграф графа ${{K}_{n}}$, в котором нет ни одного ребра графа $G$ и есть все ребра, которых в графе $G$ нет. Независимым множеством вершин графа называется любое множество вершин, никакие две из которых не соединены ребром. Мощность максимального независимого множества вершин графа $G$ называется числом независимости и обозначается $\alpha (G)$. Кликой в графе называется любой его полный подграф. Мощность максимальной клики называется кликовым числом и обозначается $\omega (G)$. Двойственность числа независимости и кликового числа, отраженная даже в обозначениях, легко описывается очевидным равенством $\alpha (G) = \omega ({{K}_{n}}{{\backslash }}G)$. В этих терминах (диагональное) число Рамсея $R(k)$ для данного натурального k определяется как минимальное натуральное $n$, такое, что для любого остовного подграфа $G$ графа ${{K}_{n}}$ либо в $G$, либо в ${{K}_{n}}{{\backslash }}G$ есть клика мощности k.

Отыскание классических чисел Рамсея – одна из ключевых и в то же время труднейших проблем на стыке теории графов и теории алгоритмов. Сейчас известно, что (см. [1, 2])

Также есть множество результатов относительно малых k (см. [3]), но нам в дальнейшем будут интереснее асимптотические утверждения.

У классических чисел Рамсея есть огромное количество важных обобщений (см., например, [1–6]). В настоящей работе мы сосредоточимся на постановке, которая была впервые предложена в работе [7]. Пусть дана произвольная последовательность графов $\{ {{G}_{n}}\} $, $n \in \mathbb{N}$. Подчеркнем сразу, что здесь $n$ – это просто номер графа, т.е. это не обязательно число его вершин. Пусть, как и прежде, $k \in \mathbb{N}$. Обозначим ${{R}_{{\min }}}(\{ {{G}_{n}}\} ,k)$ минимальное натуральное $m$, такое, что для любого остовного подграфа $G$ графа ${{G}_{m}}$ либо в $G$, либо в ${{G}_{m}}{{\backslash }}G$ есть индуцированный подграф графа ${{G}_{m}}$ на $k$ вершинах. Обозначение ${{G}_{m}}{{\backslash }}G$ следует понимать как дополнение графа $G$ до графа ${{G}_{m}}$, т.е. мы, опять-таки, все ребра графа $G$ удаляем, а все ребра графа ${{G}_{m}}$, которых нет в $G$, проводим. Ребра, не принадлежащие графу ${{G}_{m}}$, в принципе возникнуть не могут.

Понятно прежде всего, что, поскольку клика – это индуцированный подграф графа ${{K}_{n}}$, причем иных индуцированных подграфов в полном графе не существует, справедливо равенство R(k) = = $R(\{ {{K}_{n}}\} ,k)$. С другой стороны, ясно, что для многих последовательностей графов данное определение не имеет смысла или тривиально. Более того, для классического случая рамсеевское свойство в некотором смысле монотонно: если для какого-то $n$ оно выполняется, то оно выполняется и для всех m ≥ n; если для какого-то $n$ оно не выполняется (т.е. существует такой граф на $n$ вершинах, что ни в нем, ни в его дополнении до ${{K}_{n}}$ нет k-клики), то оно не выполняется и для всех m ≤ n. Это связано, очевидно, с тем, что ${{K}_{n}}$ является подграфом каждого ${{K}_{m}}$ с m ≥ n. В общем случае это не так. А потому заведомо имеет смысл рассматривать и величину ${{R}_{{\max }}}(\{ {{G}_{n}}\} ,k)$, равную максимальному $m \in \mathbb{N}$, для которого существует такой остовный подграф $G$ графа ${{G}_{m}}$, что ни в нем, ни в ${{G}_{m}}{{\backslash }}G$ нет индуцированных k-вершинных подграфов графа ${{G}_{m}}$. Разумеется, R_max({K_n}, k) = = ${{R}_{{\min }}}(\{ {{K}_{n}}\} ,k)$ – 1, но в общем случае могут быть самые разные соотношения между двумя величинами.

В работе [7] в роли $\{ {{G}_{n}}\} $ выступила последовательность графов $G(n,n{\text{/}}2,n{\text{/}}4)$, где $n = 4l$, $l \in \mathbb{N}$, вершинами служат все возможные n/2-элементные подмножества множества $\{ 1, \ldots ,n\} $, а ребрами вершины соединяются тогда и только тогда, когда мощность пересечения соответствующих множеств равна $n{\text{/}}4$. Эти графы возникают в связи с задачами теории кодирования (см. [8, 9]), и в этой науке они называются графами или схемами Джонсона. Также они играют огромную роль в комбинаторной геометрии, и там их зачастую называют дистанционными графами (см. [9–14]). Отметим, наконец, что максимальная клика в графе $G(n,n{\text{/}}2,n{\text{/}}4)$ находится в прямом соответствии с классической матрицей Адамара (см. [8]).

На самом деле, $G(n,n{\text{/}}2,n{\text{/}}4)$ – это лишь очень специальный случай более общего графа Джонсона $G(n,r,s)$: снова вершинами здесь служат $r$‑элементные подмножества множества $\{ 1, \ldots ,n\} $, а ребра образуются тогда и только тогда, когда мощности пересечений равны s. Эти графы играют все ту же огромную роль в теории кодирования и в комбинаторной геометрии. Более того, при $s = 0$ возникают так называемые кнезеровские графы (см. [15–17]), являющиеся одними из центральных объектов современной комбинаторики. Наконец, нельзя не отметить тот факт, что $G(n,1,0)$ = = K_n, т.е. классический полный граф служит очень специальным случаем в общем многообразии ситуаций.

С графами $G(n,r,s)$ очень тесно связаны графы $G(n,r, < s)$. Отличие в том, что теперь ребра соответствуют парам вершин, пересечение которых имеет мощность, строго меньшую $s$.

В следующем разделе мы приведем формулировки основных результатов и дадим комментарии к ним. Наконец, в разделе 3 мы кратко изложим идеи доказательств.

2. ФОРМУЛИРОВКИ РЕЗУЛЬТАТОВ

Справедливы следующие теоремы.

Теорема 1. Пусть $r = r(n)$ и $s = s(n)$ – такие функции, что выполнены следующие условия:

1) если при всех достаточно больших $n$ верно неравенство $r - s \geqslant 2$, то ${{r}^{3}} = o\left( {n{\text{/}}\ln n} \right)$;

2) если при всех достаточно больших $n$ верно равенство $r - s = 1$, то ${{r}^{3}} = o(n{\text{/l}}{{{\text{n}}}^{3}}n)$;

3) функции $C_{n}^{r}$ и $C_{{n - s}}^{{r - s}}$ строго монотонно возрастают.

Тогда существует такое ${{k}_{0}}$, что для любого $k \geqslant {{k}_{0}}$ имеет место точное равенство

Очевидно, что ввиду монотонности функции $C_{{m - s}}^{{r - s}}$ число $m$ в формулировке теоремы определено однозначно. Ясно, что не составит труда во многих случаях найти и асимптотику этого $m$ как функции от k. Но гораздо пафоснее то, что здесь для очень широкого класса параметров найдено точное значение числа Рамсея. При этом, разумеется, классическое число Рамсея выпадает из условий теоремы, ведь ${{K}_{n}} = G(n,1,0) = G(n,1,$ <1), т.е. функция $C_{{n - 1}}^{{1 - 1}}$ должна бы монотонно расти, но она тождественно равна единице. Отметим также, что индекс $\max $ здесь по существу. Для min-случая мы не знаем аналогичных оценок, и у нас есть основания полагать, что в его рамках числа Рамсея некорректно определены.

Теорема 2. Пусть ${{G}_{n}}\, = \,({{V}_{n}},{{E}_{n}})$, $n \in \mathbb{N}$, – последовательность графов. Пусть ${{N}_{n}} = {\text{|}}{{V}_{n}}{\text{|}}$, ${{\alpha }_{n}}\, = \,\alpha ({{G}_{n}})$. Пусть ${{\gamma }_{n}}$ – это максимальное число вершин графа ${{G}_{n}}$, которые не смежны с обеими вершинами данного ребра. Допустим, величины N_n, ${{\alpha }_{n}},{{\gamma }_{n}}$ монотонно стремятся к бесконечности, причем ${{\alpha }_{n}} = o({{N}_{n}})$, и существует такая функция ${{\beta }_{n}}$, что выполнены следующие асимптотические условия:

1) ${{\beta }_{n}} > {{\gamma }_{n}}$ и ${{\beta }_{n}} = o({{\alpha }_{n}})$;

2) $\mathop {\log }\nolimits_2 {{N}_{n}} = o\left( {\frac{{{{\alpha }_{n}}}}{{{{\beta }_{n}}}}} \right)$;

3) $\mathop {\log }\nolimits_2 {{N}_{n}} = o\left( {{{\beta }_{n}} - {{\gamma }_{n}}} \right)$.

Пусть ${{\varphi }_{n}}$ – любая функция, которая стремится к нулю при $n \to \infty $ и с которой все еще верно, что $\mathop {\log }\nolimits_2 {{N}_{n}} = o\left( {{{\varphi }_{n}}({{\beta }_{n}} - {{\gamma }_{n}})} \right)$. Тогда существует такое ${{k}_{0}}$, что для любого $k \geqslant {{k}_{0}}$ выполнено неравенство ${{R}_{{\max }}}(\{ {{G}_{n}}\} ,k) \geqslant m,$ где $m$ – максимальное натуральное число, удовлетворяющее условиям $k \geqslant {{\alpha }_{m}}(1 + {{\varphi }_{m}})$ и $k < {{N}_{m}}$.

Если же $m$ таково, что $k\, \leqslant \,{{\alpha }_{m}}$, то

${{R}_{{\max }}}(\{ {{G}_{n}}\} ,k)$ < m.

С одной стороны, пафос теоремы 2 в ее общности. Начнем с того, что ее условиям удовлетворяют многие последовательности графов из теоремы 1. Дело в том, что для них ${{\alpha }_{n}} = C_{{n - s(n)}}^{{r(n) - s(n)}}$ (см. [18, 19]), ${{N}_{n}} = C_{n}^{{r(n)}}$, и пусть для простоты расчетов $r$ фиксировано, а s = 1 (кнезеровский граф). Тогда ${{\gamma }_{n}} \leqslant {{r}^{2}}C_{n}^{{r - 2}}$. Последняя величина имеет порядок роста ${{n}^{{r - 2}}}$, тогда как ${{\alpha }_{n}}$ растет как ${{n}^{{r - 1}}}$. Таким образом, выбрать нужную ${{\beta }_{n}}$ не составляет труда. Для других параметров считать чуть труднее, но картина похожая. Есть и множество других последовательностей графов, удовлетворяющих условиям теоремы 2 (ср. [21]).

С другой стороны, если теорема 1 давала точное значение числа Рамсея, то теорема 2 говорит, как правило, о его асимптотике (что, впрочем, тоже намного сильнее результатов о классической величине $R(k)$).

Как видно, ключевое отличие теорем 1 и 2 от того, что мы знаем про классическую величину $R(k)$, состоит в том, что для последней величины число независимости исходного графа ${{G}_{n}} = {{K}_{n}}$ равно 1, тогда как в теоремах 1 и 2 оно по условию строго монотонно возрастает. В следующем разделе мы приведем схемы доказательств, за счет которых это отличие станет еще яснее.

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

Верхние оценки в обеих теоремах достаточно просты. Дело в том, что независимые множества вершин являются, конечно, индуцированными подграфами в любых графах. В теореме 2 прямо из формулировки видно, как это использовать. В теореме 1 достаточно воспользоваться неравенством $k \leqslant C_{{m + 1 - s(m + 1)}}^{{r(m + 1) - s(m + 1)}}$, монотонностью функции, стоящей в правой части этого неравенства, и тем фактом, что эта функция как раз и выражает число независимости графа из теоремы 1 (см. [18–20]).

Нижние оценки значительно труднее. Для получения нижней оценки нужно доказать, что для данного $m$ существует остовный подграф исходного графа, у которого на каждом множестве из $k$ вершин хотя бы одно ребро исходного графа отсутствует и хотя бы одно ребро исходного графа присутствует (за счет этого ни в самом графе, ни в его дополнении не возникнет индуцированного подграфа исходного графа). Применяется вероятностный метод, т.е. берется случайный подграф исходного графа, в котором каждое ребро сохраняется независимо от остальных ребер с вероятностью 1/2. Доказывается, что при достаточно больших m вероятность множества графов, обладающих нужным свойством, положительна, откуда и следует существование таких графов. В доказательстве теоремы 1 оценки проводятся с помощью методов из работы [18], а в доказательстве теоремы 2 используется техника из статьи [21]. Также большую роль играют оценки в духе тех, что получены в работах [10, 11, 22].

Если говорить чуть более подробно, то в работах [18] и [21] доказывается, что с вероятностью, стремящейся к единице, число независимости случайного подграфа исходного графа не превосходит величины $C_{{m - s(m)}}^{{r(m) - s(m)}}$ в случае первой работы и строго меньше величины ${{\alpha }_{m}}(1 + {{\varphi }_{m}})$ в случае второй работы. Это равносильно тому, что при всех больших $m$ в каждом множестве вершин мощности $k$ есть хотя бы одно ребро исходного графа с вероятностью, большей половины. Но ребра сохраняются и исчезают с одной и той же вероятностью 1/2. Значит, верно и то, что в каждом множестве вершин мощности $k$ нет хотя бы одного ребра исходного графа с вероятностью, большей половины. А следовательно, с положительной вероятностью нет ни одного множества вершин размера $k$, где сохранились бы все ребра исходного графа (остался бы его индуцированный подграф), и нет ни одного множества вершин размера $k$, где пропали бы все ребра исходного графа (остался бы его индуцированный подграф в дополнении). Таким образом, существование искомых остовных подграфов обосновано и теоремы 1–2 доказаны.

Отметим, что фактически здесь использована так называемая устойчивость числа независимости случайного подграфа, которой в последние годы было посвящено множество работ (см., например, [23–25]).