- Код статьи
- S2686954325030112-1
- DOI
- 10.31857/S2686954325030112
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 523 / Номер выпуска 1
- Страницы
- 66-70
- Аннотация
- Представлено академиком РАН В. В. Козловым. Получено улучшение результата Риордана о пороговой вероятности вхождения остовного подграфа в случайный граф для некоторых классов подграфов, что, в частности, позволило улучшить оценку на максимальную степень гамильтонова цикла в случайном графе. Кроме того, найдена асимптотика точной пороговой вероятности для вхождения широкого класса k-вырожденных остовных подграфов в случайный граф.
- Ключевые слова
- случайный граф остовный подграф гамильтонов цикл k-вырожденный граф
- Дата публикации
- 24.04.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 11
Библиография
- 1. Erdos P., Renyi A. On the evolution of random graphs // Magyar Tud. Akad. Mat. Kutato Int. Kozl. 1960. V. 5. P. 17–61.
- 2. Bollobas B., Thomason A.G. Threshold functions // Combinatorica. 1987. V. 7. P. 35–38. https://doi.org/10.1007/BF02579198
- 3. Friedgut E. Sharp thresholds of graph properties, and the k-sat problem // Journal of the american mathematical society. V. 12. № 4. P. 1017–1054.
- 4. Friedgut E. Hunting for sharp thresholds // Random Structures & Algorithms. 2005. V. 26. № 1–2. P. 37–51.
- 5. Park J., Pham H. A proof of the Kahn–Kalai conjecture // J. Amer. Math. Soc. 2024. V. 37. P. 235–243. https://doi.org/10.1090/jams/1028
- 6. Kahn J., Kalai G., Thresholds and Expectation Thresholds. Combinatorics, Probability and Computing. 2007. V. 16. № 3. P. 495–502. https://doi.org/10.1017/S0963548307008474
- 7. Riordan O. Spanning subgraphs of random graphs // Combinatorics, Probability & Computing. 2000. V. 9. P. 125–148.
- 8. Komlos J., Szemeredi E. Hamilton cycles in random graphs, In: A. Hajnal, R. Rado, V. T. Sos, eds., Infinite and Finite Sets, Colloq. Math. Soc. Janos Bolyai 10 (North-Holland, Amsterdam), 1973.
- 9. Posa L., Hamiltonian circuits in random graphs // Discrete Mathematics. 1976. V. 14. P. 359–364.
- 10. Kuhn D., Osthus D. On Posa’s conjecture for random graphs // SIAM Journal Discrete Mathematics. 2012. V. 26. P. 1440–1457.
- 11. Nenadov R., Skoric N. Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs // Random Structures Algorithms. 2019. V. 54. P. 187–208.
- 12. Fischer M., Skoric N., Steger A., Trujic M. Triangle resilience of the square of a Hamilton cycle in random graphs // Journal of Combinatorial Theory, Ser. B. 2022. V. 152. P. 171–220.
- 13. Montgomery R. Topics in random graphs, Lecture notes (2018).
- 14. Kahn J., Narayanan B., Park J. The threshold for the square of a Hamilton cycle // Proc. Amer. Math. Soc. 2021. V. 149 P. 3201–3208. https://doi.org/10.1090/proc/15419
- 15. Frankston K.,Kahn J., Narayanan B., Park J. Thresholds versus fractional expectation-thresholds // Annals of Mathematics. 2021. V. 194. № 2. P. 475–495.
