Speaker: Andrew Thomason, Cambridge
Title: Hypergraph containers
Abstract:
A collection of containers for a (uniform) hypergraph is a collection of
subsets of the vertex set such that every independent set lies inside a
container. It has been discovered (Balogh, Morris, Samotij, and Saxton)
that it is always possible to find such a collection for which the
containers are not big (close to independent) and the size of the
collection itself is quite small. This basic, if surprising, fact has many
applications, and allows easy proofs of some theorems that were previously
difficult or unknown.
Our aim in these two seminars will be roughly the following. We will look
at some illustrative examples of the use of containers, and then give a
quick and easy proof of a restricted, but still very useful, version of the
container theorem. We then set up the algorithm on which the full theorem
is based, and show that it does work as claimed. We also explain why the
theorem is, in a way, best possible.
I hope to give the algorithm by the end of the first seminar, with recap
and proof in the second.
------------------------
* This is the first of a 2-part talk. The second talk, in the CS theory seminar, will take place
on Wednesday Nov. 16, 10:30 – 11:30, at the same room Rothberg (CS) B220.
See you there,
eran