14:30
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.