Discrete Mathematics and Optimization Seminar

---

Mike Molloy
University of Toronto
Friday February 10th at 11.30am
Burnside 920



Title. Random constraint satisfaction problems.

Abstract. Constraint satisfaction problems are generalizations of CNF boolean formulas.
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.