Phase transitions for the cavity approach to the clique problem on random graphs

Alexandre Gaudilliere, Benedetto Scoppola, Elisabetta Scoppola +1

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…