Date
Tue, 04 Jun 2019
Time
14:30 - 15:30
Location
L6
Speaker
Annika Heckel

Further Information

A classic result of Shamir and Spencer states that for any function $p=p(n)$, the chromatic number of $G(n,p)$ is whp concentrated on a sequence of intervals of length about $\sqrt{n}$. For $p<n^{-\frac{1}{2} -\epsilon}$, much more is known: here, the chromatic number is concentrated on two consecutive values.

Until now, there have been no non-trivial cases where $\chi(G(n,p))$ is known not to be extremely narrowly concentrated. In 2004, Bollob\'as asked for any such examples, particularly in the case $p=\frac{1}{2}$, in a paper in the problem section of CPC. 

In this talk, we show that the chromatic number of $G(n, 1/2)$ is not whp concentrated on $n^{\frac{1}{4}-\epsilon}$ values

Please contact us with feedback and comments about this page. Last updated on 04 Apr 2022 15:24.