= Solution
Let $N=2^{4d}$ and colour the edges of $K_N$ red and blue. One colour, say red, forms a graph $G$ with
$$
m\geq\frac12\binom N2.
$$
Apply part (a) with
$$
s=d,\qquad k=2^d,\qquad t=2d.
$$
Its positive term satisfies
$$
\frac{(2m)^t}{N^{2t-1}}
\geq
N\left(\frac{N-1}{2N}\right)^{2d}
>2^{2d-1},
$$
while
$$
\binom Nd\left(\frac{2^d}{N}\right)^{2d}
\leq N^d\frac{2^{2d^2}}{N^{2d}}
=2^{-2d^2}.
$$
The difference is at least $2^{d-1}$, so $G$ contains a $(d,2^d)$-rich set of size at least $2^{d-1}$.
The <hypercube graph> $Q_d$ is bipartite according to the parity of the sum of its coordinates. Each part has $2^{d-1}$ vertices, every vertex has degree $d$, and $|Q_d|=2^d$. Part (b) therefore embeds a red copy of $Q_d$. Every red-blue colouring of $K_{2^{4d}}$ has a monochromatic copy, proving
$$
r(Q_d)\leq2^{4d}.
$$
Back to article page
