Hypergraph coloring up to condensation. Issue 4 (12th December 2018) - Ayre, Peter; Coja‐Oghlan, Amin; Greenhill, Catherine
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 + ε q, where lim q → ∞ ε q = 0 . The new lower bound on the threshold matches the "condensation phase transition" predicted by statistical physics considerations [Krzakala et al., PNAS 2007].