## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, April 08, 2021, 12:15 pm

Duration: 30 minutes

Location: Zoom: conference room

Speaker: David Munha Canas Correia

## 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. 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ás-Häggkvist theorem. We essentially resolve both questions. First, 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. Indeed, we show that for k=3, there exist 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. This is joint work with Nemanja Draganic and Benny Sudakov.

Information for students and suggested topics for student talks