The asymptotics of the clustering transition for random constraint satisfaction problems

11/21/2019
by   Louise Budzynski, et al.
0

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 + lnln k + γ_ d + o(1)), c= q (ln q + lnln 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset