Department of
Applied
Mathematics

On Hamilton cycles in highly symmetric graphs

Torsten Mütze

Abstract

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 various families of highly symmetric graphs. The starting point is the well-known middle levels conjecture, raised by Ivan Havel from Prague in the 1980s, 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 sketch the developments that lead to the solution of the conjecture and to our recent short proof for it. I will also mention several far-ranging generalizations of the conjecture that were proved subsequently, including the Hamiltonicity of bipartite Kneser graphs and sparse Kneser graphs. Moreover, I will address the algorithmic aspect of the problem, i.e., how to 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.

This talk is based on several papers that are joint work with Petr Gregor, Jerri Nummenpalo, Christoph Standke, Pascal Su, Veit Wiechert and Bartosz Walczak.