Abstract
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.
REFERENCES
N. Alon, “An extremal problem for sets with applications to graph theory,” J. Combin. Theory Ser. A 40 (1), 82–89 (1985).
M. R. Bidgoli, A. Mohammadian, B. Tayfeh-Rezaie, and M. Zhukovskii, “Threshold for weak saturation stability,” arXiv:2006.06855 (2020).
B. Bollobás, “Weakly k-saturated graphs,” in Beiträge zur Graphentheorie (Teubner, Leipzig, 1968), pp. 25–31.
G. Kalai, “Hyperconnectivity of graphs,” Graphs Combin. 1, 65–79 (1985).
O. Kalinichenko and M. Zhukovskii, “Weak saturation stability,” arXiv:2107.11138 (2022).
D. Korándi and B. Sudakov, “Saturation in random graphs,” Random Struct. Algorithms 51 (1), 169–181 (2017).
M. Krivelevich and B. Patkós, “Equitable coloring of random graphs,” Random Struct. Algorithms 35 (1), 83–99 (2009).
G. Kronenberg, T. Martins, and N. Morrison, “Weak saturation numbers of complete bipartite graphs in the clique,” J. Combin. Theory Ser. A 178, 105357 (2021).
L. Lovász, “Flats in matroids and geometric graphs,” in Combinatorial Surveys (Academic, New York, 1977), pp. 45–86.
J. Spencer, “Threshold functions for extension statements,” J. Combin. Theory Ser. A 53, 286–305 (1990).
Funding
This work was carried out with the support of the Russian Foundation for Basic Research grant no. 20‑51-56017 and Iran National Science Foundation under project no. 99003814.
Author information
Authors and Affiliations
Corresponding authors
Ethics declarations
The authors declare that they have no conflicts of interest.
Rights and permissions
About this article
Cite this article
Kalinichenko, O., Tayfeh-Rezaie, B. & Zhukovskii, M. Weakly Saturated Subgraphs of Random Graphs. Dokl. Math. 107, 37–39 (2023). https://doi.org/10.1134/S1064562423700448
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1064562423700448