Maximum induced trees in sparse random graphs

封面

如何引用文章

全文:

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

详细

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