Satisfiability Thresholds for Regular Occupation Problems
Preprint
Abstract
In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of regular CSPs, the so-called occupation problems. The regular $r$-in-$k$ occupation problems resemble a basis of this class. By now, out of these CSPs only the satisfiability threshold - the largest degree for which the problem admits asymptotically a solution - for the $1$-in-$k$ occupation problem has been rigorously established. Here we determine the satisfiability threshold of the $2$-in-$k$ occupation problem for all $k$. In the proof we exploit the connection of an associated optimization problem regarding the overlap of satisfying assignements to a fixed point problem inspired by belief propagation, a message passing algorithm developed for solving such CSPs.
Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Information-theoretic thresholds from the cavity methodAdvances in Mathematics, 2018
- Charting the Replica Symmetric PhaseCommunications in Mathematical Physics, 2018
- The asymptotic k-SAT thresholdAdvances in Mathematics, 2016
- Maximum independent sets on random regular graphsActa Mathematica, 2016
- Satisfiability Threshold for Random Regular nae-satCommunications in Mathematical Physics, 2015
- On the chromatic number of random d-regular graphsAdvances in Mathematics, 2010
- Survey propagation: An algorithm for satisfiabilityRandom Structures & Algorithms, 2005
- 2-factors in random regular graphsJournal of Graph Theory, 1996
- A Remark on Stirling’s Formula1985
- On the existence of a factor of degree one of a connected random graphActa Mathematica Hungarica, 1966