Sharp thresholds for constraint satisfaction problems and homomorphisms | Zendy

Hatami Hamed | Zendy; Molloy Michael | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research