Combinatorial Theory

Akin to the Erdős-Rademacher problem, Linial and Morgenstern made the following conjecture in tournaments: for any $d\in (0,1]$, among all $n$-vertex tournaments with $d(\genfrac{}{}{0ex}{}{n}{3})$ many 3-cycles, the number of 4-cycles is asymptotically minimized by a special random blow-up of a transitive tournament. Recently, Chan, Grzesik, Král' and Noel introduced spectrum analysis of adjacency matrices of tournaments in this study, and confirmed this for $d\ge 1/36$. In this paper, we investigate the analogous problem of minimizing the number of cycles of a given length. We prove that for integers $\ell \not\equiv 2\mathrm{mod}4$, there exists some constant $c_{\ell }>0$ such that if $d\ge 1-c_{\ell }$, then the number of $\ell$-cycles is also asymptotically minimized by the same extremal examples. In doing so, we answer a question of Linial and Morgenstern about minimizing the $q$-norm of a probabilistic vector with given $p$-norm for integers $q>p>1$. For integers $\ell \equiv 2\mathrm{mod}4$, however the same phenomena do not hold for $\ell$-cycles, for which we can construct an explicit family of tournaments containing fewer $\ell$-cycles for any given number of $3$-cycles. We propose two conjectures concerning the minimization problem for general cycles.

Mathematics Subject Classifications: 05C20, 05C35, 05C38

Keywords: Tournaments, cycles, spectrum