Andrew Thomason: Independent sets in hypergraphs

Quite a few graph theoretical questions can be phrased in terms of independent sets in hypergraphs. Some nice results could be proved if the number of independent sets were small, but usually it is too big. We give some examples, such as list colouring of graphs and hypergraphs, sparse Turan theorems, counting solutions to equations, counting graphs with a given property, and so on.

For some of these applications, it would suffice to replace the collection of independent sets by a smaller collection of "containers". This is a collection of sets such that each independent set is a subset of a container set. To be useful, each container must not be too big and the total number of containers must not be too big: these statements can be made precise and will be illustrated by examples.

We show how containers can be constructed in a general hypergraph and give examples of applications. (This is joint work with David Saxton.)