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, which is best possible up to a factor of $8$. This may be viewed as a directed analogue of a theorem proved by Bollobás and Thomason, and independently by Komlós and Szemerédi, 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\left(k^2{\log }^{3}k\right)$ which is best possible up to the logarithmic factors.

14 pages