SMS scnews item created by Stephan Tillmann at Tue 17 May 2016 0919
Type: Seminar
Distribution: World
Expiry: 16 Aug 2016
Calendar1: 18 May 2016 1200-1300
CalLoc1: Carslaw 535A
CalTitle1: Colouring random graphs and hypergraphs
Auth: tillmann@p710.pc (assumed)

Geometry & Topology

Colouring random graphs and hypergraphs

Catherine Greenhill (UNSW)

Wednesday 18 May 2016 from 12:00–13:00 in Carslaw 535A

Please join us for lunch after the talk!


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.