ON CERTAIN SPANNING SUBGRAPHS OF RANDOM GRAPHS

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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.

About the authors

O. I Serkova

Moscow Institute of Physics and Technology

Email: kalnichenko.o@phystech.ru
Moscow, Russia

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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Note

In the print version, the article was published under the DOI: 10.31857/S2686954325030112


Copyright (c) 2025 Russian Academy of Sciences

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).