2020/10/06 by António Girão, Girão, António
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.2010.02875
5 pages
arxiv created 2020/10/06 · openalex publication_date 2020/10/06 · arxiv updated 2020/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A square of a path on k vertices is a directed path x1… xk, where xi is directed to xi+2, for every i∈ \1,…, k-1\. Recently, Yuster showed that any tournament on n vertices contains a square of a path of length at least n0.295. In this short note, we improve this bound. More precisely, we show that for every ε>0, there exists cε>0 such that any tournament on n vertices contains a square of a path on at least cεn1-ε vertices.