Put $k=p^{3p}$. Parts ii and iii give a graph with neither a <clique> nor an <independent set> of size $k$. Its number of vertices satisfies the standard binomial lower bound
$$
\binom{p^3}{p^2}
\geq\left(\frac{p^3}{p^2}\right)^{p^2}
=p^{p^2}.
$$
Consequently the <modular-intersection graph Ramsey lower bound> gives
$$
\boxed{R(k,k)\geq p^{p^2}}.
$$

For every fixed $C>0$,
$$
\log(p^{p^2})=p^2\log p,
\qquad
\log(k^C)=3Cp\log p.
$$
The first quantity exceeds the second when $p>3C$. Thus $p^{p^2}$ is eventually larger than $k^C$ for every fixed $C$, so this lower bound grows faster than every <polynomial> in $k$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 161 / 4 / iv / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/iii/paper-161/4/iv/solution