Induced forests and trees in Erdös–Rényi random graph
- 作者: Akhmejanova M.B.1, Kozhevnikov V.S.2
-
隶属关系:
- King Abdullah University of Science and Technology
- Moscow Institute of Physics and Technology (National Research University)
- 期: 卷 516, 编号 1 (2024)
- 页面: 21-25
- 栏目: MATHEMATICS
- URL: https://rjeid.com/2686-9543/article/view/647944
- DOI: https://doi.org/10.31857/S2686954324020041
- EDN: https://elibrary.ru/XJAOZE
- ID: 647944
如何引用文章
详细
We prove concentration in the interval of size for the size of the maximum induced forest (of bounded and unbounded degree) in for for arbitrary fixed . We also show 2-point concentration of the size of the maximum induced forest (and tree) of bounded degree in the binomial random graph for
作者简介
M. Akhmejanova
King Abdullah University of Science and Technology
编辑信件的主要联系方式.
Email: margarita.akhmejanova@kaust.edu.sa
沙特阿拉伯, KAUST
V. Kozhevnikov
Moscow Institute of Physics and Technology (National Research University)
Email: vladislavkozhevnikov@gmail.com
俄罗斯联邦, Moscow
参考
- Bollobás B., Erdős P. Cliques in random graphs // Mathematical Proceedings of the Cambridge Philosophical Society. 1976. V. 80. P. 419–427.
- Fountoulakis N., Kang R.J., McDiarmid C. The t-stability number of a random graph // The Electronic Journal of Combinatorics. 2010. V. 17. P. 1–10.
- Fountoulakis N., Kang R.J., McDiarmid C. Largest sparse subgraphs of random graphs // European Journal of Combinatorics. 2014. V. 35. P. 232–244.
- Dutta K., Subramanian C.R. On Induced Paths, Holes and Trees in Random Graphs // 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics. 2018. P. 168–177.
- Kamaldinov D., Skorkin A., Zhukovskii M. Maximum sparse induced subgraphs of the binomial random graph with given number of edges // Discrete Mathematics. 2021. V. 344. P. 112205.
- Krivoshapko M., Zhukovskii M. Maximum induced forests in random graphs // Discrete Applied Mathematics. 2021. V. 305. P. 211–213.
- Frieze A.M. On the independence number of random graphs // Discrete Mathematics. 1990. V. 81. P. 171–175.
- Fernandez de la Vega W. The largest induced tree in a sparse random graph // Random Structures and Algorithms. 1996. V. 9. P. 93–97.
- Cooley O., Draganić N., Kang M., Sudakov B. Large Induced Matchings in Random Graphs // SIAM Journal on Discrete Mathematics. 2021. V. 35. P. 267–280.
- Draganić N., Glock S., Krivelevich M. The largest hole in sparse random graphs // Random Structures & Algorithms. 2022. V. 61. P. 666–677.
- Janson S., Łuczak T., Ruciński A. Random Graphs. John Wiley & Sons, Inc. 2000.
补充文件
