Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 495, № 1, стр. 31-33
МИНИМАЛЬНЫЕ ПОДГРАФЫ БЕЗ КЛИК В КНЕЗЕРОВСКОМ ГРАФЕ
С. В. Вахрушев 1, М. Е. Жуковский 1, 2, 3, 4, *, С. Г. Киселев 1, А. Ю. Скоркин 3
1 Московский физико-технический институт (национальный исследовательский университет)
Долгопрудный, Московская обл., Россия
2 Институт математики им С.Л. Соболева
Сибирского отделения Российской академии наук
Омск, Россия
3 Адыгейский государственный университет,
Кавказский математический центр
Майкоп, Республика Адыгея, Россия
4 Российская академия народного хозяйства
и государственной службы при Президенте
Российской Федерации
Москва, Россия
* E-mail: zhukmax@gmail.com
Поступила в редакцию 06.07.2020
После доработки 06.07.2020
Принята к публикации 17.09.2020
Аннотация
Получены оценки числа насыщения и числа слабого насыщения в кнезеровском графе с полными шаблонами.
Пусть $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$ справедливо
В дальнейших работах о насыщении рассматривались другие графы 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$.
Список литературы
Erdős P., Hajnal A., Moon J.W. A problem in graph theory // The American Mathematical Monthly. 1964. V. 71. P. 1107–1110.
Bollobás B. Weakly k-saturated graphs // Beitrage zur Graphentheorie (Kolloquium, Manebach). 1967. P. 25–31.
Lovász L. Flats in matroids and geometric graphs // Combinatorial Surveys (Proc. 6th British Comb. Conf.). Academic Press. 1977. P. 45–86.
Cui Y., Pu L. Weak saturation numbers of K2,t and ${{K}_{p}} \cup {{K}_{q}}$ // AKCE International Journal of Graphs and Combinatorics. 2019. V. 16. № 3. P. 237–240.
Gun W., Korándi D., Sudakov B. Ks,t-saturated bipartite graphs // European J. of Combinatorics. 2015. V. 45. P. 12–20.
Moshkovitz G., Shapira A. Exact bounds for some hypergraph saturation problems // J. combinatorial theory B. 2015. V. 111. P. 242–248.
Korándi D., Sudakov B. Saturation in random graphs // Random structures and algorithms. 2017. V. 51. № 1. P. 169–181.
Mohammadian A., Tayfeh-Rezaie B. Star saturation number of random graphs // Discrete Math. 2018. V. 341. P. 1166–1170.
Kronenberg G., Martins T., Morrison N. Weak saturation numbers of complete bipartite graphs in the clique // arxiv2004.01289, 2020.
Дополнительные материалы отсутствуют.
Инструменты
Доклады Российской академии наук. Математика, информатика, процессы управления