On the number of 8-cycles for two particular regular tournaments of order N with diametrically opposite local properties

Sergey Savchenko

paper

On the number of 8-cycles for two particular regular tournaments of order N with diametrically opposite local properties

arXiv:2403.07629

Abstract

For a regular tournament $T$ of order $n,$ denote by $c_{8} (T)$ the number of cycles of length $8$ in $T .$ Let $D R_{n}$ be a doubly-regular tournament of order $n \equiv 3 mod 4$ (so, the out-sets and in-sets of its vertices are also regular and hence, contain the maximum possible number of cyclic triples) and $R L T_{n}$ be the unique regular locally transitive tournament of (odd) order $n$ (so, the out-sets and in-sets of its vertices are transitive and hence, contain no cyclic triples, at all). Some arguments based on the spectral properties of tournaments allow us to suggest that $c_{8} (T) \leq c_{8} (R L T_{n}),$ where $n$ is sufficiently large. This restriction on $n$ is essential because our computer processing of B. McKay's file of tournaments implies that for $n = 9, 11, 13,$ the maximum of $c_{8} (T)$ is attained at tournaments with regular structure of the out and in-sets of their vertices. In the present paper, we show that $c_{8} (D R_{n})$ does not depend on a particular choice of $D R_{n}$ and determine expressions for $c_{8} (D R_{n})$ and $c_{8} (R L T_{n}) .$ They are both polynomials of degree $8$ in $n .$ Comparing $c_{8} (D R_{n})$ with $c_{8} (R L T_{n})$ yields the inequality $c_{8} (D R_{n}) > c_{8} (R L T_{n})$ for $11 \leq n \leq 35,$ while $c_{8} (R L T_{n}) > c_{8} (D R_{n})$ for $n \geq 39.$ This allows us to treat the value $n = 39$ as the point of phase transition in the local properties of maximizers and minimizers of $c_{8} (T)$ in the class of regular tournaments of order $n .$