论文标题
锦标赛中给定长度的周期
Cycles of a given length in tournaments
论文作者
论文摘要
我们研究了锦标赛中给定长度的最大循环的最大定向循环的渐近行为：在$ n $ -n $ vertex锦标赛中的最大循环$ \ ell $的最大循环量的比率限制，而$ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n。众所周知，$ c（3）= 1 $和$ c（4）= 4/3 $。我们表明，当$ c（\ ell）= 1 $时，仅当$ \ ell $不被四个$ $ \ ell $排除，这解决了Bartley和Day的猜想。如果$ \ ell $可排四个，我们表明$ 1+2 \ cdot \ left（2/π\右）^{\ ell} \ le c（\ ell）\ le 1+ \ left（2/π+o（1）当$ \ ell $不被四个或$ \ ell \ in \ in \ {4,8 \} $不可用时，我们还提供了最大长度周期$ \ ell $的渐近结构的完整描述。
We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let $c(\ell)$ be the limit of the ratio of the maximum number of cycles of length $\ell$ in an $n$-vertex tournament and the expected number of cycles of length $\ell$ in the random $n$-vertex tournament, when $n$ tends to infinity. It is well-known that $c(3)=1$ and $c(4)=4/3$. We show that $c(\ell)=1$ if and only if $\ell$ is not divisible by four, which settles a conjecture of Bartley and Day. If $\ell$ is divisible by four, we show that $1+2\cdot\left(2/π\right)^{\ell}\le c(\ell)\le 1+\left(2/π+o(1)\right)^{\ell}$ and determine the value $c(\ell)$ exactly for $\ell = 8$. We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length $\ell$ when $\ell$ is not divisible by four or $\ell\in\{4,8\}$.
