Kneser graphs are Hamiltonian
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10509924" target="_blank" >RIV/00216208:11320/25:10509924 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=rcmtEd6Gfv" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=rcmtEd6Gfv</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.aim.2025.110189" target="_blank" >10.1016/j.aim.2025.110189</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Kneser graphs are Hamiltonian
Popis výsledku v původním jazyce
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 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 graphs include Kneser graphs as a special case. Our results imply that all known natural 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.
Název v anglickém jazyce
Kneser graphs are Hamiltonian
Popis výsledku anglicky
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 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 graphs include Kneser graphs as a special case. Our results imply that all known natural 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.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA22-15272S" target="_blank" >GA22-15272S: Principy kombinatorického generování</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2025
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Advances in Mathematics
ISSN
0001-8708
e-ISSN
1090-2082
Svazek periodika
468
Číslo periodika v rámci svazku
květen
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
80
Strana od-do
110189
Kód UT WoS článku
001443095600001
EID výsledku v databázi Scopus
2-s2.0-85219735334