The Asymptotics of the Clustering Transition for Random Constraint Satisfaction Problems

• Published in: Journal of statistical physics 2020-12, Vol.181 (5), p.1490-1522
• Main Authors: Budzynski, Louise, Semerjian, Guilhem
• Format: Article
• Language: English
• Subjects: Computer Science; Condensed Matter; Discrete Mathematics; Disordered Systems and Neural Networks; Mathematical and Computational Physics; Mathematics; Physical Chemistry; Physics; Physics and Astronomy; Probability; Quantum Physics; Statistical Physics and Dynamical Systems; Theoretical
• ISSN: 0022-4715; 1572-9613
• DOI: 10.1007/s10955-020-02635-8

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 α 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 α = 2 k - 1 k ( ln k + ln ln k + γ d + o ( 1 ) ) , c = q ( ln q + ln ln q + γ d + o ( 1 ) ) , where γ d is the same constant for both models. We characterize γ d via a functional equation, solve the latter numerically to estimate γ d ≈ 0.871 , and obtain an analytic lowerbound γ d ≥ 1 + ln ( 2 ( 2 - 1 ) ) ≈ 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 γ r = 1 .