Отправить статью по E-mail Размер максимального подграфа случайного графа с заданным числом рёбер
- Авторы: Деревянко Н.М.1, Жуковский М.Е.1,2,3, Рассиас М.4, Скоркин А.Ю.5
-
Учреждения:
- "Московский физико-технический институт (национальный исследовательский университет)"
- Кавказский математический центр
- Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации
- Цюрихский университет
- Адыгейский государственный университет
- Выпуск: Том 488, № 6 (2019)
- Страницы: 587-589
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/17712
- DOI: https://doi.org/10.31857/S0869-56524886587-589
- ID: 17712
Цитировать
Полный текст
Аннотация
Мы доказали, что максимальный размер 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
Список литературы
- Bollobás B. Random Graphs. 2nd ed. Cambridge: Cambridge Univ. Press, 2001.
- Janson S., Luczak T., Ruciński A. Random Graphs. N.Y.: Wiley, 2000.
- Жуковский М.Е., Райгородский А.М. Случайные графы: модели и предельные характеристики // Успехи матем. наук. 2015. T. 70. 1. С. 35-88.
- Деревянко Н.М., Киселев С.Г. Числа независимости случайных подграфов некоторого дистанционного графа // Проблемы передачи информации. 2017. Т. 53. № 4. С. 307-318.
- Егорова А.Н., Жуковский М.Е. Опровержение закона нуля или единицы для экзистенциальных монадических свойств разреженного биномиального случайного графа // ДАН. 2019. Т. 484. № 5. С. 519-522.
- 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.
- Bollobás B., Erdős P. Cliques in Random Graphs // Math. Proc. Camb. Phil. Soc. 1976. V. 80. P. 419-427.
- Grimmett G.R., McDiarmid C.J.H. On colouring random graphs // Math. Proc. Camb. Phil. Soc. 1975. V. 77. № 2. P. 313-324.
- Matula D. The Employee Party Problem // Not. Amer. Math. Soc. 1972. V. 19. № 2. P. A-382.
- Matula D. The Largest Clique Size in a Random Graph. Tech. Rep. Dept. Comp. Sci., Southern Methodist University, Dallas, Texas; 1976.
- 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.
- Райгородский А.М. Об устойчивости числа независимости случайного подграфа // ДАН. 2017. Т. 477. № 6. С. 649-651.
- Fountoulakis N., Kang R.J., McDiarmid C. Largest Sparse Subgraphs of Random Graphs // European J. Combinatorics. 2014. V. 35. P. 232-244.
- Bollobás B. The Distribution of the Maximum Degree of a Random Graph // Discrete Mathematics. 1980. V. 32. P. 201-203.
Дополнительные файлы
