Seminar series
Date
Tue, 15 Oct 2013
Time
14:30 -
15:30
Location
C2
Speaker
Andrew Thomason
Organisation
University of Cambridge
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.)
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.
The work is joint with David Saxton.