Ramsey number of 1-subdivisions of transitive tournaments

DOI10.1016/J.JCTB.2022.06.001MaRDI QIDQ2171017zbMATH OpenOpenAlexFDO

Authors Nemanja Draganić, David Munhá Correia, Raphael Yuster, Benny Sudakov

Publication date 23 September 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.06919

zbMATH Keywords

Ramsey numberssubdivisionstournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: The study of problems concerning subdivisions of graphs has a rich history in extremal combinatorics. Confirming a conjecture of Burr and ErdH{o}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 $varepsilon{n}^2$ edges contains a $1$-subdivision of the complete graph on $c_{varepsilon}sqrtn$ vertices, resolving another old conjecture of ErdH{o}s. In this paper we consider the directed analogue of these problems and show that every tournament on at least $(2+o(1))k^2$ 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~ao, Popielarz and Snyder.

Recommendations

• On 1-subdivisions of transitive tournaments
• Subdivisions of transitive tournaments
• Subdivisions of digraphs in tournaments
• Subdivided graphs have linear ramsey numbers
• On topological tournaments of order 4 in digraphs of outdegree 3

Cites work

• Density theorems for bipartite graphs and related Ramsey-type results
• Doubly regular tournaments are equivalent to skew Hadamard matrices
• scientific article; zbMATH DE number 3715594 (Why is no real title available?)
• scientific article; zbMATH DE number 3494449 (Why is no real title available?)
• Subdivided graphs have linear ramsey numbers
• Subdivisions of digraphs in tournaments
• Subdivisions of transitive tournaments
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions

Cited in

(5)

• On 1-subdivisions of transitive tournaments
• Subdivided graphs have linear ramsey numbers
• A note between transitive C₄-factor and oriented Ramsey number
• Ordered Ramsey numbers of graphs with m edges
• Immersions of directed graphs in tournaments

This page was built for publication: Ramsey number of 1-subdivisions of transitive tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2171017)