NewEvery arXiv paper, its researchers & institutions — mapped.
paper

Sharp Thresholds for Constraint Satisfaction Problem and Graph Homomorphisms

arXiv:math/0612391

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.