Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 1 / c

Put $p=C{n}^{-3/4}$. For any fixed $U\subseteq [n]$ with $|U|\ge 3n/5$, let $X_U$ count copies of the cycle graph $C_4$ in $G[U]$. ThenPairs of distinct $4$-cycles are dependent only when they share an edge. Classifying them by their common paths givesThe first Janson inequality therefore givesfor an absolute $c>0$ and all sufficiently large $n$. Choose $C$ so that $c{C}^4>\log 2+1$. A union bound over the at most $2^n$ choices of $U$ shows that, with high probability, every set of at least $3n/5$ vertices contains a $C_4$.

Now greedily choose vertex-disjoint $4$-cycles until none remains. If fewer than $n/10$ were chosen, they would cover fewer than $2n/5$ vertices, leaving more than $3n/5$ vertices and hence another $C_4$. This contradiction proves that the greedy packing contains at least $n/10$ vertex-disjoint copies.