BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Extremal problems concerning cycles in tournaments Kral, Daniel


The conjecture of Linial and Morgenstern asserts that, among all tournaments with a given density $d$ of cycles of length three, the density of cycles of length four is minimized by a random blow-up of a transitive tournament with all but one parts of equal sizes, i.e., a tournament with the structure similar to graphs appearing in the Erdos-Rademacher problem on triangles in graphs with a given edge density. We prove this conjecture for $d\geq 1/36$ using methods from spectral graph theory, and demonstrate that the structure of extremal examples is more complex than expected and give its full description for $d\geq 1/16$. At the end of the talk, we will discuss the maximum number of cycles of a given length in a tournament and report on some recent results that we have obtained. The talk is based on results joint with Timothy Chan, Andrzej Grzesik, Laszlo Miklos Lovasz, Jonathan Noel and Jan Volec.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International