15 October 2013

14:30

Andrew Thomason

Abstract

<p>An independent set in an $r$-uniform hypergraph is a subset of the vertices
that contains no edges. 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.)
<br />
<br />Applications include giving bounds on the list chromatic number of
hypergraphs (including improving known bounds for graphs), counting the
solutions to equations in Abelian groups, counting Sidon sets,
establishing extremal properties of random graphs, etc.
<br />
<br />The work is joint with David Saxton.</p>