2017/12/06 by Letzter, Shoham, Sudakov, Benny
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1712.02403
An oriented graph is a directed graph with no bi-directed edges, i.e. if xy is an edge then yx 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(Pn) = Ω(n2 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(Pn). We also discuss how our methods can be used to improve the best known lower bound of the k-colour version of r(Pn).