Bicolouring random hypergraphs
Tommaso Castellani, Vincenzo Napolano, Federico Ricci‐Tersenghi, Riccardo Zecchina · Journal of Physics A Mathematical and General · 2003
We study the problem of bicolouring random hypergraphs, both numerically and analytically. We apply the zero-temperature cavity method to find analytical results for the phase transitions (dynamic and static) in the one-step replica symmetry breaking (1RSB) approximation. These points appear to be in agreement with the results of the numerical algorithm. In the second part, we implement and test the survey propagation algorithm for specific bicolouring instances in the so-called HARD-SAT phase.