Revolving Door (Middle Levels) Conjecture (1970s) -- SOLVED

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 22Ω(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 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 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 > ck2+k if k is large enough. Other extensions of the middle-levels problem were 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.
[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.



Index Page; Glossary


Posted 2005?; Last update 9/12/18