2019/08/10 by Girão, António, Popielarz, Kamil, Snyder, Richard
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1908.03733
We show that for every positive integer k, any tournament with minimum out-degree at least (2+o(1))k2 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 (k2log3 k) which is best possible up to the logarithmic factors.