# Optimal sets for plane coloring problem

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<b_j$, of points that are of the same color, which must exist by pigeonholing. Since there are only $\frac{k(k+1)}{2}$ possible choices for $(a_j,b_j)$, for some pair $(a,b)$ there are at least $k+1$ values of $j$ such that $(a,b)=(a_j,b_j)$. Since there are $k$ colors, some pair $(j_1,j_2)$ of distinct values of $j$ among these have $(a,j_1)$ and $(a,j_2)$ of the same color, and the desired rectangle has vertex set $\{a,b\} \times \{j_1, j_2\}$.

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.

You can achieve $O(k^3)$ using the same method by using more than $k+1$ points per row. A row of $k+x$ points must contain at least $x$ pairs of identical colours, so $n$ such rows contain $nx$ such pairs. In rows of $k+x$ points, there are $(k+x)(k+x-1)/2$ different pair positions, and each can be coloured with $k$ colours. Thus two pairs in the same position are guaranteed to have the same colours if $nx\gt k(k+x)(k+x-1)/2$. With $n=k(k+x)(k+x-1)/(2x)$, the total number $n(k+x)$ of points is $k(k+x)^2(k+x-1)/(2x)$, and minimizing this with respect to $x$ for large $k$ yields $x=k/2+O(1)$ , so the minimal number of points required is $\left(\frac32k\right)^3+O(k^2)$.