TAU Combinatorics Seminar 2020/21

When: Sunday, November 22, 10am
Speaker: Adva Mond, University of Cambridge
Title: Extremal problems for long cycles in random graphs


In this talk, we consider the random version of some classical extremal problems for long cycles. This type of problems can also be seen as random analogues of Turán numbers for long cycles and for short odd cycles, established by Woodall in 1972.

For graphs $G$ and $H$, denote by $ex(G,H)$ the maximal number of edges in an $H$-free subgraph of $G$. We consider a random graph $G\sim G(n,p)$ where $p\ge \frac{C}{n}$, and determine the asymptotic value of $ex(G,C_t)$, for every $A \log n \le t \le (1-\varepsilon)n$. The typical behaviour of $ex(G,C_t)$ can depend substantially on the parity of $t$. In particular, our results match the classical result of Woodall, and demonstrate the transference principle in the context of long cycles.

If time permits, we will discuss implications for Ramsey-type properties of long cycles in sparse random graphs.

Based on a joint work with Michael Krivelevich and Gal Kronenberg.