Isoperimetry In Integer Lattices

14 November 2017

The edge isoperimetric problem for a graph G is to find, for each n, the minimum number of edges leaving any set of n vertices.  Exact solutions are known only in very special cases, for example when G is the usual cubic lattice on Z^d, with edges between pairs of vertices at l_1 distance 1.  The most attractive open problem was to answer this question for the "strong lattice" on Z^d, with edges between pairs of vertices at l_infty distance 1.  Whilst studying this question we in fact solved the edge isoperimetric problem asymptotically for every Cayley graph on Z^d.  I'll talk about how to go from the specification of a lattice to a corresponding near-optimal shape, for both this and the related vertex isoperimetric problem, and sketch the key ideas of the proof. Joint work with Joshua Erde.

  • Combinatorial Theory Seminar