2020/07/31 by Louise Budzynski, Guilhem Semerjian · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Asymptotic expansion #Cluster analysis #Constant (computer programming) #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Constraint satisfaction problem #Markov Chains and Monte Carlo Methods #Measure (data warehouse) #Point processes and geometric inequalities #Range (aeronautics) #cond-mat.dis-nn #cs.DM #math.PR
paper · pdf · doi:10.1088/1742-5468/abb8c8
published as J. Stat. Mech. (2020) 103406 · 33 pages, 11 figures, minor corrections
openalex created_date 2020/07/23 · arxiv created 2020/09/04 · openalex publication_date 2020/10/01 · arxiv updated 2020/11/13 · openalex updated_date 2026/08/06
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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:msub> <mml:mrow> <mml:mi>α</mml:mi> </mml:mrow> <mml:mrow> <mml:mi mathvariant="normal">d</mml:mi> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mrow> <mml:msup> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:mfrac> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow> <mml:mi>ln</mml:mi> <mml:mspace class="nbsp" width="0.3333em"/> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mi>ln</mml:mi> <mml:mspace class="nbsp" width="0.3333em"/> <mml:mi>ln</mml:mi> <mml:mspace class="nbsp" width="0.3333em"/> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:msub> <mml:mrow> <mml:mi>γ</mml:mi> </mml:mrow> <mml:mrow> <mml:mi mathvariant="normal">d</mml:mi> </mml:mrow> </mml:msub> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow> <mml:mn>1</mml:mn> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> , where the constant γ d is strictly larger than for the uniform measure over solutions.