Sharp thresholds for constraint satisfaction problems and homomorphisms

Simple item page
dc.creatorHatami, Hamed
dc.creatorMolloy, Michael
dc.date2009-03-14
dc.date.accessioned2026-07-07T12:52:44Z
dc.date.available2026-07-07T12:52:44Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/0903.2579
dc.identifierhttp://arxiv.org/abs/0903.2579
dc.identifierRandom Structures Algorithms. 33(3) (2008), pp. 310- 332
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/223391
dc.subjectCombinatorics
dc.subjectProbability
dc.subject05C80
dc.titleSharp thresholds for constraint satisfaction problems and homomorphisms
dc.typetext

Files

Collections

arXiv