Turán‐type problems for long cycles in random and pseudo‐random graphs
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
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
Journal Title
Conference Name
Journal ISSN
1469-7750
Volume Title
Publisher
Publisher DOI
Sponsorship
Israel Science Foundation (1261/17)