**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.