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

Пусть $F$, $G$ – некоторые графы, а $H \subset G$ – остовный подграф $G$. Граф $H$ слабо $F$-насыщен в $G$, если существует последовательность графов $H = {{H}_{0}} \subset \; \cdots \; \subset {{H}_{m}} = G$ такая, что каждый граф ${{H}_{i}}$ получен из ${{H}_{{i - 1}}}$ добавлением ребра, которое принадлежит некоторой копии $F$ в ${{H}_{i}}$. Иначе говоря, все ребра графа $G{{\backslash }}H$ могут быть добавлены одно за другим таким образом, что при каждом добавлении создается хотя бы одна новая копия $F$. Наименьшее количество ребер в слабо $F$-насыщенном графе в $G$ называется числом слабого $F$-насыщения графа $G$ и обозначается ${\text{wsat}}(G,F)$. Это понятие было впервые предложено Боллобашем в 1968 г. в работе [3].

Точное значение числа слабого насыщения ${\text{wsat}}({{K}_{n}},{{K}_{s}})$ (как обычно, ${{K}_{n}}$ – полный граф на $n$ вершинах) было найдено Ловасом в работе [9]: при всех $n \geqslant s \geqslant 2$

Другим естественным паттерн-графом $F$ является полный двудольный граф ${{K}_{{s,t}}}$. Значение ${\text{wsat}}({{K}_{n}},{{K}_{{s,t}}})$ для произвольных $s$, $t$ до сих пор не найдено. Наболее общий результат был получен Калаи [4] в 1985 г., а также Кроненбер, Мартинс и Моррисон [8] в 2020 г.: при $t \geqslant 2$ и $n \geqslant 3t - 3$

Кроме того, в [8] были получены следующие оценки для произвольных $s$ и $t$:

При $s = 1$ несложно видеть, что wsat(K_n, ${{K}_{{1,t}}}) = \left( \begin{gathered} t \\ 2 \\ \end{gathered} \right)$. Случай $s = 2$ гораздо сложнее. Тем не менее нам удалось найти точное значение числа слабого насыщения и в этом случае.

Теорема 1. Для всех натуральных $t \geqslant 3$ и $n \geqslant t + 2$ справедливо следующее.

• Если $t$ нечетно или $n \geqslant 2t - 1$, то ${\text{wsat}}({{K}_{n}},{{K}_{{2,t}}})$ = = $n - 2 + \left( \begin{gathered} t \\ 2 \\ \end{gathered} \right)$.

• Если $t$ четно и $n \leqslant 2t - 2$, то ${\text{wsat}}({{K}_{n}},{{K}_{{2,t}}})$ = = $n - 1 + \left( \begin{gathered} t \\ 2 \\ \end{gathered} \right)$.

Как обычно, $G(n,p)$ – это биномиальный случайный граф на множестве вершин $[n]: = \{ 1, \ldots ,n\} $, где каждая пара различных вершин $i,j \in [n]$ смежна с вероятностью $p$ независимо от всех других пар. Здесь и далее мы будем говорить, что свойство графов выполнено асимпотически почти наверное, если его вероятность стремится к 1 при $n \to \infty $. В 2017 г. Коранди и Судаков [6] доказали, что если $s \geqslant 3$, то ${\text{wsat}}({{K}_{n}},{{K}_{s}})$ стабильно, т.е. при постоянной вероятности $p \in (0,\;1)$ асимптотически почти наверное

и задали вопрос о существовании пороговой вероятности для свойства стабильности и о ее значении. Нам удалось доказать, что пороговая вероятность существует и предъявить нетривиальные оценки ее значения [2].

Теорема 2. Существует такое $c$, что при p < < $c{{n}^{{ - \frac{2}{{s + 1}}}}}{{(\ln n)}^{{\frac{2}{{(s - 2)(s + 1)}}}}}$ асимптотически почти наверное ${\text{wsat}}(G(n,p),{{K}_{s}})$ ≠ ${\text{wsat}}({{K}_{n}},{{K}_{s}})$, а при p > > ${{n}^{{ - \frac{1}{{2s - 3}}}}}{{(\ln n)}^{2}}$ асимптотически почти наверное ${\text{wsat}}(G(n,p),{{K}_{s}})$ = ${\text{wsat}}({{K}_{n}},{{K}_{s}})$.

Естественно задаться вопросом о существовании графа $F$, для которого свойство стабильности не выполнено. Мы предполагаем, что такого графа не существует.

Гипотеза 1. Пусть $p \in (0,\;1)$ – некоторая константа. Тогда для каждого графа $F$ асимптотически почти наверное

В подтверждение этой гипотезы мы установили достаточно общее достаточное условие стабильности [5]. Обозначим $\delta (H)$ минимальную степень вершины в графе $H$. Без потери общности положим $V({{K}_{n}}) = [n]$.

Теорема 3. Пусть $F$ – граф без изолированных вершин, $p \in (0,\;1)$, $C \geqslant \delta (F) - 1$ – константы. Для каждого $n \in \mathbb{N}$, пусть $H_{n}^{0}$ – слабо $F$-насыщенный подграф ${{K}_{n}}$, содержащий такое множество вершин $S_{n}^{0} \subset [n]$ с $\left| {S_{n}^{0}} \right| \leqslant C$, что каждая вершина из $[n]{{\backslash }}S_{n}^{0}$ смежна с хотя бы $\delta (F) - 1$ вершинами из $S_{n}^{0}$. Тогда асимптотически почти наверное найдется подграф ${{F}_{n}} \subset G(n,p)$, являющийся слабо $F$-насыщенным, и у него $\min \{ |{\kern 1pt} E(G(n,p)){\kern 1pt} |$, $|{\kern 1pt} E(H_{n}^{0}){\kern 1pt} |\} $ ребер.

Из этой теоремы вытекает

Следствие 1. Пусть $p \in (0,\;1)$ – константа. Для произвольного графа $F$ без изолированных вершин асимптотически почти наверное равенство (3) выполнено, если для каждого $n \in \mathbb{N}$ существует наименьший (с ${\text{wsat}}({{K}_{n}},F)$ ребрами) слабо $F$-насыщенный подграф ${{K}_{n}}$, обладающий свойством, описанным в теореме 3.

Действительно, условие из теоремы 3 влечет неравенство ${\text{wsat}}(G(n,p),F)$ ≤ ${\text{wsat}}({{K}_{n}},F)$ асимптотически почти наверное. Так как асимптотически почти наверное каждая пара вершин $G(n,p)$ имеет хотя бы $\left| {V(F)} \right|$ попарно смежных общих соседей [10], то асимптотически почти наверное $G(n,p)$ слабо $({{K}_{n}},F)$-насыщен, что влечет ограниченность снизу числа слабого насыщения в $G(n,p)$ числом слабого насыщения в ${{K}_{n}}$.

Легко видеть, что следствие 1 влечет свойство стабильности (3) для $F = {{K}_{s}}$ и $F = {{K}_{{s,t}}}$ асимптотически почти наверное для всех возможных значений $s$, $t$ (несмотря на тот факт, что, вообще говоря, точное значение ${\text{wsat}}({{K}_{n}},{{K}_{{s,t}}})$ неизвестно). Заметим, что в силу (1) и (2) асимптотически почти наверное ${\text{wsat}}(G(n,p),{{K}_{{s,t}}})$ = $(s - 1)n + C(s,t)$ для некоторой константы $C = C(s,t)$.

Как было замечено выше, для $F = {{K}_{s}}$ мы до сих пор не знаем значение пороговой вероятности для свойства стабильности (даже в простейшем случае $s = 3$). Тем не менее нам удалось найти пороговую вероятность для звезд $F = {{K}_{{1,t}}}$ [5].

Теорема 4. Пусть $t \geqslant 3$. Обозначим p_t= = ${{n}^{{ - \frac{1}{{t - 1}}}}}{{[\ln n]}^{{ - \frac{{t - 2}}{{t - 1}}}}}$.

• Существует такая константа $c > 0$, что при $\frac{1}{{{{n}^{2}}}} \ll p < c{{p}_{t}}$ асимптотически почти наверное ${\text{wsat}}(G(n,p),{{K}_{{1,t}}})$ ≠ ${\text{wsat}}({{K}_{n}},{{K}_{{1,t}}})$.

• Существует такая константа $C > 0$, что при $p > C{{p}_{t}}$ асимптотически почти наверное ${\text{wsat}}(G(n,p),{{K}_{{1,t}}})$ = ${\text{wsat}}({{K}_{n}},{{K}_{{1,t}}})$.

Заметим, что теорема 4 не покрывает случай $t = 2$, как и случай p = $O\left( {{1 \mathord{\left/ {\vphantom {1 {{{n}^{2}}}}} \right. \kern-0em} {{{n}^{2}}}}} \right)$. Тем не менее эти случаи гораздо проще. Во-первых, если $t \geqslant 3$ и $p < \frac{Q}{{{{n}^{2}}}}$ для некоторого $Q > 0$, то асимптотически почти наверное $G(n,p)$ не содержит ${{K}_{{1,t - 1}}}$, и поэтому асимптотически почти наверное стабильность выполнена, если количество ребер в случайном графе строго равно $\left( \begin{gathered} t \\ 2 \\ \end{gathered} \right)$, что не выполнено асимптотически почти наверное при $p \ll \frac{1}{{{{n}^{2}}}}$ и выполнено с вероятностью, отделенной от 0 и 1, при $\frac{q}{{{{n}^{2}}}} < p < \frac{Q}{{{{n}^{2}}}}$ для некоторых $0 < q < Q$. Случай $t = 2$ тоже прост. Если $p > (1 + \varepsilon )\frac{{\ln n}}{{2n}}$ для некоторого $\varepsilon > 0$, то асимптотически почти наверное ${\text{wsat}}(G(n,p),{{K}_{{1,2}}})$ = ${\text{wsat}}({{K}_{n}},{{K}_{{1,2}}})$. Если $\frac{1}{{{{n}^{2}}}} \ll p$ < < $(1 - \varepsilon )\frac{{\ln n}}{{2n}}$, то асимптотически почти наверное ${\text{wsat}}(G(n,p),{{K}_{{1,2}}})$ ≠ ${\text{wsat}}({{K}_{n}},{{K}_{{1,2}}})$. Если $\frac{q}{{{{n}^{2}}}} < p < \frac{Q}{{{{n}^{2}}}}$ для некоторых $0 < q < Q$, то

отделена от 0 и 1. Если же $p \ll \frac{1}{{{{n}^{2}}}}$, то асимптотически почти наверное ${\text{wsat}}\left( {G(n,p),{{K}_{{1,2}}}} \right)$ = 0 ≠ ${\text{wsat}}\left( {{{K}_{n}},{{K}_{{1,2}}}} \right)$.

Заметим, наконец, что выполнена асимптотическая версия гипотезы 1.

Теорема 5. Для любой константы $p \in (0,\;1)$ и всякого графа $F$ асимптотически почти наверное

Коротко изложим основные этапы доказательства. Зафиксируем граф $F$ и $p \in (0,\;1)$. Напомним, что (см. [1]) найдется константа ${{c}_{F}}$ такая, что ${\text{wsat}}({{K}_{n}},F)$ = $({{c}_{F}} + o(1))n$. Более того, ${{c}_{F}} > 0$ тогда и только тогда, когда $F$ не содержит вершин степени 1. Если же $F$ содержит вершину степени 1, то несложно видеть, что для некоторой константы ${{w}_{F}}$ асимптотически почти наверное

Предположим, что $F$ содержит $s \geqslant 3$ вершин, и ни одна из них не имеет степень, равную 1. Хорошо известно [7], что множество вершин $G(n,p)$ может быть покрыто кликами размера ${{\log }_{{1/p}}}n$. Более строго, асимптотически почти наверное найдутся такие непересекающиеся множества ${{V}_{1}},\; \ldots ,\;{{V}_{m}} \subset [n]$, что ${{V}_{1}} \sqcup \; \ldots \; \sqcup {{V}_{m}}$ = [n], каждое множество ${{V}_{i}}$ имеет размер ${{{v}}_{i}} \in \left\{ {\left\lfloor {\mathop {\log }\nolimits_{1/p} n} \right\rfloor ,\left\lceil {\mathop {\log }\nolimits_{1/p} n} \right\rceil } \right\}$, и ${{V}_{i}}$ индуцирует клику в $G(n,p)$. Стандартным образом можно показать, что ${{V}_{i}}$ могут быть выбраны таким образом, что двудольные графы с частями $({{V}_{i}},{{V}_{{i + 1}}})$ псевдослучайны в следующем смысле: для каждого $i \in [m]$ существуют непересекающиеся множества $S_{i}^{1},S_{i}^{2} \subset {{V}_{i}}$ размера $s - 2$, удовлетворяющие условиям

• $S_{i}^{2} \sqcup S_{{i + 1}}^{1}$ индуцируют полные подграфы в $G(n,p)$;

• каждая вершина из ${{V}_{{i + 1}}}{{\backslash }}S_{{i + 1}}^{1}$ имеет хотя бы $s - 2$ соседа ${{{v}}_{1}}, \ldots ,{{{v}}_{{s - 2}}}$ в ${{V}_{i}}$ таких, что каждая вершина ${{{v}}_{i}}$ смежна со всеми вершинами из $S_{{i + 1}}^{1}$.

Каждый индуцированный подграф $G(n,p)[{{V}_{i}}]$ содержит подграф ${{H}_{i}}$ с ${\text{wsat}}({{K}_{{{{{v}}_{i}}}}},F)$ ребрами. Рассмотрим граф $H$, полученный объединением ${{H}_{i}}$ с $m - 1$ полными двудольными графами с частями $\left( {S_{i}^{2},S_{{i + 1}}^{1}} \right)$, $i \in [m - 1]$. Заметим, что у $H$ не более

ребер, и что он является слабо $F$-насыщенным в $G(n,p)$. Остается заметить, что асимптотически почти наверное $G(n,p)$ является слабо $F$-насыщенным в ${{K}_{n}}$, и поэтому асимптотически почти наверное ${\text{wsat}}(G(n,p),F)$ ≥ ${\text{wsat}}({{K}_{n}},F)$.