Tight bounds 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 at least n/4 contains a Hamilton cycle, and this is essentially 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. Given this, it is natural to ask for a more accurate error term in the degree condition. We show that if the degrees are at least $n/4+cn^{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 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/⌈(k−1)/2⌉}$, which matches our upper bound for all even k. For odd k, we believe that the lower bound can be improved and we show that for k=3, there exist tournaments with degrees $n/4+Ω(n^{1/5})$ and no cube of a Hamilton cycle. Additionally we also show that the Bollobás-Häggkvist theorem already holds for $n=ε^{−Θ(k)}$, which is best possible. This is joint work with Nemanja Draganic and Benny Sudakov.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).