Kneser Graphs Are Hamiltonian
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10476049" target="_blank" >RIV/00216208:11320/23:10476049 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1145/3564246.3585137" target="_blank" >https://doi.org/10.1145/3564246.3585137</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3564246.3585137" target="_blank" >10.1145/3564246.3585137</a>
Alternative languages
Result language
angličtina
Original language name
Kneser Graphs Are Hamiltonian
Original language description
For integers k >= 1 and n >= 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.. (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 graphs 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 Lovasz' 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA22-15272S" target="_blank" >GA22-15272S: Principles of combinatorial generation</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023
ISBN
978-1-4503-9913-5
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
963-970
Publisher name
ASSOC COMPUTING MACHINERY
Place of publication
NEW YORK
Event location
Orlando, USA
Event date
Jun 20, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001064640700079