Open Collections

Extremal problems concerning cycles in tournaments

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Combinatorics; Probability theory and stochastic processes

video/mp4

Author affiliation: Masaryk University

2020-03-04

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73673

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/