= Solution
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$.
Back to article page
