Sharp thresholds for random constraint satisfaction problems [1/3]

Опубликовано 6 сентября 2016, 5:04

We consider a wide family of models for random constraint satisfaction problems. This family includes random k-SAT, random k-colourability and many other well-studied generalizations. Our goal is to determine precisely which members of this family have sharp thresholds of satisfiability, in the sense (formalized by Friedgut) that the probability of satisfiability drops suddenly from 1-o(1) to o(1) as the number of constraints increases. In doing so, we want to understand what sorts of features can cause models to have coarse thresholds rather than sharp ones. In this talk, I'll report some early progress towards this goal. This includes: (1) a proof that, for any simple connected graph H (on at least 2 vertices), the property is