Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion

Abstract

We investigate the clustering transition undergone by an exemplary random constraint satisfaction problem, the bicoloring of $k$-uniform random hypergraphs, when its solutions are weighted non-uniformly, with a soft interaction between variables belonging to distinct hyperedges. We show that the threshold ${\alpha }_{\mathrm{d}}(k)$ for the transition can be further increased with respect to a restricted interaction within the hyperedges, and perform an asymptotic expansion of ${\alpha }_{\mathrm{d}}(k)$ in the large $k$ limit. We find that ${\alpha }_{\mathrm{d}}(k)=\frac{2^{k-1}}{k}(\ln k+\ln \ln k+{\gamma }_{\mathrm{d}}+o(1))$, where the constant ${\gamma }_{\mathrm{d}}$ is strictly larger than for the uniform measure over solutions.

33 pages, 11 figures, minor corrections