Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, June 07, 2016, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Annika Heckel (University of Oxford)
The chromatic number of the random graph G(n,p) has been an intensely studied subject since at least the 1970s. A celebrated breakthrough by Bollobás in 1987 first established the asymptotic value of the chromatic number of G(n,1/2), and a considerable amount of effort has since been spent on refining Bollobás' approach, resulting in increasingly accurate bounds. Despite this, up until now there has been a gap of size O(1) in the denominator between the best known upper and lower bounds for the chromatic number of dense random graphs G(n,p) where p is constant.
In this talk, I will present new upper and lower bounds which match each other up to a term of size o(1) in the denominator. Somewhat surprisingly, the behaviour of the chromatic number changes around p=1-1/e^2, with a different limiting effect being dominant below and above this value. In contrast to earlier results, the upper bound was obtained through the second moment method, and I will give details on some aspects of the proof.
Automatic MiSe System Software Version 1.4803M | admin login