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:Stable isoperimetry in lattice-like graphs - Ben B
arber (University of Manchester)
DTSTART;TZID=Europe/London:20200123T143000
DTEND;TZID=Europe/London:20200123T153000
UID:TALK137371AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/137371
DESCRIPTION:In a graph G\, the edge boundary of a set of verti
ces S is the set of edges leaving S\; the vertex b
oundary of S is the set of vertices you can get to
by following those edges. The edge or vertex iso
perimetric problem for G is to determine how small
the edge or vertex boundary of S can be\, given |
S|. Solving these problems for arbitrary G is\, un
surprisingly\, NP-hard.\n\nIn the 90s\, Imre Ruzsa
used a combination of additive combinatorial and
geometric tools to solve the vertex isoperimetric
problem asymptotically for “lattice-like” graphs (
Cayley graphs of Z^d). In 2017\, Joshua Erde and
I solved the edge isoperimetric problem asymptotic
ally for these graphs.\n\nEach of these results ha
s the slightly stronger form “this particular conf
iguration of n points has close to the smallest po
ssible boundary”. Must every set of n points with
close to the smallest possible boundary be similar
to one of these configurations? That is\, is the
solution to the isoperimetric problem stable? We
show that the answer is yes\, in a strong quantit
ative form. We also extend these results to Cayle
y graphs of arbitrary finitely generated abelian g
roups with a free part.\n\nJoint work with Joshua
Erde.\n
LOCATION:MR12
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR