Subdivisions of digraphs in tournaments

Abstract We show that for every positive integer k, any tournament with minimum out-degree at least ( 2 + o ( 1 ) ) k 2 contains a subdivision of the complete directed graph on k vertices, where each path of the subdivision has length at most 3. This result is best possible on the minimum out-degree condition (up to a multiplicative factor of 8), and it is tight with respect to the length of the paths. It may be viewed as a directed analogue of a theorem proved by Bollobas and Thomason, and independently by Komlos and Szemeredi, concerning subdivisions of cliques in graphs with sufficiently high average degree. We also consider the following problem: given k, what is the smallest positive integer f ( k ) such that any f ( k ) -vertex tournament contains a 1-subdivision of the transitive tournament on k vertices? We show that f ( k ) = O ( k 2 log 3 ⁡ k ) which is best possible up to the logarithmic factors.