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 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 f(k)>1/4 for all k. Savage and Winkler [SW] improved this to f(k) > .839. Shields and Savage [SS] proved that f(k) > .86. Johnson [J] proved that f(k)=1-o(1).
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 > ck2+k if k is large enough. Other extensions of the middle-levels problem are discussed by Dejter and Quintana [DQ2].
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.