- Код статьи
- 10.31857/S2686954324020133-1
- DOI
- 10.31857/S2686954324020133
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 516 / Номер выпуска 1
- Страницы
- 83-86
- Аннотация
- Мы доказали, что для любого и , максимальный размер индуцированного дерева в биномиальном случайном графе сконцентрирован в двух последовательных значениях с вероятностью, стремящейся к 1, при .
- Ключевые слова
- биномиальный случайный граф максимальный подграф концентрация
- Дата публикации
- 15.10.2024
- Год выхода
- 2024
- Всего подписок
- 0
- Всего просмотров
- 40
Библиография
- 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.
