The question whether a graph has a Hamilton cycle or not is one of the oldest and most fundamental graph-theoretic problems, and one of the prototypical NP-complete problems. In this talk I will survey some recent results on Hamilton cycles in certain families of highly symmetric graphs. The starting point is the well-known middle levels conjecture, which asserts that the subgraph of the Boolean lattice of dimension 2n+1 formed by all subsets of size n or n+1 has a Hamilton cycle. I will give a brief outline of the developments and ideas that lead to the solution of the conjecture, and mention several far-ranging generalizations of it that were proved subsequently, as well as some open problems. I will also go into the algorithmic aspect of the problem, i.e., how to actually compute such Hamilton cycles efficiently. The main motivation for this is to come up with fast and memory-efficient algorithms (so-called Gray codes) that generate the corresponding families of combinatorial objects.

My talk is based on joint work with Jerri Nummenpalo, Christoph Standke, Pascal Su and Veit Wiechert