An update on the middle levels problem

الأصل · EN

The middle levels problem is to find a Hamilton cycle in the middle levels, M₂ₖ₊₁, of the Hasse diagram of B₂ₖ₊₁ (the partially ordered set of subsets of a 2k+1-element set ordered by inclusion). Previously, the best result was that M₂ₖ₊₁ is Hamiltonian for all positive k through k=15. In this note we announce that M₃₃ and M₃₅ 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.