Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems

Abstract

We demonstrate through two case studies, one on the p-spin interaction model and the other on the random K-satisfiability problem, that a heterogeneity transition occurs to the ground-state configuration space of a random finite-connectivity spin glass system at certain critical value of the constraint density. At the transition point, exponentially many configuration communities emerge from the ground-state configuration space, making the entropy density s(q) of configuration-pairs a non-concave function of configuration-pair overlap q. Each configuration community is a collection of relatively similar configurations and it forms a stable thermodynamic phase in the presence of a suitable external field. We calculate s(q) by the replica-symmetric and the first-step replica-symmetry-broken cavity methods, and show by simulations that the configuration space heterogeneity leads to dynamical heterogeneity of particle diffusion processes because of the entropic trapping effect of configuration communities. This work clarifies the fine structure of the ground-state configuration space of random spin glass models, it also sheds light on the glassy behavior of hard-sphere colloidal systems at relatively high particle volume fraction.

26 pages, 9 figures, submitted to Journal of Statistical Mechanics

References in corpus (29)

• The Bethe lattice spin glass revisited
• Supercooled Liquids for Pedestrians
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Recipes for metastable states in Spin Glasses
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Phase diagram of glassy systems in an external field
• Clustering of solutions in the random satisfiability problem
• The Entropy of the K-Satisfiability Problem
• Reconstruction on trees and spin glass transition
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Simplest random K-satisfiability problem
• On the freezing of variables in random constraint satisfaction problems
• On the dynamics of the glass transition on Bethe lattices
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Elusive Glassy Phase in the Random Field Ising Model
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Geometrical organization of solutions to random linear Boolean equations
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Signature of the Ground-State Topology in the Low-Temperature Dynamics of Spin Glasses
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Domain growth within the backbone of the three-dimensional $\pm J$ Edwards-Anderson spin glass
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations

Cited by in corpus (5)

• Entropy landscape of solutions in the binary perceptron problem
• Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
• Kinked Entropy and Discontinuous Microcanonical Spontaneous Symmetry Breaking
• Maximally flexible solutions of a random $K$-satisfiability formula
• Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process