Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

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

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