An update on the middle levels problem

The middle levels problem is to find a Hamilton cycle in the middle levels, M2k+1, of the Hasse diagram of B2k+1 (the partially-ordered set of subsets of a 2k+1-element set ordered by inclusion). Previously, the best known, from [I. Shields, C.D. Savage, A Hamilton path heuristic with applications to the middle two levels problem, in: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), vol. 140, 1999], was that M2k+1 is Hamiltonian for all positive k through k=15. In this note we announce that M33 and M35 have Hamilton cycles. The result was achieved by an algorithmic improvement that made it possible to find a Hamilton path in a reduced graph (of complementary necklace pairs) having 129,644,790 vertices, using a 64-bit personal computer.