BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Kneser graphs are Hamiltonian - Torsten Mutze (War
wick)
DTSTART;TZID=Europe/London:20240208T143000
DTEND;TZID=Europe/London:20240208T153000
UID:TALK211288AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/211288
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 t
wo disjoint sets. It has been conjectured since th
e 1970s that\nall Kneser graphs admit a Hamilton c
ycle\, with one notable exception\,\nnamely the Pe
tersen graph K(5\,2). This problem received consid
erable\nattention in the literature\, including a
recent solution for the sparsest\ncase n=2k+1. The
main contribution of our work is to prove the con
jecture\nin full generality. We also extend this H
amiltonicity result to all\nconnected generalized
Johnson graphs (except the Petersen graph). The\ng
eneralized Johnson graph J(n\,k\,s) has as vertice
s all k-element subsets of\nan n-element ground se
t\, and an edge between any two sets whose\ninters
ection has size exactly s. Clearly\, we have K(n\,
k)=J(n\,k\,0)\, i.e.\,\ngeneralized Johnson graphs
include Kneser graphs as a special case. Our\nres
ults imply that all known families of vertex-trans
itive graphs defined\nby intersecting set systems
have a Hamilton cycle\, which settles an\ninterest
ing special case of Lovász’ conjecture on Hamilton
cycles in\nvertex-transitive graphs from 1970. Ou
r main technical innovation is\nto study cycles in
Kneser graphs by a kinetic system of multiple gli
ders\nthat move at different speeds and that inter
act over time\, reminiscent of\nthe gliders in Con
way’s Game of Life\, and to analyze this system\nc
ombinatorially and via linear algebra.\n\nThis is
joint work with my students Arturo Merino (TU Berl
in) and Namrata\n(Warwick).
LOCATION:MR12
CONTACT:
END:VEVENT
END:VCALENDAR