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.


Peter Ayre

Research Area



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


RC-M032, Red Centre, UNSW