Demetres Christofides: Approximate Isoperimetric Inequalities

Given a graph G and a subset S of its vertices, the boundary of S is defined to be the set of all vertices of G which do not belong to S but are adjacent to at least one vertex from S. The vertex isoperimetric problem in G is to find, for each k, the minimum size of the boundary amongst all subsets of G of size k.

In the talk we will present an approximate solution to the vertex isoperimetric problem for the graph of all r-subsets of an n-set where two r-subsets are adjacent if and only if their symmetric difference contains exactly two elements.

This is joint work with D. Ellis and P. Keevash.