Speaker:

Mike Molloy

Title:

Frozen vertices in colourings of a random graph

Abstract:

For many models of random constraint satisfaction problems, there is much evidence that if the constraint-density is sufficiently high, then the solutions can be partitioned into clusters that are, in some sense, both well-connected and well-separated. Furthermore, the clusters tend to contain a linear number of “frozen variables”, whose values are fixed within a cluster. The asymptoic density where such clusters arise corresponds to an algorithmic barrier, above which we don’t know of any complete algorithms that solve these CSPs.

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.