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

07/20/2020
by   Louise Budzynski, et al.
0

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 α_ d(k) = 2^k-1/k(ln k + lnln k + γ_ d + o(1)), where the constant γ_ d is strictly larger than for the uniform measure over solutions.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset