Containers for independent sets

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>
  • Combinatorial Theory Seminar