High probability range of chromatic number Prove that there is an absolute constant $c$, for every $n>1,$ there is an interval $I_{n}$ of at most $c \sqrt{n} /$ log $n$ consecutive integers such that the probability that the chromatic number of $G(n, 0.5)$ lies in $I_{n}$ is at least 0.99.
(From Noga Alon, Joel H. Spencer - The Probabilistic Method-Wiley (2016))
I tried use the Azuma's inequality with vertex/edge exposure martingale, but the  can not be a constant in this way. I think I need a special martingale construction to solve it.
 A: I wrote this solution when I worked through this amazing book about a year ago!
Let $\epsilon > 0$ be arbitrary for the moment. We describe three events that each happen with probability at least $1-\epsilon$ for large $n$.
Given $G\sim G(n,1/2)$, let $u$ be the smallest positive integer such that
\begin{equation}
    \mathbb{P}(\chi(G) \leq u) \geq \epsilon.
\end{equation}
The minimality of $u$ implies that
\begin{equation}
    \mathbb{P}(  \chi(G) \geq u ) = 1- \mathbb{P}(  
    \chi(G) \leq u -1 ) > 1 - \epsilon,
\end{equation}
so that with high probability, we will need at least $u$ colors to properly color $G(n,1/2)$.
Let $Y(G)$ be the minimal size of a subset $S$ of $V(G)$ such that $\chi(G-S)=u$. If we examine $Y(G)$ using the vertex exposure martingale, then it is clear that $Y$ is vertex--Lipschitz: the exposure of each vertex may increase $Y$ by at most one. Thus we can apply Azuma's Inequality to conclude that
\begin{align}
    \mathbb{P}(Y\leq \mu - \lambda\sqrt{n-1})& < e^{-\lambda^2/2}\\
    \mathbb{P}(Y\geq \mu + \lambda\sqrt{n-1})& < e^{-\lambda^2/2}.
\end{align}
We pick $\lambda  = \lambda(\epsilon)$ such that $e^{-\lambda^2/2} = \epsilon$. Now, we have selected $u$ such that $\mathbb{P}(Y=0)  = \mathbb{P}( \chi(G)\leq u ) > \epsilon$, so the first of the two bounds says that we must have $\mu \leq\lambda\sqrt{n-1}$. Then the second bound becomes
\begin{equation}
    \mathbb{P}(Y\geq 2\lambda\sqrt{n-1}) \leq \mathbb{P}(Y\geq \mu +\lambda\sqrt{n-1}) < e^{-\lambda^2/2}=\epsilon.
\end{equation}
That is, with probability $1-\epsilon$, there is some set $S$ of size $2\lambda \sqrt{n}$ so that $\chi(G-S)=u$.
Observe that $G[S] \sim G(|S|, 1/2)$. Bollob'as showed that a.a.s. $\chi(G(n,1/2)) \leq \frac{n}{\ln n}$, so for large $n$,  with probability at least $1-\epsilon$ we can color $G[S]$ with, say, at most $2 \lambda \frac{\sqrt{n}}{\ln  \sqrt{n}}=4\lambda\frac{\sqrt{n}}{\ln n} $ colors. So with probability at least $1-3\epsilon$, the following all hold:

*

*$\chi(G) \geq u$.

*There is an $S$ with $|S| \leq 2\lambda \sqrt{n}$ such that

*$\chi(G\setminus S) = u$, and

*$\chi(S) \leq 4 \lambda \frac{\sqrt{n}}{\ln n}$.

The above conditions imply that with probability $1-3\epsilon$ we have that $u \leq \chi(G) \leq u + 4\lambda \frac{\sqrt{n}}{\ln n}$, where $\lambda$ depends only on $\epsilon$. Set $\epsilon = 1/300$ so that with probability at least $0.99$ we have that $\chi(G)$ lies in an interval of size of order $4\lambda \frac{\sqrt{n}}{\ln n}$.
Note The result by Bollobas on the chromatic number is also given somewhere in the book.
