Tight bounds for powers of Hamilton cycles in tournaments.

A basic result in graph theory says that any n -vertex tournament with in- and out-degrees larger than 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 ε > 0 , and sufficiently large n , all tournaments with degrees at least n 4 + ε 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 n 4 + c n 1 − 1 / ⌈ k / 2 ⌉ 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 needs 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 / ⌈ (k − 1) / 2 ⌉ , 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 are tournaments with degrees n 4 + Ω (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 = ε − Θ (k) , which is best possible. [ABSTRACT FROM AUTHOR]