WEAKLY SSATURATED SUBGRAPHS OF RANDOM GRAPHS

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

In this paper, we study weak saturation numbers of binomial random graphs. We proved stability of the weak saturation for several pattern graphs, and proved asymptotic stability for all pattern graphs.

Негізгі сөздер

Авторлар туралы

O. Kalinichenko

Moscow Institute of Physics and Technology, Laboratory of Combinatorial and Geometric Structures

Хат алмасуға жауапты Автор.
Email: s15b1_kalinichenko@179.ru
Russia, Moscow

B. Tayfeh-Rezaie

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

Хат алмасуға жауапты Автор.
Email: tayfeh-r@ipm.ir
Iran, Tehran

M. Zhukovskii

Moscow Institute of Physics and Technology, Laboratory of Combinatorial and Geometric Structures

Хат алмасуға жауапты Автор.
Email: zhukmax@gmail.com
Russia, Moscow

Әдебиет тізімі

  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