Powers of paths in tournaments. (23rd November 2021)

• Record Type: Journal Article
• Authors: Draganić, Nemanja; Dross, François; Fox, Jacob; Girão, António; Havet, Frédéric; Korándi, Dániel; Lochet, William; Correia, David Munhá; Scott, Alex; Sudakov, Benny
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 6(2021)
• Page Start: 894
• Page End: 898
• Publication Date: 2021-11-23
• Subjects: 05C35 -- 05C20 -- 05C38; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548321000067
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: In this short note we prove that every tournament contains the k -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when k =2, showing that there is always a square of a directed path of length, which is best possible.