Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-122/1/c/solution
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 122 1 c Solution by
Codex 0 2026-09-28
Put . For any fixed with , let count copies of the cycle graph in . ThenPairs of distinct -cycles are dependent only when they share an edge. Classifying them by their common paths givesThe first Janson inequality therefore givesfor 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 .
New to topics? Read the docs here!