Малые подграфы и расширения в семействе случайных подграфов плотных дистанционных графов
Автор: Буркин А.В.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 1 (41) т.11, 2019 года.
Бесплатный доступ
В предыдущих работах были получены результаты, касающиеся распределения малых подграфов и расширений в случайном симметричном дистанционном графе. В настоящей статье мы обобщаем эти утверждения на более широкий класс случайных дистанционных графов.
Дистанционные графы, случайные графы, малые подграфы, свойства расширений
Короткий адрес: https://sciup.org/142220473
IDR: 142220473
Список литературы Малые подграфы и расширения в семействе случайных подграфов плотных дистанционных графов
- Erd˝os P., R´enyi A. On random graphs. I//Publ. Math. Debrecen. 1959. V. 6. P. 290-297.
- Erd˝os P., R´enyi A. On the evolution of random graphs//Magyar Tud. Akad. Mat. Kutat´o Int. K¨ozl. 1960. V. 5. P. 17-61.
- Bollob´as B. Random graphs. Second edition. Cambridge: Cambridge University Press, 2001. V. 73 of Cambridge Studies in Advanced Mathematics. P. xviii+498.
- Janson S., L uczak T., Rucinski A. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: Wiley-Interscience, 2000. P. xii+333.
- Райгородский А.М. Модели случайных графов. Москва: МЦНМО, 2011. 136 c.
- Колчин В.Ф. Случайные графы. Теория вероятностей и математическая статистика. Москва: Физматлит, 2000.
- Алон Н., Спенсер Дж. Вероятностный метод. Москва: БИНОМ, 2007.
- Bollob´as B. Threshold functions for small subgraphs//Math. Proc. Cambridge Philos. Soc. 1981. V. 90, N 2. P. 197-206.
- Rucin´ski A., Vince A. Balanced graphs and the problem of subgraphs of random graphs//Proceedings of the sixteenth Southeastern international conference on combinatorics, graph theory and computing. 1985. V. 49. P. 181-190.
- Буркин А.В., Жуковский M.Е. Малые подграфы и их расширения в случайном дистанционном графе//Матем. сборник. 2018. Т. 209, № 2. С. 22-46.
- Spencer J. Threshold functions for extension statements//J. Combin. Theory Ser. A. 1990. V. 53, N 2. P. 286-305.
- Райгородский А.М. Проблема Борсука и хроматические числа некоторых метрических пространств//УМН. 2001. Т. 56, № 1. С. 107-146.
- Райгородский А.М. Проблема Эрдеша-Хадвигера и хроматические числа конечных геометрических графов//Матем. сборник. 2005. Т. 196, № 1. С. 123-156.
- Райгородский А.М. Линейно-алгебраический метод в комбинаторике. Москва: МЦНМО, 2007.
- Raigorodskii A.M. Around borsuk’s conjecture//J. of Math. Sci. 2008. V. 154, N 4. P. 604-623.
- Raigorodskii A.M. On the chromatic numbers of spheres in Rn//Combinatorica. 2012. V. 32, N 1. P. 111-123.
Статья научная
