An update on the middle levels problem

Simple item page
dc.creatorShields, Ian
dc.creatorShields, Brendan J.
dc.creatorSavage, Carla D.
dc.date2006-08-19
dc.date.accessioned2026-07-07T07:21:56Z
dc.date.available2026-07-07T07:21:56Z
dc.descriptionThe middle levels problem is to find a Hamilton cycle in the middle levels, M_{2k+1}, of the Hasse diagram of B_{2k+1} (the partially ordered set of subsets of a 2k+1-element set ordered by inclusion). Previously, the best result was that M_{2k+1} is Hamiltonian for all positive k through k=15. In this note we announce that M_{33} and M_{35} 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.
dc.description11 pages, 5 figures
dc.identifierhttps://arxiv.org/abs/math/0608485
dc.identifierhttp://arxiv.org/abs/math/0608485
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/115482
dc.subjectCombinatorics
dc.subject05C45 (Primary), 05C85 (Secpndary)
dc.titleAn update on the middle levels problem
dc.typetext

Files

Collections

arXiv