Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-14/5/ii/solution
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 14 5 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For each hypergraph edge , let be the event that one of its two colours occupies more than vertices. By colour symmetry and the union bound, the preceding calculation givesAgain the dependency graph joins intersecting hypergraph edges and has . The assumed degree bound impliesThe symmetric Lovász local lemma gives positive probability that no occurs. Thus there is a two-colouring in which each colour occupies at most vertices of every hypergraph edge. Equivalently, both colour counts in every hypergraph edge lie between and ; no rounding difficulty arises because the counts are integers and the bad events use strict inequalities.
New to topics? Read the docs here!