|
|
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.
|
|
|
|