Repository logo

Turán‐type problems for long cycles in random and pseudo‐random graphs

Published version

Change log


Krivelevich, Michael 
Kronenberg, Gal 
Mond, Adva 


jats:titleAbstract</jats:title>jats:pWe study the Turán number of long cycles in random and pseudo‐random graphs. Denote by the random variable counting the number of edges in a largest subgraph of without a copy of . We determine the asymptotic value of , where is a cycle of length , for and . The typical behaviour of depends substantially on the parity of . In particular, our results match the classical result of Woodall on the Turán number of long cycles, and can be seen as its random version, showing that the transference principle holds here as well. In fact, our techniques apply in a more general sparse pseudo‐random setting. We also prove a robustness‐type result, showing the likely existence of cycles of prescribed lengths in a random subgraph of a graph with a nearly optimal density. Finally, we also present further applications of our main tool (the Key Lemma) for proving results on Ramsey‐type problems about cycles in sparse random graphs.</jats:p>



4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences

Journal Title

Journal of the London Mathematical Society

Conference Name

Journal ISSN


Volume Title


USA‐Israel BSF (2018267)
Israel Science Foundation (1261/17)