Sharp Thresholds for Constraint Satisfaction Problem and Graph Homomorphisms
Hamed Hatami, Michael S. O. Molloy · arXiv (Cornell University) · 2006
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 3.