论文标题
最小化锦标赛中的周期，并标准化$ q $ norms
Minimizing cycles in tournaments and normalized $q$-norms
论文作者
论文摘要
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''和Noel在这项研究中对比赛的邻接矩阵进行了频谱分析，并以$ d \ geq 1/36 $确认了这一点。 在本文中，我们研究了最小化给定长度周期数量的类似问题。我们证明，对于整数$ \ ell \ equiv 2 \ mod 4 $，存在一些常数的$ c_ \ ell> 0 $，这样，如果$ d \ geq 1-c_ \ ell $，那么$ \ ell $ cycles的数量也是由$ 4 $ cyccles的极端示例的同一示例的同一家族而不是$ cyccycles的同一家族的。在此过程中，我们回答了一个有关概率向量的$ q $ norm的外线和摩根斯特恩的问题，任何整数$ q> p> p> 1 $。对于整数，$ \ ell \ equiv 2 \ mod 4 $，但是相同的现象不适合$ \ ell $ -cycles，为此，我们可以为任何给定数量的$ 3 $ 3 $ -CYCLE构建一个明确的锦标赛。最后，我们提出了两个关于比赛中一般周期最小化问题的猜想。
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 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.
