University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Kneser Graphs are Hamiltonian

## Kneser Graphs are HamiltonianAdd to your list(s) Download to your calendar using vCal - Namrata (Warwick)
- Thursday 05 October 2023, 15:00-16:00
- Poynting Small Lecture Theatre (S06).
If you have a question about this talk, please contact Dr. Jan Kurkofka. 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 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. Joint work with Arturo Merino and Torsten Mütze. This talk is part of the Combinatorics and Probability seminar series. ## This talk is included in these lists:- Combinatorics and Probability seminar
- Poynting Small Lecture Theatre (S06)
- School of Mathematics events
Note that ex-directory lists are not shown. |
## Other listsSeminars on Advanced Materials Computer Science Distinguished Seminars Algebra Reading Group on Sporadic Groups## Other talksHorizontal Mean Curvature Flow and stochastic optimal controls Hunt for an Earth-twin TBA TBA Quantum Sensing in Space Life : it’s out there, but what and why ? |