University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Extremal problems of long cycles in random graphs

Extremal problems of long cycles in random graphs

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

  • UserGal Kronenberg (University of Oxford)
  • ClockThursday 13 February 2020, 15:00-16:00
  • HouseWatson 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.