**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 misattributed to many people. It was widely known as the
"Erdos Revolving Door Conjecture".

**Comments/Partial results:**
The special case *k=(n-1)/2* has been verified for *k < 15*.
Let

Another approach seeks 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.

[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.

[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 8/31/07