Revolving Door (Middle Levels) Conjecture (1970s)

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

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

Index Page; Glossary

Posted 2005?; Last update 8/31/07