The Library
Kneser graphs are Hamiltonian
Tools
Merino, Arturo, Mutze, Torsten and Namrata, (2023) Kneser graphs are Hamiltonian. In: 55th Annual ACM Symposium on Theory of Computing (STOC2023), Miami, Florida, USA, 20-23 Jun 2023 (In Press)
|
PDF
WRAP-Kneser-graphs-Hamiltonian-Mutze-2022.pdf - Accepted Version - Requires a PDF viewer. Download (5Mb) | Preview |
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\'asz' 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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Graph theory, Hamiltonian graph theory, Petersen graphs | ||||||
Publisher: | ACM | ||||||
Official Date: | 2023 | ||||||
Dates: |
|
||||||
Status: | Peer Reviewed | ||||||
Publication Status: | In Press | ||||||
Date of first compliant deposit: | 13 March 2023 | ||||||
Date of first compliant Open Access: | 13 March 2023 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 55th Annual ACM Symposium on Theory of Computing (STOC2023) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Miami, Florida, USA | ||||||
Date(s) of Event: | 20-23 Jun 2023 | ||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year