University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Cycles of length three and four in tournaments

Cycles of length three and four in tournaments

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

  • UserJon Noel (University of Warwick)
  • ClockThursday 14 March 2019, 13:00-14:00
  • HouseWatson LTB.

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

Given a tournament with d*(n choose 3) cycles of length three, how many cycles of length four must there be? Linial and Morgenstern (2016) conjectured that the minimum is asymptotically attained by ``blowing up’’ a transitive tournament and orienting the edges randomly within the parts. This is reminiscent of the tight examples for the famous Triangle and Clique Density Theorems of Razborov, Nikiforov and Reiher. We prove the conjecture for d ≥ 1/36 using spectral methods. We also show that the family of tight examples is more complex than expected and fully characterise it for d ≥ 1/16.

Joint work with Timothy Chan, Andrzej Grzesik and Daniel Král’.

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 talks.cam from the University of Cambridge.