Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 17H / b

Let $X$ count copies of the complete graph $K_4$ in $G$. Its expected value is

Write $X$ as a sum of indicator random variable. Indicators for two distinct copies are independent when the copies share at most one vertex, since their edge sets are then disjoint. Pairs sharing two vertices have eleven edges in their union, while pairs sharing three have nine. It follows thatThus $\mathrm{var}(X)/{\mu }^2\to 0$. By the second moment method, $X/\mu \to 1$ in probability, so $\mathbb{P}(X\ge 100)\to 1$. This is the sparse clique-count concentration estimate.

Let $Y$ count unordered pairs of distinct $K_4$ copies that have a common vertex. Classifying such a pair by whether it shares one, two, or three vertices givesIndeed, after substituting $p=n^{-2/3}\log n$, these terms are respectively

The first moment method gives $\mathbb{P}(Y>0)\le \mathbb{E}Y\to 0$. Part (i) says that $X\ge 100$ with probability tending to one, so the union bound shows that, with probability tending to one, both $X\ge 100$ and $Y=0$. On that event any one hundred of the $K_4$ copies are pairwise vertex-disjoint, proving vertex-disjoint sparse clique copies in this case.