2021/03/18 by Draganić, Nemanja, Correia, David Munhá, Sudakov, Benny · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2103.10414
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) + cn1-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 n1-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 (n)/(4)+Ω(n1/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.