CSC 2427 Topics in Graph Theory - Random Constraint Satisfaction Problems

Thursdays 1-4, WB 119

Produce a random graph by starting with n vertices, and then adding M random edges (in the obvious way).  How big does M need to be so that the graph is probably not r-colourable?  This is the oldest unsolved problem in random graph theory.

Produce a random instance of k-SAT by starting with n variables, and then adding M random k-clauses (in the obvious way). How big does M need to be so that this is probably not satisfiable?

These are two important examples of random constraint satisfaction problems.  We will study these and several others.  One important goal is to determine the values of M asked about above.  Another is to understand some algorithmic issues: when the number of edges is at the upper end of the range where the graph is probably r-colourable, then it appears to be very challenging (perhaps impossible) to produce an actual r-colouring efficiently.

Most recent successes on these problems have been focussed on some deep insights arising from statistical physics.  Physicists have developed a set of remarkable hypotheses which have led to a very strong understanding of these random problems and the reasons that they are algorithmically challenging.  Moreover, physicists have used these insights to develop a very impressive heuristic algorithm: Survey Propagation.  This is a version of Belief Propagation which performs quite well on random 3-SAT.

Much of this course will be focussed on understanding Survey Propagation, and other contributions from statistical physics.

I'll assume a good introductory level background in graph theory, such as that provided in CSC 2410 or a similar undergraduate course, and a basic background in probability.