Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 14 / 1

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$, putThis 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|\le 1$, by the permitted Lipschitz condition.

Here is the required exponential-moment proof of the Azuma-Hoeffding inequality. More generally, suppose $|D_i|\le c_i$ for deterministic $c_i$. Convexity of the exponential function gives, for $-c_i\le d\le c_i$,Taking conditional expectation and using the zero conditional mean yieldsFor the last inequality, integrate $(\log \cosh u{)}^{\prime }=\tanh u\le u$ for $u\ge 0$, and use evenness. A zero $c_i$ simply means a zero increment. Iterated conditional expectation now givesFor $s,t>0$, the strict Markov bound on the event $M_n-M_0>s$ givesThe 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$,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\log 10}$. If $\mu \ge 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$,Here the non-strict one-sided bound follows by the usual non-strict Markov inequality. Consequently the asserted upper bound holds with high probability, uniformly over any sequence $p=p(n)$ satisfying the stated assumption.