
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 kSAT, 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 wellconnected and wellseperated. 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 kcolourings of a random graph, when k is a sufficiently large constant. We determine the exact density threshold at which they appear.



