The oriented size Ramsey number of directed paths

Abstract

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) over right arrow (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) over right arrow ((P-n) over right arrow) = Omega(n(2) log n). This improves a lower bound by Ben-Eliezer, Krivelevich and Sudakov. It also matches an upper bound by Bucic and the authors, thus establishing an asymptotically tight bound on (r) over right arrow ((P-n) over right arrow). We also discuss how our methods can be used to improve the best known lower bound of the k-colour version of (r) over right arrow ((P-n) over right arrow). (C) 2020 Elsevier Ltd. All rights reserved.