The chromatic number of random graphs
Oliver Riordan (Oxford)

The chromatic number of a graph is the minimum number of colours needed to colour the vertices so that adjacent vertices receive distinct colours. While this sounds like a game, in applications it is a very important property, corresponding to the minimum number of groups a set must be divided into to avoid any incompatible pairs within each group. The chromatic number is also studied purely theoretically, which will be the point of view here. A basic question is: considering all possible graphs on $n$ vertices, what do their chromatic numbers look like? How often does each possible value occur? Or, rephrasing, what is the distribution of the chromatic number of a graph chosen uniformly at random? Writing $X$ for this random variable, we can look for reasonable upper and lower bounds on the mean of $X$, and upper and lower bounds on the variance of $X$. For the last combination, nothing was known until a recent breakthrough of Annika Heckel. In this talk I will discuss some of the history of the problem, and try to describe some of the ideas Annika used, which she and I have since taken further.