An update on the middle levels problem (Q1044886): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2097603218 / rank | |||
Normal rank |
Revision as of 20:04, 19 March 2024
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