Given a countable coloring of the plane, is it always possible to find a monochromatic set of points $\left\{ \left(x,y\right),\left(x+w,y\right),\left(x,y+h\right),\left(x+w,y+h\right)\right\} $ (the corners of a rectangle)?


2 Answers 2


This is equivalent to CH.

Quoting "Problems and Theorems in Classical Set Theory" by Komjath and Totik, chapter 16, Continuum hypothesis:$\DeclareMathOperator{\dist}{dist}$

CH holds if and only if the plane can be decomposed into countably many parts none containing 4 different points $a$, $b$, $c$, $d$ such that $\dist(a,b)=\dist(c,d)$

This is a stronger requirement than your problem, so assuming CH the answer is no. Their solution, assuming CH is false, proves that there's a monochromatic rectangle.

Previous version, with added explanation about Hamel basis:


CH holds if and only if $\mathbf R$ can be colored by countably many colors such that the equation $x+y=u+v$ has no solution with different $x$, $y$, $u$, $v$ of the same color.

This gives a negative answer assuming CH. Explanation: consider $\mathbf R$ as a vector space over $\mathbf Q$. Let $A$ be some basis. Take any bijection $A \to A + A$, where $+$ is the disjoint sum. It induces a linear isomorphism $f:\mathbf R \to \mathbf R \times \mathbf R$. (You can think that there's a linear isomorphism between reals and complexes if that helps.) Then, if you were given a monochromatic rectangle $a=(x_1, y_1)$, $b=(x_1+x_2, y_1)$, $c=(x_1, y_1+y_2)$, $d=(x_1+x_2, y_1+y_2)$, certainly $a+d=b+c$. Using that isomorphism, $f(a)+f(d)=f(b)+f(c)$ gives a monochromatic solution of quoted equation.


Take a look at this site: http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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