Hypergraph coloring up to condensation

Abstract

Improving a result of Dyer, Frieze and Greenhill [Journal of Combinatorial Theory, Series B, 2015], we determine the $q$-colorability threshold in random $k$-uniform hypergraphs up to an additive error of $\ln 2+{\epsilon }_q$, where ${\lim }_{q\to \infty }{\epsilon }_q=0$. The new lower bound on the threshold matches the "condensation phase transition" predicted by statistical physics considerations [Krzakala et al., PNAS 2007].

31 pages. Revised version, addressing referees' comments