Stable Kneser Graphs are Hamiltonian

AGUSTINA VICTORIA LEDEZMA; ADRIÁN PASTINE

Nancy

Seminario; Seminario Malotec del equipo de investigación Orpailleur.; 2023

Laboratorio de Investigación LORIA de la Universidad de Lorraine en Nancy, Francia.

The Kneser graph $K(n,k)$ has as vertices the subsets of size $k$ from a base set of size $n$, and edges connecting vertices representing disjoint subsets. The s-stable Kneser subgraph $K_{s-stab}(n,k)$, is obtained by eliminating every subset that contains a pair of elements at cyclic distance $s$ or less.One of the most important open problems related to Kneser graphs is their Hamiltonicity, that is, whether every connected Kneser graph has a path or a cycle that goes through every vertex. In this talk, we present a construction that proves the existence of Hamilton cycles in s-stable Kneser graphs. Although this result is interesting in itself, we also propose a way to use it as a key ingredient in the research of Hamilton cycles in Kneser graphs.