BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:List colourings and preference orders - Andrew Thomason (Universit
 y of Cambridge)
DTSTART:20170504T133000Z
DTEND:20170504T143000Z
UID:TALK72522@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:The list chromatic number of a hypergraph G is the smallest nu
 mber k such that\, for any assignment to each vertex of G of a list of k c
 olours\, it is possible for each vertex to choose a colour from its list s
 o that no edge is monochromatic. Alon showed that the list chromatic numbe
 r of a graph is of order at least log d\, where d is the average degree. S
 axton et at did the same for r-uniform hypergraphs\, using the container m
 ethod.\n\nIs the lower bound best possible? Using a notion of "preference 
 orders" we examine the list chromatic numbers of multipartite hypergraphs\
 , showing thereby that the lower bound is best possible for r=2 and r=3 bu
 t probably not for r>=4. This is joint work with Arès Méroueh.
LOCATION:MR12
END:VEVENT
END:VCALENDAR