论文标题
关于锦标赛中长途道路的注释
A note on long powers of paths in tournaments
论文作者
论文摘要
$ k $ Vertices上的路径正方形是一个定向路径$ x_1 \ ldots x_k $，其中$ x_i $被指向$ x_ {i+2} $，每$ i \ in \ in \ in \ {1，\ ldots，k-1 \} $。最近，Yuster表明，$ N $顶点上的任何比赛都包含一条长度的正方形，至少$ n^{0.295} $。在此简短的说明中，我们改善了这一界限。更确切地说，我们证明，对于每$ \ varepsilon> 0 $，存在$ c _ {\ varepsilon}> 0 $，以便任何$ n $ dertices上的任何比赛都包含至少$ c _ {\ varepsilon} n^{1- \ varepsilon} $ c _ {1- \ varepsilon} $ Vertices的路径的平方。
A square of a path on $k$ vertices is a directed path $x_1\ldots x_k$, where $x_i$ is directed to $x_{i+2}$, for every $i\in \{1,\ldots, 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 $\varepsilon>0$, there exists $c_{\varepsilon}>0$ such that any tournament on $n$ vertices contains a square of a path on at least $c_{\varepsilon}n^{1-\varepsilon}$ vertices.
