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(\sigma )|$ over the finite collection of permutations. At least one value is as large as its average. By part (e), the corresponding $S(\sigma )$ is an independent set, soHere $\alpha (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.