BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:The (non-)concentration of the chromatic number -
Oliver Riordan (University of Oxford)
DTSTART;TZID=Europe/London:20191031T143000
DTEND;TZID=Europe/London:20191031T153000
UID:TALK131377AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/131377
DESCRIPTION:Let $G(n\,1/2)$ be the random graph on $n$ vertice
s in which each edge is present with probability $
1/2$\, independently of the others. A classical qu
estion 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 rec
eive different colours? Of course\, $X_n$ is a ran
dom variable: one main thrust of past work is prov
ing 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 n
owadays standard argument gives an upper bound of
$O(n^{{1/2}})$. Surprisingly\, until very
recently \\emph{no} meaningful lower bounds were\n
known\, although this natural question was raised
by Bollob\\'as many years ago.\nRecently\, Annika
Heckel made a breakthrough\, establishing a lower
bound of\n$n^{{1/4-o(1)}}$. She and I have
now extended this to $n^{{1/2-o(1)}}$\, a
lmost\nmatching the upper bound.\n
LOCATION:MR12
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR