BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Kneser graphs are Hamiltonian - Torsten Mutze (Warwick)
DTSTART:20240208T143000Z
DTEND:20240208T153000Z
UID:TALK211288@talks.cam.ac.uk
CONTACT:103978
DESCRIPTION:or integers k>=1 and n>=2k+1\, the Kneser graph K(n\,k) has as
 \nvertices all k-element subsets of an n-element ground set\, and an edge\
 nbetween any two disjoint sets. It has been conjectured since the 1970s th
 at\nall Kneser graphs admit a Hamilton cycle\, with one notable exception\
 ,\nnamely the Petersen graph K(5\,2). This problem received considerable\n
 attention in the literature\, including a recent solution for the sparsest
 \ncase n=2k+1. The main contribution of our work is to prove the conjectur
 e\nin full generality. We also extend this Hamiltonicity result to all\nco
 nnected generalized Johnson graphs (except the Petersen graph). The\ngener
 alized Johnson graph J(n\,k\,s) has as vertices all k-element subsets of\n
 an n-element ground set\, and an edge between any two sets whose\nintersec
 tion has size exactly s. Clearly\, we have K(n\,k)=J(n\,k\,0)\, i.e.\,\nge
 neralized Johnson graphs include Kneser graphs as a special case. Our\nres
 ults imply that all known families of vertex-transitive graphs defined\nby
  intersecting set systems have a Hamilton cycle\, which settles an\nintere
 sting special case of Lovász’ conjecture on Hamilton cycles in\nvertex-
 transitive graphs from 1970. Our main technical innovation is\nto study cy
 cles in Kneser graphs by a kinetic system of multiple gliders\nthat move a
 t different speeds and that interact over time\, reminiscent of\nthe glide
 rs in Conway’s Game of Life\, and to analyze this system\ncombinatoriall
 y and via linear algebra.\n\nThis is joint work with my students Arturo Me
 rino (TU Berlin) and Namrata\n(Warwick).
LOCATION:MR12
END:VEVENT
END:VCALENDAR