Independent sets in hypergraphs

Graphs, Hypergraphs, and Computing

30 January 15:30 - 16:30

Andrew Thomason - University of Cambridge

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.)
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