The (non-)concentration of the chromatic number

Add to your list(s) Download to your calendar using vCal

• Oliver Riordan (University of Oxford)
• Thursday 31 October 2019, 14:30-15:30
• MR12.

If you have a question about this talk, please contact Andrew Thomason.

Let $G(n,1/2)$ be the random graph on $n$ vertices in which each edge is present with probability $1/2$, independently of the others. A classical question is: what is the chromatic number $X_n$ of $G(n,1/2)$, i.e., how many colours do we need to colour all vertices so that adjacent vertices receive different colours? Of course, $X_n$ is a random variable: one main thrust of past work is proving better and better upper and lower bounds that hold with high probability (probability tending to 1), starting with the asymptotic formula proved by Bollob\’as in the 1980s. A separate direction asked: even if we can’t pin down the value of $X_n$ precisely, can we bound how much it varies? A nowadays standard argument gives an upper bound of $O(n^{1/2})$. Surprisingly, until very recently \emph{no} meaningful lower bounds were known, although this natural question was raised by Bollob\’as many years ago. Recently, Annika Heckel made a breakthrough, establishing a lower bound of $n^{1/4-o(1)}$. She and I have now extended this to $n^{1/2-o(1)}$, almost matching the upper bound.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.