Friday February 10th at 11.30am

We are given a set of variables, and a domain of values that the variables can take.

Some subsets of the variables have ``constraints'' which restrict the value-assignments

that can be made to those variables. A problem is satisfiable if there is an assignment

of values to the variables which does not violate any of the constraints. Some well-studied

special cases are k-SAT, graph colourability and graph homomorphism.

In this talk, we discuss models of random constraint satisfaction problems. The main issue

is the following: if we form a random problem by adding random constraints one-at-a-time,

how does the probability of the problem being satisfiable change? It is clear that this

probability is monotonically decreasing as the number of constraints increases, but how

suddenly does it decrease? How many constraints must be added before the decrease is

significant? (In formal terms, these questions can be rephrased as "does the problem

have a sharp threshold of satisfiability?" and "how many constraints must be added before

it is no longer almost surely satisfiable?") These questions generalize the well-studied

notions of the threshold of satisfiability for a random instance of k-SAT and the threshold

of k-colourability for a random graph.