Title: Lehmer’s 1965 Conjecture about Hamiltonian Paths in Permutation Graphs

Speaker: Tom Verhoeff

Abstract:

Consider the graph with all permutations of a symbol sequence as vertices, where two permutations are connected by an edge when they differ by an interchange of two distinct adjacent symbols.

In 1965, D.H. Lehmer conjectured that all vertices in this graph can be visited by a Hamiltonian path, which is possibly _imperfect_, in the sense of having _spurs_.  Such a spur visits a vertex twice, with a single vertex in-between.

We prove Lehmer's conjecture for permutations of a binary sequence, and we strengthen the conjecture for general symbol sequences by identifying the _stutter_ permutations as candidate spurs. We also provide new proofs for some known results.