The Chromatic Number of a Random Hypergraph

Martin Dyer ( University of Leeds )

We consider the problem of k-colouring a random r-uniform hypergraph with n vertices and cn edges, where k, r and c remain constant as n grows. Achlioptas and Naor showed that the chromatic number of a random graph in this setting (the case r = 2) has one of two easily computable values for large n. We give a complete generalisation of this result to colouring random uniform hypergraphs.