BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Stable isoperimetry in lattice-like graphs - Ben Barber (Universit
 y of Manchester)
DTSTART:20200123T143000Z
DTEND:20200123T153000Z
UID:TALK137371@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:In a graph G\, the edge boundary of a set of vertices S is the
  set of edges leaving S\; the vertex boundary of S is the set of vertices 
 you can get to by following those edges.  The edge or vertex isoperimetric
  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\, unsurprisi
 ngly\, NP-hard.\n\nIn the 90s\, Imre Ruzsa used a combination of additive 
 combinatorial and geometric tools to solve the vertex isoperimetric proble
 m 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 has the slightly stronger 
 form “this particular configuration of n points has close to the smalles
 t possible boundary”. Must every set of n points with close to the small
 est possible boundary be similar to one of these configurations?  That is\
 , is the solution to the isoperimetric problem stable?  We show that the a
 nswer is yes\, in a strong quantitative form.  We also extend these result
 s to Cayley graphs of arbitrary finitely generated abelian groups with a f
 ree part.\n\nJoint work with Joshua Erde.\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR