Размер максимального подграфа случайного графа с заданным числом рёбер

Обложка

Цитировать

Полный текст

Аннотация

Мы доказали, что максимальный размер k индуцированного подграфа в биномиальном случайном графе G(n, p) с заданным числом рёбер e(k) (при некоторых ограничениях на эту функцию) с вероятностью, стремящейся к 1, принимает одно из двух значений.

Об авторах

Н. М. Деревянко

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

Email: zhukmax@gmail.com
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9

М. Е. Жуковский

"Московский физико-технический институт (национальный исследовательский университет)"; Кавказский математический центр; Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации

Автор, ответственный за переписку.
Email: zhukmax@gmail.com
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9; 385016, Республика Адыгея, г. Майкоп, ул. Первомайская, 208; 119571, г. Москва, пр-кт Вернадского, д. 82

М. Рассиас

Цюрихский университет

Email: zhukmax@gmail.com
Швейцария, 8006, г. Цюрих, Рэмисштрассе, 71

А. Ю. Скоркин

Адыгейский государственный университет

Email: zhukmax@gmail.com
Россия, 385000, г. Майкоп, ул. Университетская 188

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

  1. Bollobás B. Random Graphs. 2nd ed. Cambridge: Cambridge Univ. Press, 2001.
  2. Janson S., Luczak T., Ruciński A. Random Graphs. N.Y.: Wiley, 2000.
  3. Жуковский М.Е., Райгородский А.М. Случайные графы: модели и предельные характеристики // Успехи матем. наук. 2015. T. 70. 1. С. 35-88.
  4. Деревянко Н.М., Киселев С.Г. Числа независимости случайных подграфов некоторого дистанционного графа // Проблемы передачи информации. 2017. Т. 53. № 4. С. 307-318.
  5. Егорова А.Н., Жуковский М.Е. Опровержение закона нуля или единицы для экзистенциальных монадических свойств разреженного биномиального случайного графа // ДАН. 2019. Т. 484. № 5. С. 519-522.
  6. Ostrovsky L.B., Zhukovskii M.E. Monadic Second-Order Properties of Very Sparse Random Graphs // Ann. Pure and Applied Logic. 2017. V. 168. № 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. Grimmett G.R., McDiarmid C.J.H. On colouring random graphs // Math. Proc. Camb. Phil. Soc. 1975. V. 77. № 2. P. 313-324.
  9. Matula D. The Employee Party Problem // Not. Amer. Math. Soc. 1972. V. 19. № 2. P. A-382.
  10. Matula D. The Largest Clique Size in a Random Graph. Tech. Rep. Dept. Comp. Sci., Southern Methodist University, Dallas, Texas; 1976.
  11. 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. № 1. P. 1-14.
  12. Райгородский А.М. Об устойчивости числа независимости случайного подграфа // ДАН. 2017. Т. 477. № 6. С. 649-651.
  13. Fountoulakis N., Kang R.J., McDiarmid C. Largest Sparse Subgraphs of Random Graphs // European J. Combinatorics. 2014. V. 35. P. 232-244.
  14. Bollobás B. The Distribution of the Maximum Degree of a Random Graph // Discrete Mathematics. 1980. V. 32. P. 201-203.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

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