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

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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

About the authors

M. B. Akhmejanova

King Abdullah University of Science and Technology

Author for correspondence.
Email: margarita.akhmejanova@kaust.edu.sa
Saudi Arabia, KAUST

V. S. Kozhevnikov

Moscow Institute of Physics and Technology (National Research University)

Email: vladislavkozhevnikov@gmail.com
Russian Federation, Moscow

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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences