We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let $c(ell)$ be the limit of the ratio of the maximum number of cycles of length $ell$ in an $n$-vertex tournament and the expected number of cycles of length $ell$ 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(ell)=1$ if and only if $ell$ is not divisible by four, which settles a conjecture of Bartley and Day. If $ell$ is divisible by four, we show that $1+2cdotleft(2/piright)^{ell}le c(ell)le 1+left(2/pi+o(1)right)^{ell}$ and determine the value $c(ell)$ exactly for $ell = 8$. We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length $ell$ when $ell$ is not divisible by four or $ellin{4,8}$.
تحميل البحث