A Note on Powers of Paths in Tournaments

2020/10/15 by Nemanja Draganić, Draganić, Nemanja, David Munhá Correia +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.2010.07911

2 pages

arxiv created 2020/10/15 · openalex publication_date 2020/10/15 · arxiv updated 2020/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this note we show that every tournament on n vertices contains the k-th power of a directed path of length n/2^6k+7, which improves upon the recent bound of Scott and Korándi of n/2^2^3k. By doing so, we get an inverse exponential dependence on k, which is best possible as Yuster recently showed an upper bound of kn/2^k/2.

Related

• Powers of paths in tournaments
• A note on long powers of paths in tournaments
• Powers of paths and cycles in tournaments
• Paths of given length in tournaments
• Searching for Maximum Out-Degree Vertices in Tournaments