Powers of paths and cycles in tournaments

Journal article

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 ε > 0 and every integer k, any tournament on n ≥ ε −Ck vertices which is ε-far from being transitive contains the k-th power of a cycle of length Ω(εn); both bounds are tight up to the implied constants.

Authors: Girão, A; Korándi, D; Scott, A

• Publication status: Accepted
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Journal of Combinatorial Theory
• Publication date: 2021-05-26
• Acceptance date: 2025-06-16
• EISSN: 1096-0899
• ISSN: 0097-3165
• Language: English