Maximum induced trees in sparse random graphs

Мұқаба

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

Толық мәтін

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

Аннотация

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.

Негізгі сөздер

Толық мәтін

Рұқсат жабық

Авторлар туралы

J. Buitrago Oropeza

Moscow Institute of Physics and Technology (National Research University)

Хат алмасуға жауапты Автор.
Email: buitrago.okh@phystech.edu

Department of Discrete Mathematics, Advanced Combinatorics and Network Applications Laboratory

Ресей, Dolgoprudny, Moscow region

Әдебиет тізімі

  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.

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу

© Russian Academy of Sciences, 2024