= Solution
We use the following standard off-diagonal Ramsey result from the course: if $F$ is a <forest> on $h-1$ vertices and $K_1\vee F$ is obtained by adjoining a <universal vertex>, then, for $k$ sufficiently large in terms of $h$,
$$
r(K_1\vee F,K_k)\leq C\frac{hk^2}{\log k}.
$$
Its proof combines the $r(K_3,K_k)=O(k^2/\log k)$ bound with an iterative neighbourhood embedding of the forest.
The graph $H_\ell$ in the question is exactly $K_1\vee P_{\ell-1}$, and a path is a <tree>, hence a forest. Substitution of $h=\ell$ gives
$$
R(H_\ell,K_k)\leq C\frac{\ell k^2}{\log k},
$$
as required.
Back to article page
