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
Adam Mickiewicz University
Technical University of Denmark, DTU