Cycles of a given length in tournaments

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GRZESIK Andrzej KRÁĽ Daniel LOVASZ Laszlo M VOLEC Jan

Year of publication 2023
Type Article in Periodical
Magazine / Source Journal of Combinatorial Theory. Series B
MU Faculty or unit

Faculty of Informatics

Citation
Web https://doi.org/10.1016/j.jctb.2022.07.007
Doi http://dx.doi.org/10.1016/j.jctb.2022.07.007
Keywords Tournament; Oriented cycle; Theory of combinatorial limits; Extremal graph theory
Description We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let c(l) be the limit of the ratio of the maximum number of cycles of length l in an n-vertex tournament and the expected number of cycles of length l in the random n-vertex tournament, when n tends to infinity. It is well-known that c(3) = 1 and c(4) = 4/3. We show that c(l) = 1 if and only if l is not divisible by four, which settles a conjecture of Bartley and Day. If l is divisible by four, we show that 1 + 2 center dot (2/pi)(l) <= c(l) <= 1 + (2/pi+ o(1))(l) and determine the value c(l) exactly for l = 8. We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length l when l is not divisible by four or l is an element of{4, 8}.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.