Abstract
For integers k ≥1 and n≥2k+1 the Kneser graph K(n;k) has as vertices all k-element subsets of [n]:={1;2;:::;n} and an edge between any two vertices (=sets) that are disjoint. The bipartite Kneser graph H(n,k) has as vertices all k-element and (n—k)-element subsets of [n] and an edge between any two vertices where one is a subset of the other. It has long been conjectured that all Kneser graphs and bipartite Kneser graphs except the Petersen graph K(5, 2) have a Hamilton cycle. The main contribution of this paper is proving this conjecture for bipartite Kneser graphs H(n,k). We also establish the existence of cycles that visit almost all vertices in Kneser graphs K(n,k) when n=2k+o(k), generalizing and improving upon previous results on this problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Biggs: Some odd graph theory, in: Second International Conference on Combinatorial Mathematics (New York, 1978), volume 319 of Ann. New York Acad. Sci., 71-81, New York Acad. Sci., New York, 1979.
M. Buck and D. Wiedemann: Gray codes with restricted density, Discrete Math. 48 (1984), 163-171.
Y. Chen and Z. Füredi: Hamiltonian Kneser graphs, Combinatorica 22 (2002), 147-149.
Y. Chen: Kneser graphs are Hamiltonian for n=3k, J. Combin. Theory Ser. B 80 (2000), 69-79.
Y. Chen: Triangle-free Hamiltonian Kneser graphs, J. Combin. Theory Ser. B 89 (2003), 1-16.
B. Chen and K. Lih: Hamiltonian uniform subset graphs, J. Combin. Theory Ser. B 42 (1987), 257-263.
D. Duffus, H. Kierstead and H. Snevily: An explicit 1-factorization in the middle of the Boolean lattice, J. Combin. Theory Ser. A 65 (1994), 334-342.
D. Duffus, B. Sands and R. Woodrow: Lexicographic matchings cannot form Hamiltonian cycles, Order 5 (1988), 149-161.
S. Felsner and W. Trotter: Colorings of diagrams of interval orders and ff-sequences of sets, Discrete Math. 144 (1995), 23-31. Combinatorics of ordered sets (Oberwolfach, 1991).
R. Gould: Updating the hamiltonian problem-a survey, Journal of Graph Theory 15 (1991), 121-157.
P. Gregor and R. Skrekovski: On generalized middle-level problem, Inform. Sci. 180 (2010), 2448-2457.
I. Havel: Semipaths in directed cubes, in: Graphs and other combinatorial topics (Prague, 1982), volume 59 of Teubner-Texte Math., 101-108. Teubner, Leipzig, 1983.
F. Harary, J. Hayes and H. Wu: A survey of the theory of hypercube graphs, Comput. Math. Appl. 15 (1988), 277-289.
P. Horák, T. Kaiser, M. Rosenfeld and Z. Ryjácek: The prism over the middlelevels graph is Hamiltonian, Order 22 (2005), 73-81.
G. Hurlbert: The antipodal layers problem, Discrete Math. 128 (1994), 237-245.
K. Heinrich and W. Wallis: Hamiltonian cycles in certain graphs, J. Austral. Math. Soc. Ser. A 26 (1978), 89-98.
R. Johnson: Long cycles in the middle two layers of the discrete cube, J. Combin. Theory Ser. A 105 (2004), 255-271.
R. Johnson: An inductive construction for Hamilton cycles in Kneser graphs, Electron. J. Combin. 18 (2011), Paper 189, 12.
R. Karp: Reducibility among combinatorial problems, in: Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), 85-103, New York, 1972. Plenum.
D. Kühn and D. Osthus: Hamilton cycles in graphs and hypergraphs: an extremal perspective, To appear in Proceedings of the ICM 2014.
H. Kierstead and W. Trotter: Explicit matchings in the middle levels of the Boolean lattice, Order 5 (1988), 163-171.
L. Lovász: Problem 11, in Combinatorial structures and their applications, in: Proc. Calgary Internat. Conf. (Calgary, Alberta, 1969), xvi+508, New York, 1970. Gordon and Breach Science Publishers.
L. Lovász: Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), 319-324.
M. Mather: The Rugby footballers of Croam, J. Combinatorial Theory Ser. B 20 (1976), 62-63.
G. Meredith and K. Lloyd: The Hamiltonian graphs O4 to O7, in: Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), 229-236. Inst. Math. Appl., Southend-on-Sea, 1972.
T. Mütze: Proof of the middle levels conjecture, accepted for publication by the Proceedings of the London Mathematical Society.
M. Shimada and K. Amano: A note on the middle levels conjecture, arXiv:0912.4564, September 2011.
C. Savage: Long cycles in the middle two levels of the boolean lattice, Ars Combin. 35-A (1993), 97-108.
C. Savage: A survey of combinatorial Gray codes, SIAM Rev. 39 (1997), 605-629.
J. Simpson: Hamiltonian bipartite graphs, in: Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), volume 85, 97-110, 1991.
J. Simpson: On uniform subset graphs, Ars Combin. 37 (1994), 309-318.
I. Shields and C. Savage: A note on Hamilton cycles in Kneser graphs, Bull. Inst. Combin. Appl. 40 (2004), 13-22.
I. Shields, B. Shields and C. Savage: An update on the middle levels problem, Discrete Math. 309 (2009), 5271-5277.
C. Savage and P. Winkler: Monotone Gray codes and the middle levels problem, J. Combin. Theory Ser. A 70 (1995), 230-248.
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of this work has appeared in the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb) 2015.
The author was supported by a fellowship of the Swiss National Science Foundation. This work was completed when the author was with the School of Mathematics at Georgia Institute of Technology, 30332 Atlanta GA, USA.
Rights and permissions
About this article
Cite this article
Mütze, T., Su, P. Bipartite Kneser Graphs are Hamiltonian. Combinatorica 37, 1207–1219 (2017). https://doi.org/10.1007/s00493-016-3434-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-016-3434-6