**Originator(s):**
I. Havel

**Definitions:**
With [*n*]={1,...,*n*}, let
*B(n,k)* denote the graph whose vertices are the *k*-sets and
*(n-k)*-sets in [*n*], with vertices adjacent when one contains
the other.

**Conjecture:**
There is a cycle through the *k*-sets and *(k+1)*-sets in
[*2k+1*] by alternately adding and deleting one element.
More generally, Havel [Ha] conjectured that *B(n,k)* is Hamiltonian
whenever *1 < k < n/2*.

**Background/motivation:**
The special case *k=(n-1)/2* was popular at the Banff conferences in 1981
and 1984 and was attributed also to Dejter, Erdös, Trotter, and others.
It was widely known as the "Erdös Revolving Door Conjecture".

**Comments:**
Many papers proved special cases or gave lower bounds on the length of the
longest cycle. Some of these are describe below for historical background.
The crucial point is that the conjecture for the case *k=(n-1)/2* was
proved by Torsten Mütze [M]. The paper also showed that there are at
least *2 ^{2Ω(k)}* Hamiltonian cycles.

In addition, the problem for general *k* was solved by
Mütze and Su [MS], and an algorithmic proof of the case
*k=(n-1)/2* was obtained by Mütze and Nummenpalo [MN1], with
source code in C++ at http://www.math.tu-berlin.de/~muetze/.
In [MN2], the authors later published a simpler and faster algorithm,
based on a shorter and much simpler proof of the conjecture
by Gregor, Mütze, and Nummenpalo [GMP].

**Earlier partial results:**
Let *f(k)* denote the fraction of the vertices in the
longest cycle in *B(2k+1,k)*; the conjecture states that *f(k)=1*.
Dejter and Quintana [DQ1] proved that if *f(k)=1*, then
*f(k+1) > 3/4*.
Felsner and Trotter [FT] proved that

Another approach sought cycles of restricted forms by using an auxiliary
quotient graph on cyclic classes of binary *(2k+1)*-tuples; Dejter [D]
showed that spanning paths in this graph lift to spanning cycles in
*B(2k+1,k)*. Also, a spanning cycle in *B(2k+1,k)* must consist of
two 1-factors in the graph of possible edges; examples of 1-factors in this
graph are discussed in [DKS, DSW, KT].

For the general conjecture, Hurlbert [Hu] proved that *B(n,k)* is
Hamiltonian whenever * n > ck ^{2}+k* if

**References:**

[D] I.J. Dejter, Hamilton cycles and quotients of bipartite graphs.
Graph theory with applications to algorithms and computer science (Kalamazoo,
Mich., 1984), 189--199, Wiley-Intersci. Publ., Wiley, New York, 1985.

[DCQ] I.J. Dejter, J. Cordova, J.A. Quintana, Two Hamilton cycles in bipartite
reflective Kneser graphs. Proceedings of the First Japan Conference on Graph
Theory and Applications (Hakone, 1986). Discrete Math. 72 (1988), no. 1-3,
63--70.

[DQ1] I.J. Dejter, J. Quintana, Long cycles in revolving door graphs.
Eighteenth Southeastern International Conference on Combinatorics, Graph
Theory, and Computing (Boca Raton, Fla., 1987).
Congr. Numer. 60 (1987), 163--168.

[DQ2] I.J. Dejter, J. Quintana, On an extension of a conjecture of I. Ha'vel.
Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988),
327--341, Wiley-Intersci. Publ., Wiley, New York, 1991.

[DKS] D.A. Duffus, H.A. Kierstead, H.S. Snevily, An explicit $1$-factorization
in the middle of the Boolean lattice.
J. Combin. Theory Ser. A 65 (1994), no. 2, 334--342.

[DSW] D.A. Duffus, B. Sands, R. Woodrow,
Lexicographic matchings cannot form Hamiltonian cycles.
Order 5 (1988), no. 2, 149--161.

[FT] S. Felsner, W.T. Trotter, Colorings of diagrams of interval orders and
*\alpha*-sequences of sets, Discrete Math. 144 (1995) 23--31.

[GMP] P. Gregor, T. Mütze, J. Nummenpalo,
A short proof of the middle-levels theorem,
Discrete Analysis 8 (2018), 12 pp; arXiv:1710.08249

[Ha] I. Havel, Semipaths in directed cubes, in: M. Fiedler (Ed.), Graphs and
other Combinatorial Topics, Teubner-Texte Math., Teubner, Leipzig, 1983, pp.
101--108.

[Hu] G. Hurlbert, The antipodal layers problem.
Discrete Math. 128 (1994), no. 1-3, 237--245.

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

[KT] H.A. Kierstead, W.T. Trotter,
Explicit matchings in the middle levels of the Boolean lattice.
Order 5 (1988), no. 2, 163--171.

[M] T. Mütze,
Proof of the middle levels conjecture.
Proc. Lond. Math. Soc. (3) 112 (2016), no. 4, 677--713.

[MN] T. Mütze and J. Nummenpalo,
Efficient computation of middle levels Gray codes.
Algorithmsâ€”ESA 2015, 915--927, Lecture Notes in Comput. Sci. 9294,
(Springer 2015), and ACM Trans. Algorithms 14 (2018), no. 2, Art. 15, 29 pp.

[MS] T. Mütze and P. Su,
Bipartite Kneser graphs are Hamiltonian.
Combinatorica 37 (2017), no. 6, 1207--1219.

[SS] C.D. Savage, I. Shields, A Hamilton path heuristic with applications to the
middle two levels problem, Congr. Numer. 140 (1999) 161--178.

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

Posted 2005?; Last update 9/12/18