Colouring random graphs and hypergraphs

Catherine Greenhill (UNSW)

Abstract

A colouring of a graph (or hypergraph) is a map which assigns a colour to each vertex such 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 in combinatorics, with applications in areas as diverse as statistical physics and radio frequency assignment. The chromatic number of random graphs has been studied since the pioneering work of Erdös and Rényi (1960). We will take a tour through some of the major results in this area, and the methods used to prove them, including the probabilistic method and martingale argumenets. I will also discuss some results on the chromatic number of hypergraphs with a linear number of edges (joint work with Martin Dyer and Alan Frieze, and with Peter Ayre and Amin Coja-Oghlan). This work uses a more analytic approach, inspired by results from statistical physics about phase transitions in the space of colourings.