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

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login