Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-14/5/ii/solution

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 gives
Again the dependency graph joins intersecting hypergraph edges and has . The assumed degree bound implies
The 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!