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: https://arxiv.org/abs/1911.09377v1
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

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_{\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