Hypergraph colouring up to condensation

Abstract: 

 A hypergraph is kk-uniform if every hyperedge contains kk 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 qq-colouring a random kk-uniform hypergraph with nn vertices and cncn edges, where qq, kk and cc are constants and nn tends to infinity. Most recently Dyer, Frieze and Greenhill (2014) determined the qq-colourability threshold up to a multiplicative 1+o(1)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 qq-colouring, we are able to reduce the uncertainty in the threshold to an additive error of ln2+o(1)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.