Kneser graphs are Hamiltonian

EUROCOMB’23

Arturo Merino Torsten Mütze - Namrata

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-101

PDF
Abstract
For integers $k\geq 1$ and $n\geq 2k+1$, the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph $K(5,2)$. This problem received considerable attention in the literature, including a recent solution for the sparsest case $n=2k+1$. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph $J(n,k,s)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two sets whose intersection has size exactly $s$. Clearly, we have $K(n,k)=J(n,k,0)$, i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász‘ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway‘s Game of Life, and to analyze this system combinatorially and via linear algebra.

Pages:
731–739
References

A. T. Balaban. Chemical graphs. XIII. Combinatorial patterns. Rev. Roumain Math. Pures Appl., 17:3-16, 1972.

N. Biggs. Some odd graph theory. In Second International Conference on Combinatorial Mathematics (New York, 1978), volume 319 of Ann. New York Acad. Sci., pages 71-81. New York Acad. Sci., New York, 1979.
https://doi.org/10.1111/j.1749-6632.1979.tb32775.x

J. Bellmann and B. Schülke. Short proof that Kneser graphs are Hamiltonian for n ≥ 4k. Discrete Math., 344(7):Paper No. 112430, 2 pp., 2021.
https://doi.org/10.1016/j.disc.2021.112430

Y. Chen and Z. Füredi. Hamiltonian Kneser graphs. Combinatorica, 22(1):147-149, 2002.
https://doi.org/10.1007/s004930200007

Y. Chen. Kneser graphs are Hamiltonian for n ≥ 3k. J. Combin. Theory Ser. B, 80(1):69-79, 2000.
https://doi.org/10.1006/jctb.2000.1969

Y. Chen. Triangle-free Hamiltonian Kneser graphs. J. Combin. Theory Ser. B, 89(1):1-16, 2003.
https://doi.org/10.1016/S0095-8956(03)00040-6

W. E. Clark and M. E. H. Ismail. Binomial and Q-binomial coefficient inequalities related to the Hamiltonicity of the Kneser graphs and their Q-analogues. J. Combin. Theory Ser. A, 76(1):83-98, 1996.
https://doi.org/10.1006/jcta.1996.0089

B. Chen and K. Lih. Hamiltonian uniform subset graphs. J. Combin. Theory Ser. B, 42(3):257-263, 1987.
https://doi.org/10.1016/0095-8956(87)90044-X

P. Erdős, C. Ko, and R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2), 12:313-320, 1961.
https://doi.org/10.1093/qmath/12.1.313

C. Greene and D. J. Kleitman. Strong versions of Sperner's theorem. J. Combin. Theory Ser. A, 20(1):80-88, 1976.
https://doi.org/10.1016/0097-3165(76)90079-0

P. Gregor, T. Mütze, and J. Nummenpalo. A short proof of the middle levels theorem. Discrete Anal., pages Paper No. 8, 12 pp., 2018.
https://doi.org/10.19086/da.3659

R. J. Gould. Updating the Hamiltonian problem-a survey. J. Graph Theory, 15(2):121-157, 1991.
https://doi.org/10.1002/jgt.3190150204

K. Heinrich and W. D. Wallis. Hamiltonian cycles in certain graphs. J. Austral. Math. Soc. Ser. A, 26(1):89-98, 1978.
https://doi.org/10.1017/S1446788700011563

J. R. Johnson. An inductive construction for Hamilton cycles in Kneser graphs. Electron. J. Combin., 18(1):Paper 189, 12 pp., 2011.
https://doi.org/10.37236/676

M. Jiang and F. Ruskey. Determining the Hamilton-connectedness of certain vertex-transitive graphs. Discrete Math., 133(1-3):159-169, 1994.
https://doi.org/10.1016/0012-365X(94)90023-X

M. Knor. Gray codes in graphs. Math. Slovaca, 44(4):395-412, 1994.

L. Lovász. Problem 11. In Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, AB, 1969). Gordon and Breach, New York, 1970.

L. Lovász. Kneser's conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A, 25(3):319-324, 1978.
https://doi.org/10.1016/0097-3165(78)90022-5

M. Mather. The Rugby footballers of Croam. J. Combin. Theory Ser. B, 20(1):62-63, 1976.
https://doi.org/10.1016/0095-8956(76)90066-6

G. H. J. Meredith and E. K. Lloyd. The Hamiltonian graphs O4 to O7 . In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pages 229-236. Inst. Math. Appl., Southend-on-Sea, 1972.

G. H. J. Meredith and E. K. Lloyd. The footballers of Croam. J. Combin. Theory Ser. B, 15:161-166, 1973.
https://doi.org/10.1016/0095-8956(73)90016-6

A. Merino, T. Mütze, and Namrata. Kneser graphs are Hamiltonian. arXiv:2212.03918. Full preprint version of the present article, 2022.
https://doi.org/10.1145/3564246.3585137

T. Mütze, J. Nummenpalo, and B. Walczak. Sparse Kneser graphs are Hamiltonian. J. Lond. Math. Soc. (2), 103(4):1253-1275, 2021.
https://doi.org/10.1112/jlms.12406

T. Mütze and P. Su. Bipartite Kneser graphs are Hamiltonian. Combinatorica, 37(6):1207-1219, 2017.
https://doi.org/10.1007/s00493-016-3434-6

T. Mütze. Proof of the middle levels conjecture. Proc. Lond. Math. Soc., 112(4):677-713, 2016.
https://doi.org/10.1112/plms/pdw004

T. Mütze. Gliders in Kneser graphs, 2023. http://tmuetze.de/gliders.html.

I. Shields and C. D. Savage. A note on Hamilton cycles in Kneser graphs. Bull. Inst. Combin. Appl., 40:13-22, 2004.

D. Tang and C. Liu. Distance-2 cyclic chaining of constant-weight codes. IEEE Trans. Comput., C-22:176-180, 1973.
https://doi.org/10.1109/T-C.1973.223681

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Arturo Merino, Torsten Mütze, - Namrata

PDF