2021/10/13 by Nemanja Draganić, David Munhá Correia, Draganić, Nemanja +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2110.06919
openalex publication_date 2021/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The study of problems concerning subdivisions of graphs has a rich history in extremal combinatorics. Confirming a conjecture of Burr and Erdős, Alon proved in 1994 that subdivided graphs have linear Ramsey numbers. Later, Alon, Krivelevich and Sudakov showed that every n-vertex graph with at least ε n2 edges contains a 1-subdivision of the complete graph on cε√(n) vertices, resolving another old conjecture of Erdős. In this paper we consider the directed analogue of these problems and show that every tournament on at least (2+o(1))k2 vertices contains the 1-subdivision of a transitive tournament on k vertices. This is optimal up to a multiplicative factor of 4 and confirms a conjecture of Girão, Popielarz and Snyder.