Hypergraph colouring up to condensation

Peter Ayre

UNSW

Date:

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

Venue:

RC-M032, The Red Centre, UNSW

Abstract:

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.