Cycles of a given length in tournaments

FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) 0102 computer and information sciences 0101 mathematics 01 natural sciences
DOI: 10.1016/j.jctb.2022.07.007 Publication Date: 2022-08-04T11:51:09Z
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/π\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/>
SUPPLEMENTAL MATERIAL
Coming soon ....
REFERENCES (25)
CITATIONS (2)
EXTERNAL LINKS
PlumX Metrics
RECOMMENDATIONS
FAIR ASSESSMENT
Coming soon ....
JUPYTER LAB
Coming soon ....