Hypergraph colouring up to condensation


Peter Ayre




Fri, 27/11/2015 - 10:30am


RC-M032, The Red Centre, UNSW


 A hypergraph is $k$-uniform if every hyperedge contains $k$ vertices. A colouring of a hypergraph is an assignment of colours to the vertices such that no hyperedge is monochromatic. We consider the problem of $q$-colouring a random $k$-uniform hypergraph with $n$ vertices and $cn$ edges, where $q$, $k$ and $c$ are constants and $n$ tends to infinity. Most recently Dyer, Frieze and Greenhill (2014) determined the $q$-colourability threshold up to a multiplicative $1 + o(1)$ factor. However, due to changes in the geometry of the solution space a vanilla second moment argument becomes untenable at edge densities above those considered. Following developments by Coja-Oghlan and Vilenchik (2014) in graph $q$-colouring, we are able to reduce the uncertainty in the threshold to an additive error of $\ln 2 + o(1)$. In order to do so, we consider a new variable which is informed by non-rigorous physics predictions on the geometry of the solution space of colours. This new threshold matches the conjectured location of the ’condensation phase transition’ which poses yet another technical barrier.

School Seminar Series: