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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International