A Note on the Middle Levels Conjecture

Abstract

The middle levels conjecture asserts that there is a Hamiltonian cycle in the middle two levels of $2k+1$-dimensional hypercube. The conjecture is known to be true for $k\le 17$ [I.Shields, B.J.Shields and C.D.Savage, Disc. Math., 309, 5271--5277 (2009)]. In this note, we verify that the conjecture is also true for $k=18$ by constructing a Hamiltonian cycle in the middle two levels of 37-dimensional hypercube with the aid of the computer. We achieve this by introducing a new decomposition technique and an efficient algorithm for ordering the Narayana objects.

10 pages, 7 figures; Note on the results of k=19 is added at the end of the paper

Cited by in corpus (4)

• Bipartite Kneser graphs are Hamiltonian
• Construction of 2-factors in the middle layer of the discrete cube
• Trimming and gluing Gray codes
• A minimum-change version of the Chung-Feller theorem for Dyck paths