Discrete Mathematics and Optimization Seminar
Jan 10th, 2011
Frozen vertices in colourings of a random graph
Mike Molloy
Dept of Computer Science, University of Toronto
Abstract: Over the past decade, much of the work on random k-SAT, random graph colouring, and other random constraint satisfaction problems has focussed on some foundational hypotheses that have arisen from statistical physics. Some of the most important such hypotheses concern the ``clustering'' of the solutions. It is believed that, if the problem density is sufficiently high, then the solutions can be partitioned into clusters that are, in some sense, both well-connected and well-seperated. Furthermore, the clusters contain a linear number of ``frozen variables", whose values are fixed within a cluster. The density where these clusters form corresponds to an algorithmic barrier, above which we don't know of any complete algorithms which solve these problems.

In this talk, we prove that frozen vertices do indeed arise for k-colourings of a random graph, when k is a sufficiently large constant. We determine the exact density threshold at which they appear.