2007/05/15 by Guilhem Semerjian · 5 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Cluster analysis #Computation #Constraint Satisfaction and Optimization #Constraint satisfaction dual problem #Constraint satisfaction problem #Data Management and Algorithms #Data Mining Algorithms and Applications #Discrete mathematics #Graph #Local consistency #Mathematics #Phase transition #Physics #Random graph #Satisfiability #Statistical physics #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC #math.PR
paper · pdf · doi:10.1007/s10955-007-9417-7
published as J. Stat. Phys. 130, 251 (2008) · 32 pages, 7 figures
arxiv created 2007/05/15 · openalex publication_date 2007/10/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The set of solutions of random constraint satisfaction problems (zero energy groundstates of mean-field diluted spin glasses) undergoes several structural phase transitions as the amount of constraints is increased. This set first breaks down into a large number of well separated clusters. At the freezing transition, which is in general distinct from the clustering one, some variables (spins) take the same value in all solutions of a given cluster. In this paper we study the critical behavior around the freezing transition, which appears in the unfrozen phase as the divergence of the sizes of the rearrangements induced in response to the modification of a variable. The formalism is developed on generic constraint satisfaction problems and applied in particular to the random satisfiability of boolean formulas and to the coloring of random graphs. The computation is first performed in random tree ensembles, for which we underline a connection with percolation models and with the reconstruction problem of information theory. The validity of these results for the original random ensembles is then discussed in the framework of the cavity method.