Sharp Thresholds for Constraint Satisfaction Problem and Graph Homomorphisms

2006/12/14 by Hamed Hatami, Hatami, Hamed, Michael Molloy +1
Mathematics · #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C80

paper · pdf · doi:10.48550/arxiv.math/0612391

arxiv created 2006/12/14 · arxiv updated 2009/12/01

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.

Related

• Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems
• The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold
• The satisfiability threshold and solution space of random uniquely extendable constraint satisfaction problems