BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The (non-)concentration of the chromatic number - Oliver Riordan (
 University of Oxford)
DTSTART:20191031T143000Z
DTEND:20191031T153000Z
UID:TALK131377@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:Let $G(n\,1/2)$ be the random graph on $n$ vertices in which e
 ach 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 adjac
 ent vertices receive different colours? Of course\, $X_n$ is a random vari
 able: 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$ pr
 ecisely\, can we bound how much it varies? A nowadays standard argument gi
 ves an upper bound of $O(n<sup>{1/2}</sup>)$. Surprisingly\, until very re
 cently \\emph{no} meaningful lower bounds were\nknown\, although this natu
 ral question was raised by Bollob\\'as many years ago.\nRecently\, Annika 
 Heckel made a breakthrough\, establishing a lower bound of\n$n<sup>{1/4-o(
 1)}</sup>$. She and I have now extended this to $n<sup>{1/2-o(1)}</sup>$\,
  almost\nmatching the upper bound.\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR