{
  "id": "2103.10414",
  "version": "v1",
  "published": "2021-03-18T17:48:53.000Z",
  "updated": "2021-03-18T17:48:53.000Z",
  "title": "Tight bound for powers of Hamilton cycles in tournaments",
  "authors": [
    "Nemanja Draganić",
    "David Munhá Correia",
    "Benny Sudakov"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A basic result in graph theory says that any $n$-vertex tournament with in- and out-degrees larger than $\\frac{n-2}{4}$ contains a Hamilton cycle, and this is tight. In 1990, Bollob\\'{a}s and H\\\"{a}ggkvist significantly extended this by showing that for any fixed $k$ and $\\varepsilon > 0$, and sufficiently large $n$, all tournaments with degrees at least $\\frac{n}{4}+\\varepsilon n$ contain the $k$-th power of a Hamilton cycle. Given this, it is natural to ask for a more accurate error term in the degree condition, and also how large $n$ should be in the Bollob\\'{a}s-H\\\"{a}ggkvist theorem. We essentially resolve both questions. First, we show that if the degrees are at least $\\frac{n}{4} + cn^{1-1/\\lceil k/2 \\rceil}$ for some constant $c = c(k)$, then the tournament contains the $k$-th power of a Hamilton cycle. In particular, in order to guarantee the square of a Hamilton cycle, one only requires a constant additive term. We also present a construction which, modulo a well-known conjecture on Tur\\'an numbers for complete bipartite graphs, shows that the error term must be of order at least $n^{1-1/\\lceil (k-1)/2 \\rceil}$, which matches our upper bound for all even $k$. For odd $k$, we believe that the lower bound can be improved. Indeed, we show that for $k=3$, there exist tournaments with degrees $\\frac{n}{4}+\\Omega(n^{1/5})$ and no cube of a Hamilton cycle. In addition, our results imply that the Bollob\\'{a}s-H\\\"{a}ggkvist theorem already holds for $n = \\varepsilon^{-\\Theta(k)}$, which is best possible.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-18T17:48:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamilton cycle",
      "tight bound",
      "th power",
      "accurate error term",
      "graph theory says"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}