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
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
Hamilton cycle
0 references
middle levels
0 references
Boolean lattice
0 references
necklace
0 references