Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

up vote 9 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:

Using

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|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
add comment

Your Answer

 
discard

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.