Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-14/1/solution
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 14 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Expose the vertices in order, revealing at step every edge from vertex to an earlier vertex. With the resulting filtration , putThis is the vertex exposure for chromatic number martingale. Its increments have conditional mean zero and satisfy , by the permitted Lipschitz condition.
Here is the required exponential-moment proof of the Azuma-Hoeffding inequality. More generally, suppose for deterministic . Convexity of the exponential function gives, for ,Taking conditional expectation and using the zero conditional mean yieldsFor the last inequality, integrate for , and use evenness. A zero simply means a zero increment. Iterated conditional expectation now givesFor , the strict Markov bound on the event givesThe strict inequality follows directly by integrating on that event; it is also immediate if the event is empty. Optimize at and apply the same argument to the negative increments. For and , the union bound proves, for every ,At the displayed strict bound is trivial.
For the second conclusion write and choose a fixed . If , then , whose probability is less than . Thus the given positive probability forces . For sufficiently large ,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 satisfying the stated assumption.
New to topics? Read the docs here!