Induced forests and trees in Erdös–Rényi random graph

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

We prove concentration in the interval of size o 1/p for the size of the maximum induced forest (of bounded and unbounded degree) in Gn, p forCε / n < p < 1 ε for arbitrary fixed ε > 0. We also show 2-point concentration of the size of the maximum induced forest (and tree) of bounded degree in the binomial random graph Gn, p for p = const

作者简介

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

参考

  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.

补充文件

附件文件
动作
1. JATS XML

版权所有 © Russian Academy of Sciences, 2024