BIMSA >
Research seminar in Discrete Mathematics
Research seminar in Discrete Mathematics
Hamiltonicity of expanders: optimal bounds and applications
Hamiltonicity of expanders: optimal bounds and applications
Organizer
Benjamin Sudakov
Speaker
Nemanja Draganić
Time
Tuesday, May 21, 2024 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
An $n$-vertex graph $G$ is a $C$-expander if $|N(X)| \ge C|X|$ for every $X \subseteq V(G)$ with $|X| \lt n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices. We show that there is some constant $C > 0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications.
Joint work with R. Montgomery, D. Munhá Correia, A. Pokrovskiy and B. Sudakov.
Speaker Intro
Nemanja Draganić is currently a SNSF postdoctoral fellowship holder at the University of Oxford, working with Peter Keevash. Previously, he obtained his PhD at ETH Zurich under the supervision of Benny Sudakov. His primary research interests are in extremal and probabilistic combinatorics, Ramsey theory and theoretical computer science.