Premium
Sharp thresholds for constraint satisfaction problems and homomorphisms
Author(s) -
Hatami Hamed,
Molloy Michael
Publication year - 2008
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20225
Subject(s) - constraint satisfaction problem , homomorphism , constraint satisfaction , mathematics , satisfiability , random graph , constraint (computer aided design) , hypergraph , complexity of constraint satisfaction , backtracking , constraint graph , discrete mathematics , graph , binary number , combinatorics , local consistency , mathematical optimization , statistics , arithmetic , geometry , probabilistic logic
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. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008