Sharp thresholds for constraint satisfaction problems and homomorphisms
classification
🧮 math.CO
math.PR
keywords
constraintproblemssatisfactionmodelssharpthresholdsbinarycertain
read the original abstract
We determine under which conditions certain natural models of random constraint satisfaction problems have sharp thresholds of satisfiability. These models include graph and hypergraph homomorphism, the $(d,k,t)$-model, and binary constraint satisfaction problems with domain size three.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.