Enviar artigo por via de e-mail ON CERTAIN SPANNING SUBGRAPHS OF RANDOM GRAPHS
- Autores: Serkova O.I1
-
Afiliações:
- Moscow Institute of Physics and Technology
- Edição: Volume 523, Nº 1 (2025)
- Páginas: 66-70
- Seção: MATHEMATICS
- URL: https://bakhtiniada.ru/2686-9543/article/view/305348
- DOI: https://doi.org/10.31857/S2686954325030112
- EDN: https://elibrary.ru/JSXSOX
- ID: 305348
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
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.
Palavras-chave
Sobre autores
O. Serkova
Moscow Institute of Physics and Technology
Email: kalnichenko.o@phystech.ru
Moscow, Russia
Bibliografia
- Erdos P., Renyi A. On the evolution of random graphs // Magyar Tud. Akad. Mat. Kutato Int. Kozl. 1960. V. 5. P. 17–61.
- Bollobas B., Thomason A.G. Threshold functions // Combinatorica. 1987. V. 7. P. 35–38. https://doi.org/10.1007/BF02579198
- Friedgut E. Sharp thresholds of graph properties, and the k-sat problem // Journal of the american mathematical society. V. 12. № 4. P. 1017–1054.
- Friedgut E. Hunting for sharp thresholds // Random Structures & Algorithms. 2005. V. 26. № 1–2. P. 37–51.
- 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
- 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
- Riordan O. Spanning subgraphs of random graphs // Combinatorics, Probability & Computing. 2000. V. 9. P. 125–148.
- 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.
- Posa L., Hamiltonian circuits in random graphs // Discrete Mathematics. 1976. V. 14. P. 359–364.
- Kuhn D., Osthus D. On Posa’s conjecture for random graphs // SIAM Journal Discrete Mathematics. 2012. V. 26. P. 1440–1457.
- 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.
- 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.
- Montgomery R. Topics in random graphs, Lecture notes (2018).
- 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
- Frankston K.,Kahn J., Narayanan B., Park J. Thresholds versus fractional expectation-thresholds // Annals of Mathematics. 2021. V. 194. № 2. P. 475–495.
Arquivos suplementares
