论文标题
有偏见的措施解决随机约束满意度问题：较大的相互作用范围和渐近扩展
Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
论文作者
论文摘要
我们通过示例性的随机约束满意度问题（$ k $均匀的随机超图的双色溶液都不均匀地加权，$ k $均匀的随机超图的两种颜色，并通过属于不同超匹配的变量之间的软相互作用，我们研究了聚类的转变。我们表明，对于超计划中的限制交互，可以进一步增加阈值$α_ {\ rm d}（k）$，并在大$ k $限制中执行$α_ {\ rm d}（k）$的渐近扩张。我们发现$α_ {\ rm d}（k）= \ frac {2^{k-1}} {k}（\ ln k + \ ln \ ln \ ln \ ln k +γ_ {\ rm d} + rm d} + o（1））
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 $α_{\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 $α_{\rm d}(k)$ in the large $k$ limit. We find that $α_{\rm d}(k) = \frac{2^{k-1}}{k}(\ln k + \ln \ln k + γ_{\rm d} + o(1))$, where the constant $γ_{\rm d}$ is strictly larger than for the uniform measure over solutions.
