Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
Louise Budzynski, Guilhem Semerjian · Journal of Statistical Mechanics Theory and Experiment · 2020
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 α 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 + ln ln k + γ d + o ( 1 ) ) , where the constant γ d is strictly larger than for the uniform measure over solutions.