Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-122/1/c/solution

Put . For any fixed with , let count copies of the cycle graph in . Then
Pairs of distinct -cycles are dependent only when they share an edge. Classifying them by their common paths gives
The first Janson inequality therefore gives
for an absolute and all sufficiently large . Choose so that . A union bound over the at most choices of shows that, with high probability, every set of at least vertices contains a .
Now greedily choose vertex-disjoint -cycles until none remains. If fewer than were chosen, they would cover fewer than vertices, leaving more than vertices and hence another . This contradiction proves that the greedy packing contains at least vertex-disjoint copies.

New to topics? Read the docs here!