Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 17H (Graph Theory)

Fix $k\ge 1$ and sample $G$ from the Erdős-Rényi model with $p=\frac{1}{2}{n}^{-2/3}$. Let $X$ count copies of the complete bipartite graph $K_{3,3}$. By the expected subgraph count in the Erdős-Rényi model,

Put $m=\lceil n/k\rceil$ and let $Z$ count independent set of size $m$. If the chromatic number satisfies $\chi (G)\le k$, some colour class has at least $m$ vertices, so $Z\ge 1$. Moreover,because the positive part of the exponent is $O(n)$ whereas $p\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ has order $n^{4/3}$. The first moment method therefore gives $\mathbb{P}(\chi (G)\le k)\le \mathbb{E}Z=o(1)$.

Using Markov inequality for $X$ and the union bound,for all sufficiently large $n$. Hence at least one such $G$ contains no $K_{3,3}$ and has $\chi (G)>k$.

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.