Phase transitions for the cavity approach to the clique problem on random graphs
arXiv:1011.2945 · doi:10.1007/s10955-011-0336-2
Abstract
We give a rigorous proof of two phase transitions for a disordered system designed to find large cliques inside Erdos random graphs. Such a system is associated with a conservative probabilistic cellular automaton inspired by the cavity method originally introduced in spin glass theory.
36 pages, 4 figures