The Asymptotics of the Clustering Transition for Random Constraint Satisfaction Problems
- PDF / 748,834 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 157 Views
The Asymptotics of the Clustering Transition for Random Constraint Satisfaction Problems Louise Budzynski1
· Guilhem Semerjian1
Received: 4 June 2020 / Accepted: 9 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Random constraint satisfaction problems exhibit several phase transitions when their density of constraints is varied. One of these threshold phenomena, known as the clustering or dynamic transition, corresponds to a transition for an information theoretic problem called tree reconstruction. In this article we study this threshold for two CSPs, namely the bicoloring of k-uniform hypergraphs with a density α of constraints, and the q-coloring of random graphs with average degree c. We show that in the large k, q limit the clustering transition k−1 occurs for α = 2 k (ln k + ln ln k + γd + o(1)), c = q(ln q + ln ln q + γd + o(1)), where γd is the same constant for both models. We characterize γd via a functional equation, solve the latter √ numerically to estimate γd ≈ 0.871, and obtain an analytic lowerbound γd ≥ 1 + ln(2( 2 − 1)) ≈ 0.812. Our analysis unveils a subtle interplay of the clustering transition with the rigidity (naive reconstruction) threshold that occurs on the same asymptotic scale at γr = 1. Keywords Statistical physics · Constraint satisfaction problems · Spin glasses · Disordered systems · Tree reconstruction
1 Introduction A constraint satisfaction problem (CSP) is a system of N variables that can take discrete values, with M constraints that each enforce some requirements on a subset of the variables, a solution of the CSP being an assignment of the variables which satisfies simultaneously all the constraints. The two examples of CSPs that will appear in this paper are the graph coloring and the hypergraph bicoloring problems. In the first one the variables are placed on the vertices of a graph, they have q possible values, to be interpreted as colors, and each edge of the graph enforce the constraint that the two vertices at its ends take different colors. The hypergraph bicoloring problem is similarly defined on an hypergraph, with hyperedges
Communicated by Federico Ricci-Tersenghi.
B 1
Louise Budzynski [email protected] Laboratoire de physique de l’Ecole normale supérieure, ENS, Université PSL, CNRS, Sorbonne Université, Université de Paris, 75005 Paris, France
123
L. Budzynski, G. Semerjian
linking subsets of k (instead of two for a graph) vertices; the variables on the vertices can take two colors, and the constraint associated to each hyperedge is that both colors are present among its k adjacent vertices. CSPs can be studied from several different perspectives; computational complexity theory [16,30] classifies them according to their worst-case difficulty, assessed by the existence or not of an efficient algorithm (running in a time polynomial in N , M) able to solve (i.e. to determine the existence or not of a solution) all their possible instances. Another line of work [2,3,7,13,17,19,22–24], in which this paper fin
Data Loading...
