Graph Theory seminar - Mike Molloy

Frozen vertices in colourings of a random graph

Abstract:

Over the past decade, much of the work on  random graph colouring,random k-SAT, and other random constraint satisfaction problems has focussed on some foundational unproven hypotheses that have arisen from statistical physics. Some of the most important such hypotheses concern the "clustering" of solutions.

In the context of colourings: It is believed that if the edge-density is sufficiently high then the colourings of a random graph can be partitioned into clusters that are, in some sense, both well-connected and well separated. Furthermore, clusters contain a linear number of "frozen vertices", whose colours remain fixed amongst all the colourings in a cluster. The density above which such clusters appear corresponds to an "algorithmic barrier", above which no algorithm has been proven to find a colouring.

In this talk, we prove that colourings of a random graph do indeed have frozen vertices, and we determine the exact edge-density threshold at which they appear.