Hamiltonicity of expanders: optimal bounds and applications
组织者
本杰明·苏达科夫
演讲者
Nemanja Draganić
时间
2024年05月21日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
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.
演讲者介绍
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.