The reviewed record of science sign in
Pith

arxiv: 2011.14142 · v1 · pith:FINFVDUV · submitted 2020-11-28 · math.CO

Minimizing cycles in tournaments and normalized q-norms

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:FINFVDUVrecord.jsonopen to challenge →

classification math.CO
keywords cyclestournamentsnumbergivenintegersminimizingproblemasymptotically
0
0 comments X
read the original abstract

Akin to the Erd\H{o}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\'al' 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 family of extremal examples for $4$-cycles. 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 any 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 conclude by proposing two conjectures on the minimization problem for general cycles in tournaments.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.