Слабо насыщенные подграфы случайного графа

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

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

Об авторах

О. И. Калиниченко

Московский физико-технический институт (Национальный исследовательский университет), лаборатория комбинаторных и геометрических структур

Автор, ответственный за переписку.
Email: s15b1_kalinichenko@179.ru
Россия, Москва

Б. Тайфе-Реза

School of Mathematics, Institute for Research
in Fundamental Sciences (IPM)

Автор, ответственный за переписку.
Email: tayfeh-r@ipm.ir
Iran, Tehran

М. Е. Жуковский

Московский физико-технический институт (Национальный исследовательский университет), лаборатория комбинаторных и геометрических структур

Автор, ответственный за переписку.
Email: zhukmax@gmail.com
Россия, Москва

Список литературы

  1. Alon N. An extremal problem for sets with applications to graph theory // J. Combin. Theory Ser. A. 1985. V. 40. № 1. P. 82–89.
  2. Bidgoli M.R., Mohammadian A., Tayfeh-Rezaie B., Zhukovskii M. Threshold for weak saturation stability // arXiv:2006.06855. 2020.
  3. Bollobás B. Weakly k-saturated graphs // Beiträge zur Graphen–theorie. 1968. P. 25–31.
  4. Kalai G. Hyperconnectivity of graphs // Graphs Combin. 1985 V. 1. P. 65–79.
  5. Kalinichenko O., Zhukovskii M. Weak saturation stability // arXiv:2107.11138. 2022.
  6. Korándi D., Sudakov B. Saturation in random graphs // Random Structures Algorithms. 2017. V. 51. № 1. P. 169–181.
  7. Krivelevich M., Patkós B. Equitable coloring of random graphs // Random Structures Algorithms. 2009. V. 35. № 1. P. 83–99.
  8. Kronenberg, G., Martins T., Morrison N. Weak saturation numbers of complete bipartite graphs in the clique // J. Combin. Theory Ser. A. 2021. V. 178. 105357.
  9. Lovász, L. Flats in matroids and geometric graphs // Combinatorial Surveys. 1977. P. 45–86.
  10. Spencer J. Threshold Functions for Extension Statements // J. Combin. Theory Ser. A. 1990. V. 53. P. 286–305.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© О.И. Калиниченко, Б. Тайфе-Реза, М.Е. Жуковский, 2023