Premium
Hypergraph coloring up to condensation
Author(s) -
Ayre Peter,
CojaOghlan Amin,
Greenhill Catherine
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20824
Subject(s) - hypergraph , combinatorics , condensation , frieze , mathematics , series (stratigraphy) , upper and lower bounds , phase transition , discrete mathematics , physics , quantum mechanics , mathematical analysis , thermodynamics , art history , paleontology , biology , art
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].