MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|cite|improve this question
up vote 11 down vote accepted

This is equivalent to CH.

Quoting "Problems and Theorems in Classical Set Theory" by Komjath and Totik, chapter 16, Continuum hypothesis:

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 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 R as a vector space over Q. Let A be some basis. Take any bijection A -> A + A, where + is disjoint sum. It induces a linear isomorphism f: R -> R * 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=(x1, y1), b=(x1+x2, y1), c=(x1, y1+y2), d=(x1+x2, y1+y2), certainly a+d=b+c. Using that isomorphism, f(a)+f(d)=f(b)+f(c) gives a monochromatic solution of quoted equation.

share|cite|improve this answer
Could you explain what you mean by "use Hamel basis to represent R as R+R"? – Ian H Oct 11 '09 at 23:46
Thank you for the clear explanation. – Ian H Oct 12 '09 at 8:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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