Powers of paths and cycles in tournaments

Abstract

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 $\epsilon >0$ and every integer $k$, any tournament on $n\ge {\epsilon }^{-Ck}$ vertices which is $\epsilon$-far from being transitive contains the $k$-th power of a cycle of length $\Omega (\epsilon n)$; both bounds are tight up to the implied constants.

17 pages

References in corpus (1)

• Paths with many shortcuts in tournaments