University of Cambridge > > Combinatorics Seminar > Stable isoperimetry in lattice-like graphs

Stable isoperimetry in lattice-like graphs

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

  • UserBen Barber (University of Manchester)
  • ClockThursday 23 January 2020, 14:30-15:30
  • HouseMR12.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity