A Hamilton Path Heuristic with Applications to the Middle Two Levels Problem
Ian Shields, Carla D. Savage · 1999
The notorious middle two levels problem is to find a Hamilton cycle in the middle two 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 result, due to Moews and Reid [11] in 1990, was that M2k+1 is Hamiltonian for all positive k through k = 11. We show that if a Hamilton path between two distinguished vertices exists in a reduced graph then a Hamilton cycle can be constructed in the middle two levels. We describe a heuristic for finding Hamilton paths and apply it to the reduced graph to extend the previous best known results. This also improves the best lower bound on the length of a longest cycle in M2k+1 for any k. 1