 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/probability-and-computing/2/g/solution

The expectation from part (f) is the average of

∣ S (σ) ∣

over the finite collection of permutations. At least one value is as large as its average. By part (e), the corresponding

S (σ)

α (G) \geq i = 1 \sum n \frac{1}{d _{i} + 1} .

Here

α (G)

is the independence number. Since its value is an integer, one can equivalently round the right side up with the ceiling function. This application of the probabilistic method is the Caro-Wei bound.

 New to topics? Read the docs here!