2023/05/10 by Girão, António, Hancock, Robert
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2305.06204
Recently, Draganić, Munhá Correia, Sudakov and Yuster showed that every tournament on (2+o(1))k2 vertices contains a 1-subdivision of a transitive tournament on k vertices, which is tight up to a constant factor. We prove a counterpart of their result for immersions. Let f(k) be the smallest integer such that any tournament on at least f(k) vertices must contain a 1-immersion of a transitive tournament on k vertices. We show that f(k)=O(k), which is clearly tight up to a multiplicative factor. If one insists in finding an immersion of a complete directed graph on k vertices then an extra condition on the tournament is necessary. Indeed, we show that every tournament with minimum out-degree at least Ck must contain a 2-immersion of a complete digraph on k vertices. This is again tight up to the value of C and tight on the order of the paths in the immersion.