























We show that for every positive integer $k$, any tournament can be partitioned into at most $2^{ck}$ $k$-th powers of paths. This result is tight up to the exponential constant. Moreover, we prove that for every $\varepsilon>0$ and every integer $k$, any tournament on $n\ge \varepsilon^{-Ck}$ vertices which is $\varepsilon$-far from being transitive contains the $k$-th power of a cycle of length $Ω(\varepsilon n)$; both bounds are tight up to the implied constants.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。