Abstract
Let G(n,p) be the random graph on n vertices where each edge is included independently with probability p=p(n). A classic question asks: how many colours do we need to colour each vertex so that adjacent vertices are always coloured differently? This is called the chromatic number. In 1987, Shamir and Spencer pioneered the use of martingale concentration inequalities in probabilistic combinatorics (which have now become a standard tool in the area) to show that the chromatic number of G(n,p) is concentrated on about n^(1/2) consecutive values. If p=p(n) tends to 0 quickly enough, this can be improved dramatically: Alon and Krivelevich proved that the chromatic number of G(n,p) is two-point concentrated whenever p<n^(-1/2 - epsilon). In view of strong concentration results, Bollobás and Erd?s asked the opposite question: can we find any examples where the chromatic number is not very narrowly concentrated? Specifically, can we show that the chromatic number of G(n, 1/2) is not concentrated on, say, 100 integers? This question remained open for a long time because there were no tools available to show non-concentration. I will present a recent result showing that, at least for some values n, the chromatic number of G(n, 1/2) is not concentrated on fewer than n^(1/2- o(1)) consecutive values, almost matching Shamir and Spencer's classic upper bound. Joint work with Oliver Riordan.