Максимальные индуцированные деревья в разреженных случайных графах

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Мы доказали, что для любого ε > 0 и n−e−23e−2+ε≤p=o(1), максимальный размер индуцированного дерева в биномиальном случайном графе Gn,p сконцентрирован в двух последовательных значениях с вероятностью, стремящейся к 1, при n → ∞.

Об авторах

Х. К. Буитраго Оропеса

Московский физико-технический институт (национальный исследовательский университет)

Автор, ответственный за переписку.
Email: buitrago.okh@phystech.edu

кафедра дискретной математики, лаборатория продвинутой комбинаторики и сетевых приложений

Россия, Долгопрудный, Московская облаcть

Список литературы

  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
Скачать

© Российская академия наук, 2024