Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, March 16, 2023, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: David Munha Canas Correia

Hamilton cycles in pseudorandom graphs

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:   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