Publication details

# Cycles of a given length in tournaments

Authors GRZESIK Andrzej LOVASZ Laszlo M VOLEC Jan 2023 Article in Periodical Journal of Combinatorial Theory. Series B https://doi.org/10.1016/j.jctb.2022.07.007 http://dx.doi.org/10.1016/j.jctb.2022.07.007 Tournament; Oriented cycle; Theory of combinatorial limits; Extremal graph theory 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}.