Ben Barber (Manchester) - Stable isoperimetry in lattice-like graphs
| Dates: | 11 February 2020 |
|---|
| Times: | 15:00 - 15:00 |
|---|
| What is it: | Seminar |
|---|
| Organiser: | Department of Mathematics |
|---|
| Who is it for: | University staff, External researchers, Adults, Alumni, Current University students |
|---|
| Speaker: | Ben Barber |
|---|
|
Abstract : 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 techniques from geometry and additive number theory 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.
Speaker
Ben Barber
Organisation: University of Manchester
Travel and Contact Information
Find event
Frank Adams 1
Alan Turing Building
Manchester
