Open access
Date
2022-11Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
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. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000557094Publication status
publishedExternal links
Journal / series
Journal of Combinatorial Theory. Series BVolume
Pages / Article No.
Publisher
Academic PressSubject
Ramsey numbers; Subdivisions; TournamentOrganisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
More
Show all metadata
ETH Bibliography
yes
Altmetrics