Sharp Thresholds for Constraint Satisfaction Problem and Graph Homomorphisms

MaRDI QIDQ6478432zbMATH OpenFDO

Authors Hamed Hatami, Michael Molloy

Publication date 14 December 2006

Mathematics Subject Classification ID

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

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.

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)