Dr. Torsten Mütze, Dresden

“On Hamilton cycles in highly symmetric graphs”

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 from the 1980s, which asserts that the subgraph of the (2n+1)-dimensional hypercube formed by all bitstrings with Hamming weight 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.