Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion

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 α _d(k) for the transition can be further increased with respect to a restricted interaction within the hyperedges, and perform an asymptotic expansion of α _d(k) in the large k limit. We find that ${\alpha }_d\left(k\right)=\frac{2^{k-1}}{k}(lnk+lnlnk+{\gamma }_d+o\left(1\right))$, where the constant γ _d is strictly larger than for the uniform measure over solutions. (paper)