Extremal problems of long cycles in random graphs

Add to your list(s) Download to your calendar using vCal

• Gal Kronenberg (University of Oxford)
• Thursday 13 February 2020, 15:00-16:00
• Watson LTC.

If you have a question about this talk, please contact Richard Montgomery.

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

For a graph G on n vertices and a graph H, denote by ex(G,H) the maximal number of edges in an H-free subgraph of G. We consider a random graph G~G(n,p) where p>C/n, and determine the asymptotic value of ex(G,C_t), for every A*log(n)< t< (1- Ɛ)n. The 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.

Using similar techniques, 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 (a nearly ’’Woodall graph”). If time permits, we will present some connections to size-Ramsey numbers of long cycles.

Based on joint works with Michael Krivelevich and Adva Mond.

This talk is part of the Combinatorics and Probability Seminar series.

This talk is included in these lists:

• Combinatorics and Probability Seminar
• School of Mathematics Events
• Watson LTC

Note that ex-directory lists are not shown.