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

Пусть $n \in \mathbb{N}$, F – некоторый граф. Числом насыщения ${\text{sat}}(n,F)$ называется наименьшее количество ребер в таком графе G на множестве вершин $[n]: = {\text{\{ }}1,\; \ldots ,\;n{\text{\} }}$, что

1) G не содержит ни одного подграфа, изоморфного F,

2) при добавлении любого отсутствующего ребра в G в нем появляется хотя бы один подграф, изоморфный F.

Иными словами, ${\text{sat}}(n,F)$ – это минимальное количество ребер в максимальном по включению графе без F на множестве вершин [n]. Числом слабого насыщения ${\text{wsat}}(n,F)$ называется наименьшее количество ребер в таком графе G на множестве вершин $[n]: = {\text{\{ }}1,\; \ldots ,\;n{\text{\} }}$, что

1) G не содержит ни одного подграфа, изоморфного F,

2) отсутствующие ребра можно добавить в такой последовательности в G, что каждое новое ребро будет создавать хотя бы одну новую копию F в текущем графе.

Разумеется, ${\text{wsat}}(n,F) \leqslant {\text{sat}}(n,F)$.

В [1] доказано, что для любых натуральных $s \leqslant n$ справедливо

где K_s – полный граф на s вершинах (или, как говорится, s-клика). В [2] Боллобаш выдвинул гипотезу о том, что для всех s справедливо равенство ${\text{wsat}}(n,{{K}_{s}}) = {\text{sat}}(n,{{K}_{s}})$. Заметим, что при s = 3 это равенство очевидно, так как звезда ${{K}_{{1,n - 1}}}$ (т.е. дерево, в котором одна вершина смежна со всеми остальными) содержит ровно n – 1 ребро, и добавление любого ребра создает треугольник, но при этом из несвязного графа “восстановить” все ребра нельзя. Гипотеза Боллобаша была доказана в [3].

В дальнейших работах о насыщении рассматривались другие графы F, а также предполагалось, что необходимо восстановить не все ребра между вершинами из $[n]$. Итак, пусть F, G – графы. Числом насыщения ${\text{sat}}(G,F)$ называется наименьшее количество ребер в максимальном по включению остовном подграфе G, не содержащем подграфов, изоморфных F. Числом слабого насыщения ${\text{wsat}}(G$, F) называется наименьшее количество ребер в таком остовном подграфе H графа G, не содержащем копий F, что отсутствующие ребра из $G{\backslash }H$ можно добавить в такой последовательности в H, что каждое новое ребро будет создавать хотя бы одну новую копию F в текущем графе.

В работах [4, 9] было оценено ${\text{wsat}}(n,F)$ для полного двудольного графа F. Точные значения ${\text{wsat}}(G,F)$, а также оценки ${\text{sat}}(G,F)$ в случае, когда оба графа являются полными двудольными, получены в работах [5, 6]. Работы [7, 8] посвящены оцениванию числа насыщения и числа слабого насыщения в случае, когда граф $G$ случаен.

Настоящая работа посвящена оцениванию величин ${\text{sat}}({\text{KG}}(n,k),{{K}_{s}})$ и ${\text{wsat}}({\text{KG}}(n,k),{{K}_{s}})$, где ${\text{KG}}(n,k)$ – кнезеровский граф, т.е. граф, в котором вершинами являются все k-элементные подмножества [n], при этом две вершины смежны, если они не пересекаются. Заметим, что в случае k = 1 задача уже решена, так как ${\text{KG}}(n,1)$ – это просто полный граф на $n$ вершинах. Кроме того, при $n < sk$ в ${\text{KG}}(n,k)$ нет ни одной s-клики, а значит, ${\text{wsat}}({\text{KG}}(n,k),{{K}_{s}}) = {\text{sat}}({\text{KG}}(n,k),{{K}_{s}})$ совпадает с числом ребер ${\text{KG}}(n,k)$, т.е. равно $\tfrac{1}{2}\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)\left( {\begin{array}{*{20}{c}} {n - k} \\ k \end{array}} \right)$.

Обратимся теперь к нетривиальным результатам. Начнем с числа насыщения. Пусть сперва s = 3. Если $n = 3k$, то никакие два треугольника в кнезеровском графе не имеют общего ребра, а значит,

Пусть теперь $n > 3k + 1$. К сожалению, даже в простейшем нетривиальном случае n = 7, k = 2, s = 3 нам не удалось найти точного значения числа насыщения.

Теорема 1. Справедливы оценки

В этой связи мы исследовали асимптотическое поведение ${\text{sat}}({\text{KG}}(n,k),{{K}_{3}})$ при $n \to \infty $ и $k = {\text{const}}$. При k = 2 нам удалось получить относительно точные оценки числа насыщения.

Теорема 2. При всех $n \geqslant 8$

При остальных $n$, $k$, $s$ нам не удалось получить настолько точных оценок. В оставшихся случаях мы только определили порядок роста.

Теорема 3. При всех $k \geqslant 3$ справедливо

При всех $k \geqslant 3$, $s \geqslant 4$ и $n \geqslant sk + 1$ справедливо

Обратимся теперь к слабому насыщению. Пусть сперва s = 3. В случае $n = 3k$ выполнено

${\text{wsat}}({\text{KG}}(n,k),{{K}_{3}})$ = ${\text{sat}}({\text{KG}}(n,k),{{K}_{3}})$ = = $\tfrac{1}{3}\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)\left( {\begin{array}{*{20}{c}} {n - k} \\ k \end{array}} \right)$,

так как никакие два треугольника не имеют общего ребра. Для случая $n \geqslant 3k + 2$ нам удалось найти точное значение числа слабого насыщения.

Теорема 4. При всех $k \geqslant 2$ и $n \geqslant 3k + 2$ справедливо равенство

Таким образом, единственным случаем, в котором точное значение числа слабого насыщения не известно, является $n = 3k + 1$. При малых k с помощью линейно–алгебраического метода удалось найти следующие оценки.

Теорема 5. Справедливы оценки

При больших k с помощью вероятностного метода получена следующая нетривиальная оценка сверху. Напомним, что количество ребер в кнезеровском графе равно $\tfrac{1}{2}\left( {\begin{array}{*{20}{c}} {3k + 1} \\ k \end{array}} \right)\left( {\begin{array}{*{20}{c}} {2k + 1} \\ k \end{array}} \right)$.

Теорема 6.

Наконец, при $s \geqslant 4$ и достаточно больших n мы нашли точное значение числа слабого насыщения.

Теорема 7. При $s \geqslant 4$, $n \geqslant (2s - 2)k$ справедливо равенство

Кроме того, верна следующая асимптотическая оценка.

Теорема 8. При $s \geqslant 4$, $n \geqslant sk + 1$ справедливо равенство

В последней теореме имеется в виду, что $n \to \infty $, и при этом k не обязано быть фиксированным – необходимо лишь выполнение неравенства $n \geqslant sk + 1$.