Back to Search Start Over

Powers of paths in tournaments

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
Publication Year :
2020

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\~ao. 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 $\lceil 2n/3 \rceil-1$, which is best possible.<br />Comment: 6 pages; updated affiliations; accepted at CPC

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2010.05735
Document Type :
Working Paper