Sharp Thresholds for Constraint Satisfaction Problem and Graph Homomorphisms

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 3.

References in corpus (3)

• On the non-3-colourability of random graphs
• Phase Transitions and all that
• Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems