List Colourings of Simple Hypergraphs
Presenter
September 9, 2014
Keywords:
- Hypergraphs, Coloring
MSC:
- 05C15
Abstract
Unlike the ordinary chromatic number, the list chromatic number necessarily
grows with the average degree. Indeed, Alon (2000) proved it grows with the
logarithm of the average degree. Recently, the same has been shown to be
true for uniform hypergraphs, by means of the "container method": we sketch
how this works. The question then arises as to the precise value of the
minimum list chromatic number. Here the answer turns out to be not what was
expected. We attempt to sketch the latest progress, and its implications
for containers. (Joint work with David Saxton and Ares Meroueh.)