Networks

Hamilton cycles in sparse graphs

 

Summary One of the main goals of extremal combinatorics is to understand sharp conditions under which a combinatorial structure contains some substructure of interest. Finding such conditions for spanning substructures in graphs is a very active area of research and one of the most fundamental such substructures is the Hamilton cycle.

There has been great recent success in solving long-standing problems asking whether dense (directed) graphs with certain conditions contain one or more Hamilton cycles. The Szemerédi Regularity Lemma as well as the recent robust expansion technique have been instrumental in this regard. The goal of this project is to attack long-standing open problems about Hamilton cycles in sparse graphs partly by extending the ideas of robust extension. The problems involve the long-standing conjectures of Chvátal on toughness and Hamiltonicity, and Lovász's conjecture on Hamiltonicity of connected Cayley graphs. In addition we consider the problem of Hamiltonian resilience: given a graph class that is Hamiltonian, how likely is it to remain Hamiltonian under random edge deletion. The final theme is to investigate applications of methods from extremal graph theory to the algorithmic Hamilton cycle problem.
Supervisors Viresh Patel (UvA)
PhD Student Fabian Stroh
Location Universiteit van Amsterdam (UvA)