Sharp Thresholds for Constraint Satisfaction Problem and Graph Homomorphisms

arXivmath/0612391MaRDI QIDQ6478432FDOQ6478432

Authors: Hamed Hatami, Michael Molloy 

Publication date: 14 December 2006

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.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

This page was built for publication: Sharp Thresholds for Constraint Satisfaction Problem and Graph Homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6478432)