- Код статьи
- 10.31857/S2686954324020041-1
- DOI
- 10.31857/S2686954324020041
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 516 / Номер выпуска 1
- Страницы
- 21-25
- Аннотация
- Доказана концентрация в интервале размера размера максимального индуцированного леса (ограниченной и неограниченной степени) в при для произвольного заданного . Доказана двухточечная концентрация размера максимального индуцированного леса (а также дерева) ограниченной степени в биномиальном случайном графе Эрдёша–Реньи при .
- Ключевые слова
- случайный граф граф Эрдёша–Реньи индуцированный подграф дерево лес
- Дата публикации
- 15.10.2024
- Год выхода
- 2024
- Всего подписок
- 0
- Всего просмотров
- 44
Библиография
- 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.
