Publication details

Cycles of a given length in tournaments

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.

More info