Let $N=\lceil k^{1+\epsilon}\rceil$ and red-blue colour $K_N$. One colour class gives a graph $G$ with
$$
m=e(G)\ge\frac12\binom N2\ge c_0N^2.
$$
Apply part (a) with $s=d$, the common-neighbour target equal to $k$, and an integer
$$
t>\frac{(1+\epsilon)(d-1)}\epsilon.
$$
The first term in its hypothesis is at least $c_1^tN$. The error term satisfies
$$
\binom Nd\left(\frac{k}{N}\right)^t
\le N^d\left(\frac{k}{N}\right)^t
=N\,k^{(1+\epsilon)(d-1)-\epsilon t}
=o(N).
$$
Since $N/k=k^\epsilon\to\infty$, the difference is at least $k$ for all sufficiently large $k$, depending only on $d$ and $\epsilon$. Part (a) therefore gives a $(d,k)$-rich set of size at least $k$, and part (b) embeds $H$ in this colour. Hence
$$
\boxed{r(H)\le k^{1+\epsilon}}
$$
for sufficiently large $k$.


Solution

Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 3 / c / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/iii/paper-132/3/c/solution