Асимптотическая нормальность размера гигантской компоненты в случайном двудольном графе
Автор: Захаров П.А., Шабанов Д.А.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 1 (57) т.15, 2023 года.
Бесплатный доступ
В работе исследуется предельное распределение размера так называемой гигантской компоненты в случайном двудольном графе G(n, n, p) в разреженном случае, когда p = c/n для некоторого фиксированного c > 1. Доказано, что распределение размера гигантской компоненты является асимптотически нормальным.
Случайные графы, компоненты связности, двудольные графы, асимптотическая нормальность
Короткий адрес: https://sciup.org/142238146
IDR: 142238146
Список литературы Асимптотическая нормальность размера гигантской компоненты в случайном двудольном графе
- Erd˝os P., R´enyi A. On the evolution of random graphs // Publication of the Mathematical Institute of the Hungarian Academy of Sciences. 1960. V. 5. P. 17–61.
- Степанов В.Е. О вероятности связности случайного графа 𝒢𝑚(𝑡) // Теория вероятн. и ее примен. 1970. Т. 15, № 1. С. 55–67.
- Bollob´as B., Riordan O. Asymptotic normality of the size of the giant component via a random walk // Journal of Combinatorial Theory, Series B. 2012. V. 102. P. 53–61.
- Aldous D. Brownian excursions, critical random graphs and the multiplicative coalescent // The Annals of Probability. 1997. V. 25. P. 812–854.
- Schmidt-Pruzan J., Shamir E. Component structures in the evolution of random hypergraphs // Combinatorica. 1985. V. 5. P. 81–94.
- Frieze A., Krivelevich M., Martin R. The emergence of a giant component in random subgraphs of pseudo-random graphs // Random Structures and Algorithms. 2004. V. 24. P. 42–50.
- Ajtai M., Koml´os J., Szemer´edi E. Largest random component of a k-cube // Combinatorica. 1982. V. 2. P. 1–7.
- Behrisch M., Coja-Oghlan A., Kang M. The order of the giant component of random hypergraphs // Random Structures and Algorithms. 2010. V. 36. P. 149–184.
- Bollob´as B., Riordan O. Asymptotic Normality of the Size of the Giant Component in a Random Hypergraph // Random Structures and Algorithms. 2012. V. 41. P. 441–450.
- Johansson T. The giant component of the randombipartite graph // Master thesis in Engineering and Computational Science. 2012.
- Do T.A., Erde J., Kang M. Component behaviour and excess of random bipartite graphs near the critical point // arXiv.2105.14883. 2021.
Статья научная
