Максимальные индуцированные пути в случайных двудольных графах
Автор: Буитраго Оропеса Х.К.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 3 (63) т.16, 2024 года.
Бесплатный доступ
Доказано, что максимальный размер индуцированного пути в биномиальном двудольном случайном графе G(n,n,p =1/2) сконцентрирован в трех последовательных значениях с вероятностью, стремящейся к 1, при n to infinity.
Двудольный случайный граф, максимальный подграф, концентрация
Короткий адрес: https://sciup.org/142242982
IDR: 142242982
Список литературы Максимальные индуцированные пути в случайных двудольных графах
- Bollobas В., Erdos Р. Cliques in random graphs // Math. Proc. Camb. Phil. Soc. 1976. V. 80. P. 119 127.
- Grimmett G.R., McDiarmid C.J.H. On colouring random graphs // Math. Proc. Cambridge Philos. Soc. 1975. V. 77. P. 313 32 1.
- Matula D.W. The largest clique size in a random graph // Tech. Rep. Dept.Comp. Sci. Southern Methodist University, Dallas, Texas, 1976.
- Matula D. The Employee Party Problem // Notices of the American Mathematical Society. 1972. V. 19, N 2. P. A-382.
- KriveJevich M., Sudakov B., Vu V.H., Wormald N.C. On the probability of independent sets in random graphs // Random Struct. Algorithms. 2003. V. 22(1). P. 111.
- Dutta K., Subramanian C.R. On Induced Paths, Holes and Trees in Random Graphs // Proc. ANAL-CO. 2018. P. 168-177.
- Kamaldinov D., Skorkin A., Zhukovskii M. Maximum sparse induced subgraphs of the binomial random graph with given number of edges // Discrete Appl. Math. 2021. V. 344(2). P. 112205.
- Krivoshapko M., Zhukovskii M. Maximum induced forests in random graphs // Discrete Appl. Math. 2021. V. 305. P. 211-213. EDN: CGAARB
- Bohman T., Hofstad J. Two-Point Concentration of the Independence Number of the Random Graph // Forum of Mathematics, Sigma. 2024. V. 12. P. e24. EDN: WBDOVK
- Buitrago Oropeza J.C. Maximum Induced Trees in Sparse Random Graphs // Dokl. Math. 2024. V. 109. P. 167-169. EDN: LHLCAU
Статья научная
