{
  "id": "2105.12484",
  "version": "v1",
  "published": "2021-05-26T11:35:09.000Z",
  "updated": "2021-05-26T11:35:09.000Z",
  "title": "Powers of paths and cycles in tournaments",
  "authors": [
    "António Girão",
    "Dániel Korándi",
    "Alex Scott"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We show that for every positive integer $k$, any tournament can be partitioned into at most $2^{ck}$ $k$-th powers of paths. This result is tight up to the exponential constant. Moreover, we prove that for every $\\varepsilon>0$ and every integer $k$, any tournament on $n\\ge \\varepsilon^{-Ck}$ vertices which is $\\varepsilon$-far from being transitive contains the $k$-th power of a cycle of length $\\Omega(\\varepsilon n)$; both bounds are tight up to the implied constants.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-05-26T11:35:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "tournament",
      "th power",
      "exponential constant",
      "positive integer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}