Question

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

Answer 1

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.

Answer 2

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