Cycles of a given length in tournaments

Abstract

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+2\cdot {\left(2/\pi \right)}^{\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 $\ell \in \{4,8\}$.

One of the programs used to verify the validity of Lemma 17 is available as an ancillary file; its output has also been made available as an ancillary file