= Solution
Expose the vertices in order, revealing at step $i$ every <edge> from vertex $i$ to an earlier vertex. With the resulting <filtration> $\mathcal F_i$, put
$$
M_i=\mathbb E[\chi(G)\mid\mathcal F_i],\qquad M_0=\mu,\quad M_n=\chi(G).
$$
This is the <vertex exposure for chromatic number> <martingale>. Its increments $D_i=M_i-M_{i-1}$ have <conditional mean> zero and satisfy $|D_i|\leq1$, by the permitted <Lipschitz condition>.
Here is the required exponential-moment proof of the <Azuma-Hoeffding inequality>. More generally, suppose $|D_i|\leq c_i$ for deterministic $c_i$. <Convexity> of the <exponential function> gives, for $-c_i\leq d\leq c_i$,
$$
e^{td}\leq\frac{c_i+d}{2c_i}e^{tc_i}+\frac{c_i-d}{2c_i}e^{-tc_i}.
$$
Taking <conditional expectation> and using the zero <conditional mean> yields
$$
\mathbb E[e^{tD_i}\mid\mathcal F_{i-1}]\leq\cosh(tc_i)\leq e^{t^2c_i^2/2}.
$$
For the last inequality, integrate $(\log\cosh u)'=\tanh u\leq u$ for $u\geq0$, and use evenness. A zero $c_i$ simply means a zero increment. Iterated <conditional expectation> now gives
$$
\mathbb E e^{t(M_n-M_0)}\leq\exp\left(\frac{t^2}{2}\sum_i c_i^2\right).
$$
For $s,t>0$, the strict Markov bound on the event $M_n-M_0>s$ gives
$$
\mathbb P(M_n-M_0>s)<\exp\left(-ts+\frac{t^2}{2}\sum_i c_i^2\right).
$$
The strict inequality follows directly by integrating $e^{t(M_n-M_0)}>e^{ts}$ on that event; it is also immediate if the event is empty. Optimize at $t=s/\sum_i c_i^2$ and apply the same argument to the negative increments. For $c_i=1$ and $s=\lambda\sqrt n$, the <union bound> proves, for every $\lambda>0$,
$$
\boxed{\mathbb P(|\chi(G)-\mu|>\lambda\sqrt n)<2e^{-\lambda^2/2}.}
$$
At $\lambda=0$ the displayed strict bound is trivial.
For the second conclusion write $a_n=n/\log n$ and choose a fixed $C>\sqrt{2\log10}$. If $\mu\geq a_n+C\sqrt n$, then $\{\chi(G)<a_n\}\subseteq\{\chi(G)-\mu<-C\sqrt n\}$, whose <probability> is less than $e^{-C^2/2}<1/10$. Thus the given positive <probability> forces $\mu<a_n+C\sqrt n$. For sufficiently large $n$,
$$
\mathbb P\bigl(\chi(G)\geq a_n+(\log n)\sqrt n\bigr)
\leq\exp\left(-\frac{(\log n-C)^2}{2}\right)\longrightarrow0.
$$
Here the non-strict one-sided bound follows by the usual non-strict <Markov inequality>. Consequently \b[the asserted upper bound holds <with high probability>], uniformly over any sequence $p=p(n)$ satisfying the stated assumption.
Back to article page
