Hamiltonicity ofexpanders: optimal bounds and applications | Research seminar in Discrete Mathematics

Time：2024-05-21 Tue 17:05-18:15

Venue：Zoom: 787 662 9899 BIMSA

Organizer：Benjamin Sudakov

Speaker：Nemanja Draganic Universty of Oxford

Abstract

An n-vertex graph G is a C-expander if |N(X)>CX for everyXCV(G) withX<n/2C and there is an edge between every two disjoint sets of at least n/2C' vertices. Weshow that there is some constant C'> 0 for which every C-expander is Hamiltonian. in particularthis implies the well known coniecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in(n, d, `)-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, andhas 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 Oxfordworking with Peter Keevash. Previously, he obtained his PhD at ETH Zurich under the supervisionof Benny Sudakov. His primary research interests are in extremal and probabilistic combinatoricsRamsey theory and theoretical computer science.

DATEMay 20, 2024

Related News

0
On rainbow threshold | Research seminar in Discrete Mathematics
AbstractSolving a problem of Bell, Frieze and Marbach, we extend the recent breakthrough of Frankston,Kahn, Narayanan and Park to the rainbow setting.Speaker IntroJie Han is a professor at the School of Mathematics and Statistics of Beijing Institute ofTechnology. He obtained his Ph.D. degree in 2015 at Georgia State University under thesupervision of Prof. Yi Zhao. He then spent his academic l...
1
Uniform Turn density of hypergraphs | Research seminar in Discrete Mathematics
AbstractIn the early 1980s, Erdos and Ss, initiated the study of the classical Turn problem with auniformity condition: the uniform Turn density of a hypergraph H is the infimum over all d for whichany sufficiently large hypergraph with the property that all its linear-size subhypergraphs havedensity at least d contains H. In particular, they raised the questions of determining the uniformTurn ...