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 t...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-09
Main Authors: Budzynski, Louise, Semerjian, Guilhem
Format: Article
Language:English
Subjects:
Asymptotic methods
Asymptotic series
Clustering
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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_{\rm 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_{\rm d}(k)\) in the large \(k\) limit. We find that \(\alpha_{\rm d}(k) = \frac{2^{k-1}}{k}(\ln k + \ln \ln k + \gamma_{\rm d} + o(1))\), where the constant \(\gamma_{\rm d}\) is strictly larger than for the uniform measure over solutions.
ISSN:2331-8422
DOI:10.48550/arxiv.2007.10303