- PII
- S2686954325030112-1
- DOI
- 10.31857/S2686954325030112
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume 523 / Issue number 1
- Pages
- 66-70
- Abstract
- Presented by Academician of the RAS V. V. Kozlov. An improvement of Riordan’s result on the threshold probability of the occurrence of a spanning subgraph in a random graph is obtained for some classes of subgraphs, which, in particular, implies an improved bound for the maximum power of a Hamiltonian cycle in a random graph. Moreover, the exact asymptotics of the threshold probability for the occurrence of spanning subgraphs from a wide class of k-degenerate graphs is found.
- Keywords
- случайный граф остовный подграф гамильтонов цикл k-вырожденный граф
- Date of publication
- 24.04.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 12
References
- 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.
