Register for: WIMSIG2017

Details of talk

TitleThresholds for colouring random graphs and hypergraphs
PresenterCatherine Greenhill (University of New South Wales)
Author(s)Peter Ayre, Amin Coja-Oghlan and Catherine Greenhill
SessionAlgebra and Discrete Mathematics
Time11:30:00 2017-09-25

A colouring of a graph (or hypergraph) is a map which assigns a colour to each
vertex so that no edge is monochromatic.  If there are $k$ available colours
then this map is called a $k$-colouring, and the minimum value of $k$ such that
a $k$-colouring exists is called the chromatic number of the
graph.  Graph colourings are fundamental objects of study, with applications in
many areas including statistical physics and radio frequency assignment.

The set of $k$-colourings of a graph (or hypergraph) with $cn$ edges undergoes
several phase transitions as $c$ increases.  Initially the problem is not very
constrained, so there are many solutions (colourings) and it is easy to move
from one solution to another, say by recolouring one vertex at a time. But as
$c$ increases, the solution space forms ``clusters'' of colourings which are
similar to one another.  Eventually, many vertices in a cluster are ``frozen'',
and are unable to be recoloured without also recolouring a constant fraction of
the vertices.  Finally, $c$ increases beyond the $k$-colourability threshold,
and the solution space becomes empty.

Statistical physicists have used heuristics to predict the value of many
colouring thresholds for graphs and hypergraphs.  Some of these thresholds have
been rigorously proved, starting with the pioneering work by Amin Coja-Oghlan
and his co-authors.  I will discuss my contributions
to this effort.