Presented by: 
Catherine Greenhill (UNSW)
Date: 
Mon 10 Aug, 2:00 pm - 3:00 pm
Venue: 
Steele Building (03), room 262

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, with applications in many areas including statistical physics and radio frequency assignment. The chromatic number of random graphs has been studied since the pioneering work of Erdos and Renyi (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 arguments. I will also discuss some results on the chromatic number of hypergraphs with a linear number of edges (joint work with Colin Cooper and Martin Dyer and, subsequently, Peter Ayre and Amin Coja-Oghlan.) This work which uses a more analytic approach, inspired by ideas from statistical mechanics.