Maximum induced trees in sparse random graphs

Cover Page

Cite item

Full Text

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

Abstract

We prove that a.a.s. for any ε > 0 and n−e−23e−2+ε≤p=o(1) the maximum size of an induced subtree of the binomial random graph Gn,p is concentrated in 2 consecutive points.

About the authors

J. C. Buitrago Oropeza

Moscow Institute of Physics and Technology (National Research University)

Author for correspondence.
Email: buitrago.okh@phystech.edu

Department of Discrete Mathematics, Advanced Combinatorics and Network Applications Laboratory

Russian Federation, Dolgoprudny, Moscow region

References

  1. Bollobás B. Random Graphs. 2nd ed. Cambridge University Press, 2001.
  2. Janson S., Luczak T., Ruciński A. Random Graphs. New York: Wiley, 2000.
  3. Жуковский М.Е., Райгородский А.М. Случайные графы: модели и предельные характеристики // Успехи математических наук. 2015. T. 70. № 1. С. 35–88.
  4. Деревянко Н.М., Киселев С.Г. Числа независимости случайных подграфов некоторого дистанционного графа // Проблемы передачи информации. 2017. Т. 53. № 4. С. 307–318.
  5. Егорова А.Н., Жуковский М.Е. Опровержение закона нуля или единицы для экзистенциальных монадических свойств разреженного биномиального случайного графа // Доклады Академии наук. Т. 99. № 1. С. 68–70.
  6. Ostrovsky L.B., Zhukovskii M.E. Monadic second-order properties of very sparse random graphs // Annals of Pure and Applied Logic. 2017. V. 168. N 11. P. 2087–2101.
  7. Bollobás B., Erdös P. Cliques in random graphs // Math. Proc. Camb. Phil. Soc. 1976. V. 80. P. 419–427.
  8. Matula D. The largest clique size in a random graph // Tech. Rep. Dept. Comp. Sci. Dallas, Texas: Southern Methodist University, 1976.
  9. Krivelevich M., Sudakov B., Vu V.H., Wormald N.C. On the probability of independent sets in random graphs // Random Structures & Algorithms. 2003. V. 22. N 1. P. 1–14.
  10. Fountoulakis N., Kang R.J., McDiarmid C. Largest sparse subgraphs of random graphs // European Journal of Combinatorics. 2014. V. 35. P. 232–244.
  11. Balogh J., Zhukovskii M. On the sizes of large subgraphs of the binomial random graph // Discrete Mathematics. 2022. V. 345. N 2. 112675. ISSN 0012-365X.
  12. 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. N 2. 112205. ISSN 0012-365X.
  13. Krivoshapko M., Zhukovskii M. Maximum induced forests in random graphs // Discrete Applied Mathematics. 2021. V. 305. P. 211–213.
  14. Bohman T., Hofstad J. Two-Point Concentration of the Independence Number of the Random Graph // 2022. arXiv:2208.00117.
  15. Moon J.W. Counting Labelled Trees. Canadian Mathematical Monograph. 1970.
  16. Bohman T., Warnke L., Zhu E. Two-point concentration of the domination number of random graphs // 2024. arXiv:2401.10486.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences