Campuses:

List Colourings of Simple Hypergraphs

Tuesday, September 9, 2014 - 10:15am - 11:05am
Keller 3-180
Andrew Thomason (University of Cambridge)
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.)
MSC Code: 
05C15