A note on long powers of paths in tournaments

Abstract

A square of a path on $k$ vertices is a directed path $x_1\dots x_k$, where $x_i$ is directed to $x_{i+2}$, for every $i\in \{1,\dots ,k-1\}$. Recently, Yuster showed that any tournament on $n$ vertices contains a square of a path of length at least $n^{0.295}$. In this short note, we improve this bound. More precisely, we show that for every $\epsilon >0$, there exists $c_{\epsilon }>0$ such that any tournament on $n$ vertices contains a square of a path on at least $c_{\epsilon }{n}^{1-\epsilon }$ vertices.

5 pages