  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.
