Home » Subject » Graph Theory » Basic G.T. » Cycles

Middle levels problem (Solved)

Importance: Medium ✭✭
Author(s): Erdos, Paul
Subject: Graph Theory
» Basic Graph Theory
» » Cycles
Keywords:
Recomm. for undergrads: no
Posted by: tchow
on: September 25th, 2008
Solved by: Mütze, Torsten. “Proof of the Middle Levels Conjecture.” Proceedings of the London Mathematical Society. Third Series 112, no. 4 (2016): 677–713. doi:10.1112/plms/pdw004.
Conjecture   Let $ G_n $ be the bipartite graph whose vertices are the $ n $-subsets and the $ (n+1) $-subsets of a $ (2n+1) $-element set, and with inclusion as the adjacency relationship. Then $ G_n $ is Hamiltonian.

The graph $ G_n $ is known as the middle-levels graph because it may be thought of as the graph formed by the cover relations between the middle two layers of the Hasse diagram of the Boolean lattice of all subsets of a $ (2n+1) $-element set, partially ordered by inclusion. The conjecture has been computationally verified up to $ n=19 $ [AS] (Announced only at end of paper). It is also known that $ G_n $ contains a cycle containing at least $ 1 - o(1) $ of its vertices [J] and that $ G_n \times K_2 $ is Hamiltonian [HKRR].

Bibliography

[HKRR] Peter Horák, Tomáš Kaiser, Moshe Rosenfeld, Zdeněk Ryjáček, The prism over the middle-levels graph is Hamiltonian, Order 22 (2005), no. 1, 73--81.

[J] Robert J. Johnson, Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A 105 (2004), no. 2, 255--271. MathSciNet

[SW] Carla D. Savage and Peter Winkler, Monotone Gray codes and the middle levels problem, J. Combin. Theory Ser. A 70 (1995), no. 2, 230--248.

[SSS] Ian Shields, Brendan J. Shields, Carla D. Savage, An update on the middle levels problem, preprint.

[AS] Kazuyuki Amano, Manabu Shimada, A Note on the Middle Levels Conjecture, preprint.

[M] Mütze, Torsten. “Proof of the Middle Levels Conjecture.” Proceedings of the London Mathematical Society. Third Series 112, no. 4 (2016): 677–713.


* indicates original appearance(s) of problem.
add new comment