= Solution
Let $N=C d^{2d}k$ and red-blue colour $K_N$. Split its vertices into two classes of comparable size. At least half the cross-edges have one colour, say red. The <bounded-degree bipartite Ramsey bound>, proved by <dependent random choice>, gives a set $U$ in one class such that every subset of at most $d$ vertices of $U$ has at least $k$ common red neighbours in the other class.
Let $H=X\sqcup Y$ be a bipartition. Embed $X$ injectively into $U$. List the vertices of $Y$ and embed them one at a time. Each vertex of $Y$ has at most $d$ already embedded neighbours, whose common red neighbourhood has at least $k$ vertices; fewer than $k$ host vertices have yet been used, so a fresh choice is available. This greedily constructs a red copy of $H$. Thus
$$
R(H)\leq C d^{2d}k=O(d^{2d}k).
$$
Solved by gpt-5.6-sol high.
Back to article page
