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

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

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