SciPost Submission Page

The asymptotics of the clustering transition for random constraint satisfaction problems

by Louise Budzynski, Guilhem Semerjian

Submission summary

As Contributors: Louise Budzynski
Arxiv Link:
Date submitted: 2019-11-25
Submitted by: Budzynski, Louise
Submitted to: SciPost Physics
Discipline: Physics
Subject area: Statistical and Soft Matter Physics
Approaches: Theoretical, Computational


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$.

Current status:
Editor-in-charge assigned

Submission & Refereeing History

Submission 1911.09377v1 on 25 November 2019

Login to report or comment