Details of talk
|Title||Thresholds for colouring random graphs and hypergraphs|
|Presenter||Catherine Greenhill (University of New South Wales)|
|Author(s)||Peter Ayre, Amin Coja-Oghlan and Catherine Greenhill|
|Session||Algebra and Discrete Mathematics|
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.