- PII
- 10.31857/S2686954324020041-1
- DOI
- 10.31857/S2686954324020041
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume 516 / Issue number 1
- Pages
- 21-25
- Abstract
- 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
- Keywords
- случайный граф граф Эрдёша–Реньи индуцированный подграф дерево лес
- Date of publication
- 15.10.2024
- Year of publication
- 2024
- Number of purchasers
- 0
- Views
- 43
References
- 1. Bollobás B., Erdős P. Cliques in random graphs // Mathematical Proceedings of the Cambridge Philosophical Society. 1976. V. 80. P. 419–427.
- 2. 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.
- 3. Fountoulakis N., Kang R.J., McDiarmid C. Largest sparse subgraphs of random graphs // European Journal of Combinatorics. 2014. V. 35. P. 232–244.
- 4. 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.
- 5. 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.
- 6. Krivoshapko M., Zhukovskii M. Maximum induced forests in random graphs // Discrete Applied Mathematics. 2021. V. 305. P. 211–213.
- 7. Frieze A.M. On the independence number of random graphs // Discrete Mathematics. 1990. V. 81. P. 171–175.
- 8. Fernandez de la Vega W. The largest induced tree in a sparse random graph // Random Structures and Algorithms. 1996. V. 9. P. 93–97.
- 9. 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.
- 10. Draganić N., Glock S., Krivelevich M. The largest hole in sparse random graphs // Random Structures & Algorithms. 2022. V. 61. P. 666–677.
- 11. Janson S., Łuczak T., Ruciński A. Random Graphs. John Wiley & Sons, Inc. 2000.
