The oriented size Ramsey number of directed paths. (August 2020)

• Record Type: Journal Article
• Authors: Letzter, Shoham; Sudakov, Benny
• Is Part Of: European journal of combinatorics. Volume 88(2020)
• Publication Date: 2020-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103103
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: An oriented graph is a directed graph with no bi-directed edges, i.e. if x y is an edge then y x is not an edge. The oriented size Ramsey number of an oriented graph H, denoted by r ⃗ ( H ), is the minimum m for which there exists an oriented graph G with m edges, such that every 2-colouring of G contains a monochromatic copy of H . In this paper we prove that the oriented size Ramsey number of the directed paths on n vertices satisfies r ⃗ ( P n ⃗ ) = Ω ( n 2 log n ) . This improves a lower bound by Ben-Eliezer, Krivelevich and Sudakov. It also matches an upper bound by Bucić and the authors, thus establishing an asymptotically tight bound on r ⃗ ( P n ⃗ ) . We also discuss how our methods can be used to improve the best known lower bound of the k -colour version of r ⃗ ( P n ⃗ ) .