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)$.

I suspect that it will be difficult to do much better than that, but I don't know how to prove it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.