Repository logo
 

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

Published version
Peer-reviewed

Change log

Authors

Krivelevich, Michael 
Kronenberg, Gal 
Mond, Adva 

Abstract

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>

Description

Keywords

4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences

Journal Title

Journal of the London Mathematical Society

Conference Name

Journal ISSN

0024-6107
1469-7750

Volume Title

Publisher

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