UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

The oriented size Ramsey number of directed paths

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. Green open access

[img]
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}).

Type: Article
Title: The oriented size Ramsey number of directed paths
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.ejc.2020.103103
Publisher version: https://doi.org/10.1016/j.ejc.2020.103103
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10107265
Downloads since deposit
2Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item