Stable isoperimetry in lattice-like graphs

Add to your list(s) Download to your calendar using vCal

• Ben Barber (University of Manchester)
• Thursday 23 January 2020, 14:30-15:30
• MR12.

If you have a question about this talk, please contact Andrew Thomason.

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, unsurprisingly, NP-hard.

In 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 asymptotically for these graphs.

Each of these results has the slightly stronger form “this particular configuration of n points has close to the smallest possible 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 quantitative form. We also extend these results to Cayley graphs of arbitrary finitely generated abelian groups with a free part.

Joint work with Joshua Erde.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.