Letzter, S; Sudakov, B; (2020) The oriented size Ramsey number of directed paths. European Journal of Combinatorics , 88 , Article 103103. 10.1016/j.ejc.2020.103103.

Preview

Text size-ramsey-dipaths.pdf - Accepted Version Download (234kB) | Preview

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 \vec{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 \vec{r}(\vec{P}_{n}) = \Omega (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 \vec{r}(\vec{P}_{n}). We also discuss how our methods can be used to improve the best known lower bound of the k-colour version of \vec{r}(\vec{P}_{n}).

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item