Cycles of a given length in tournaments

• DOI: 10.1016/j.jctb.2022.07.007
• Publication Date: 2022-08-04T11:51:09Z
• Authors: Andrzej Grzesik; Daniel Král'; László M. Lovász; Jan Volec
• Keywords: FOS: Mathematics; Mathematics - Combinatorics; Combinatorics (math.CO); 0102 computer and information sciences; 0101 mathematics; 01 natural sciences

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/π\right)^{\ell}\le c(\ell)\le 1+\left(2/π+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\}$.<br/>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<br/>