There is a reasonably well-known problem:
Given a plane with each point colored one of k colors, show there is a rectangle whose vertices are all of the same color, whose axes are parallel to the x- and y- axes
A solution to this problem is to consider points in $\{0, 1, \ldots, k\} \times \{0, \ldots, \frac{k^2(k+1)}{2}\}$. From each row $\{0, \ldots, k\} \times \{j\}$ pick a pair $(a_j, j), (b_j,j)$, with $a_j
This actually proves something stronger, namely that there is a set of $\frac{k^4}{2}+k^3+\frac{k^2}{2}+k+1$ points that must contain vertices of a rectangle, oriented with the coordinate axes, which are all of the same color. It's also pretty clear that the $\frac{k^2(k+1)}{2}$ can't be improved upon with this method.
On the other hand, the method seems inefficient, at least for large k. So my question is: Can one do better than $O(k^4)$? More explicitly, do there exist sets, of size $o(k^4)$, such that for any coloring of the plane with $k$ colors, the $k$-th such set must contain the vertices, all of the same color, of a rectangle whose sides are parallel to the coordinate axes? And if so, what is the best (known) number of points.