Department of
Applied
Mathematics

Some recent developments on the middle levels conjecture

Torsten Mütze

Abstract

(joint work with Jerri Nummenpalo and Pascal Su)

The so-called middle levels graph has as vertices all bitstrings of length 2n+1 that have either n or n+1 entries equal to 1, and an edge between any two vertices that differ in exactly one bit. The well-known middle levels conjecture asserts that this graph has a Hamilton cycle for every n>=1. This conjecture was raised in the 80's independently by Ivan Havel and Buck/Wiedemann, but has also been attributed to Dejter, Erdős, Trotter and various others. In 2014 the conjecture was proved in full generality, and it was shown that the middle levels graph even has double-exponentially (in n) many different Hamilton cycles, which is best possible. In this talk I will give a high-level overview of the proof, and report on some more recent results towards generalizing the conjecture and turning it into an efficient algorithm.