The middle levels conjecture (Havel 1983, Buck and Wiedemann 1984), also known as revolving door conjecture, posits that the middle
layer graph of order has a Hamilton cycle for
every .
The conjecture was proved by Mütze (2016); see also Mütze (2024).
Buck, M. and Wiedemann, D. "Gray Codes With Restricted Density." Disc. Math.48, 163-171, 1984.Diaconis,
P. and Graham, R. Magical
Mathematics: The Mathematical Ideas That Animate Great Magic Tricks. Princeton,
NJ: Princeton UNiversity Press, 2011.Felsner, S. and Trotter, W. T.
"Colorings of Diagrams of Interval Orders and -Sequences of Sets." Disc. Math.144,
23-31, 1995.Havel, I. "Semipaths in Directed Cubes." In Graphs
and Other Combinatorial Topics (Prague, 1982). Leipzig, Germany: Teubner, pp. 101-108,
1983.Kierstead, H. A. and Trotter, W. T. "Explicit Matchings
in the Middle Levels of the Boolean Lattice." Order5, 163-171,
1988.Knuth, D. E. The
Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1.
New York: Addison-Wesley, 2021.Mütze, T. "Proof of the Middle
Levels Conjecture." 11 Aug 2014. https://arxiv.org/abs/1404.4442.Mütze,
T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems."
Not. Amer. Soc.74, 583-592, 2024.Savage, C. D. and
Winkler, P. "Monotone Gray Codes and the Middle Levels Problem." J.
Combin. Th. Ser. A70, 230-248, 1995.Winkler, P. Mathematical
Puzzles. Boca Raton, FL: CRC Press, 2003.