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\binom{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\geq 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\mod 4\), there exists some constant \(c_\ell>0\) such that if \(d\geq 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\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