An update on the middle levels problem (Q1044886)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An update on the middle levels problem
scientific article

    Statements

    An update on the middle levels problem (English)
    0 references
    0 references
    0 references
    0 references
    15 December 2009
    0 references
    The middle levels problem is to find a Hamilton cycle in the graph \(M_{2k+1}\) formed by the middle two levels of the Hasse diagram of the Boolean lattice \({\mathcal B}_{2k+1}\). It was considered by \textit{I. J. Dejter} [Proc.\ 5th Int.\ Conf., Kalamazoo/Mich.\ 1984, 189--199 (1985; Zbl 0574.05035)]. The bipartite graph \(M_{2k+1}\) is hamiltonian for \(1 \leq k \leq 15\), see \textit{I. Shields} and \textit{C. D. Savage} [Congr.\ Numerantium 140, 161--178 (1999; Zbl 0960.05063)], and also for \(k=16\) and \(k=17\) [this note].
    0 references
    0 references
    Hamilton cycle
    0 references
    middle levels
    0 references
    Boolean lattice
    0 references
    necklace
    0 references
    0 references
    0 references