### Non-concentration of the chromatic number of a random graph

- Series
- Combinatorics Seminar
- Time
- Friday, January 10, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 202
- Speaker
- Lutz Warnke

We shall discuss the recent breakthrough of Annika Heckel on the chromatic number of the binomial random graph G(n,1/2), showing that it is not concentrated on any sequence of intervals of length n^{1/4-o(1)}.

To put this into context, in 1992 Erdos (and also Bollobás in 2004) asked for any non-trivial results asserting a lack of concentration, pointing out that even the weakest such results would be of interest.

Until recently this seemed completely out of reach, in part because there seemed to be no obvious approach/strategy how to get one's foot in the door.

Annika Heckel has now found such an approach, based on a clever coupling idea that compares the chromatic number of G(n,1/2) for different n.

In this informal talk we shall try to say a few words about her insightful proof approach from https://arxiv.org/abs/1906.11808

Please note the unusual room (Skiles 202)