Directed Ramsey number for trees

Matija Bucić, Shoham Letzter, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In this paper, we study Ramsey-type problems for directed graphs. We first consider the k-colour oriented Ramsey number of H, denoted by r→(H,k), which is the least n for which every k-edge-coloured tournament on n vertices contains a monochromatic copy of H. We prove that r→(T,k)≤c k |T| k for any oriented tree T. This is a generalisation of a similar result for directed paths by Chvátal and by Gyárfás and Lehel, and answers a question of Yuster. In general, it is tight up to a constant factor. We also consider the k-colour directed Ramsey number r↔(H,k) of H, which is defined as above, but, instead of colouring tournaments, we colour the complete directed graph of order n. Here we show that r↔(T,k)≤c k |T| k−1 for any oriented tree T, which is again tight up to a constant factor, and it generalises a result by Williamson and by Gyárfás and Lehel who determined the 2-colour directed Ramsey number of directed paths.

Original languageEnglish (US)
Pages (from-to)145-177
Number of pages33
JournalJournal of Combinatorial Theory. Series B
Volume137
DOIs
StatePublished - Jul 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Directed graphs
  • Ramsey theory
  • Tournaments
  • Trees

Fingerprint

Dive into the research topics of 'Directed Ramsey number for trees'. Together they form a unique fingerprint.

Cite this