Videos

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.)