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_{rm d} + o(1))$, $c= q (ln q + ln ln q + gamma_{rm d}+ o(1))$, where $gamma_{rm d}$ is the same constant for both models. We characterize $gamma_{rm d}$ via a functional equation, solve the latter numerically to estimate $gamma_{rm d} approx 0.871$, and obtain an analytic lowerbound $gamma_{rm 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_{rm r}=1$.
تحميل البحث