Tight bound for powers of Hamilton cycles in tournaments

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ás and Häggkvist significantly extended this by showing that for any fixed $k$ and $\epsilon >0$, and sufficiently large $n$, all tournaments with degrees at least $\frac{n}{4}+\epsilon n$ contain the $k$-th power of a Hamilton cycle. Up until now, there has not been any progress on determining a more accurate error term in the degree condition, neither in understanding how large $n$ should be in the Bollobás-Häggkvist theorem. We essentially resolve both of these questions. First, we show that if the degrees are at least $\frac{n}{4}+c{n}^{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án 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}+\hat{I}\text{c◯}(n^{1/5})$ and no cube of a Hamilton cycle. In addition, our results imply that the Bollobás-Häggkvist theorem already holds for $n={\epsilon }^{-\hat{I}˜(k)}$, which is best possible.