The asymptotics of the clustering transition for random constraint satisfaction problems

Abstract

Random Constraint Satisfaction Problems exhibit several phase transitions when their density of constraints is varied. One of these threshold phenomena, known as the clustering or dynamic transition, corresponds to a transition for an information theoretic problem called tree reconstruction. In this article we study this threshold for two CSPs, namely the bicoloring of $k$-uniform hypergraphs with a density $\alpha$ of constraints, and the $q$-coloring of random graphs with average degree $c$. We show that in the large $k,q$ limit the clustering transition occurs for $\alpha =\frac{2^{k-1}}{k}(\ln k+\ln \ln k+{\gamma }_{\mathrm{d}}+o(1))$, $c=q(\ln q+\ln \ln q+{\gamma }_{\mathrm{d}}+o(1))$, where ${\gamma }_{\mathrm{d}}$ is the same constant for both models. We characterize ${\gamma }_{\mathrm{d}}$ via a functional equation, solve the latter numerically to estimate ${\gamma }_{\mathrm{d}}\approx 0.871$, and obtain an analytic lowerbound ${\gamma }_{\mathrm{d}}\ge 1+\ln (2(\sqrt{2}-1))\approx 0.812$. Our analysis unveils a subtle interplay of the clustering transition with the rigidity (naive reconstruction) threshold that occurs on the same asymptotic scale at ${\gamma }_{\mathrm{r}}=1$.

arXiv comment35 pages, 8 figures

References in corpus (14)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Algorithmic barriers from phase transitions
• Reconstruction on trees and spin glass transition
• A variational description of the ground state structure in random satisfiability problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• On the freezing of variables in random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Reconstruction of Random Colourings
• The hard-core model on random graphs revisited
• Biased landscapes for random Constraint Satisfaction Problems
• Phase transitions in the $q$-coloring of random hypergraphs

Cited by in corpus (4)

• Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Random Recursive Hypergraphs
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states