The condensation phase transition in random graph coloring (Q5963760)

The cavity method is a non-rigorous approach which has been proposed to study diluted mean-field models, in which the geometry of interactions is described by a sparse random graph or hypergraph. The specific model therein considered is the Potts antiferromagnet on the Erdős-Renyi random graph at zero temperature known as the random graph coloring problem. The contribution of the present paper is to prove that, in the random graph coloring problem, condensation occurs at the exact value predicted by the cavity method. The key of the proof is to establish an explicit link between the combinatorics of the graph coloring problem and the cavity formalism.