School of Mathematical Sciences

Containers for independent sets menu

Containers for independent sets

Andrew Thomason (Cambridge)
Mon, 30/09/2013 - 17:30
Seminar series: 

An r-uniform hypergraph consists of a vertex set and a set of edges that are r-subsets of the vertex set (so an ordinary graph is a 2-uniform hypergraph). An independent set in an r-uniform hypergraph is a subset of the vertices that contains no edges.

It turns out that many questions can be phrased naturally as questions about independent sets in hypergraphs: we shall give examples from graph colouring, equation solving in Abelian groups (including Sidon sets), extremal properties of random graphs, sparse arithmetic progressions and so on.

A container for the independent set is a superset of it. It turns out to be desirable for many applications to find a small collection of containers, none of which is large, but which between them contain every independent set. ("Large" and "small" have reasonable meanings which will be explained.)

We will illustrate with simple examples how such containers can be used to answer the above questions, and will indicate how containers might be found.

The work is joint with David Saxton.

Speaker's webpage