Approximate Isoperimetric Inequalities

Graphs, Hypergraphs, and Computing

11 March 15:30 - 16:30

Demetres Christofides - The University of Central Lancashire, UCLan Cyprus

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.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to