Disorder Chaos in Diluted Spin Glass models and Constraint Satisfaction Problems

This thesis investigates the phenomenon of disorder chaos in disordered systems, with a particular focus on random constraint satisfaction problems (CSPs) such as random k-SAT. We begin by introducing the framework of spin glass models, reviewing the Sherrington–Kirkpatrick (SK) model and its generalization to mixed p-spin models. In these fully connected systems, the presence of disorder chaos is well understood and has been rigorously established by Chen and Panchenko: even small perturbations of the disorder cause typical equilibrium configurations to become asymptotically orthogonal, confirming earlier predictions by Bray and Moore. We then turn to diluted models, where each variable participates only in a finite number of constraints. We consider k-SAT and related problems (NAESAT, XORSAT, hypergraph 2-coloring), we reinterpret them as Hamiltonians with random interactions, highlighting the analogy with spin glass systems. Within this framework, we analyze different perturbation schemes, such as resampling clauses or random signs. This thesis tries to establish a rigorous foundation for disorder chaos in diluted models :a phenomenon first understood in fully connected spin glasses that also governs the structure and stability of solutions in random CSPs.