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, March 16, 2023, 12:15 pm

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: David Munha Canas Correia

Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well known conjecture in the area states that any d-regular n-vertex graph G whose second largest eigenvalue in absolute value λ(G) is at most d/C, for some universal constant C>0, has a Hamilton cycle. We obtain two main results which make substantial progress towards this problem. Firstly, we settle this conjecture in full when the degree d is at least a small power of n. Secondly, in the general case we show that λ(G)≤d/C(log n)^{1/3} implies the existence of a Hamilton cycle, improving the 20-year old bound of d/(log n)^{1−o(1)} of Krivelevich and Sudakov. We use in a novel way a variety of methods, such as a robust Pósa rotation-extension technique, the Friedman-Pippenger tree embedding with rollbacks and the absorbing method, combined with additional tools and ideas. Our results have several interesting applications, giving best bounds on the number of generators which guarantee the Hamiltonicity of random Cayley graphs, which is an important partial case of the well known Hamiltonicity conjecture of Lovász. They can also be used to improve a result of Alon and Bourgain on additive patterns in multiplicative subgroups. This is joint work with Stefan Glock and Benny Sudakov.

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

Previous talks by year: 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