-

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.