{
  "id": "1708.04504",
  "version": "v1",
  "published": "2017-08-15T14:14:50.000Z",
  "updated": "2017-08-15T14:14:50.000Z",
  "title": "Directed Ramsey number for trees",
  "authors": [
    "Matija Bucic",
    "Shoham Letzter",
    "Benny Sudakov"
  ],
  "comment": "27 pages, 14 figures",
  "categories": [
    "math.CO"
  ],
  "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 $\\overrightarrow{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 $ \\overrightarrow{R}(T,k) \\le c_k|T|^k$ for any oriented tree $T$. This is a generalisation of a similar result for directed paths by Chv\\'atal and by Gy\\'arf\\'as 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 $\\overleftrightarrow{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 $ \\overleftrightarrow{R}(T,k) \\le 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\\'arf\\'as and Lehel who determined the $2$-colour directed Ramsey number of directed paths.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-15T14:14:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "colour directed ramsey number",
      "constant factor",
      "colour oriented ramsey number",
      "oriented tree",
      "directed paths"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}