Finding monochromatic rectangles in a countable coloring of R^2 - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T01:53:40Z http://mathoverflow.net/feeds/question/273 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/273/finding-monochromatic-rectangles-in-a-countable-coloring-of-r2 Finding monochromatic rectangles in a countable coloring of R^2 Ian H 2009-10-11T11:33:00Z 2009-12-28T20:33:50Z <p>Given a countable coloring of the plane, is it always possible to find a monochromatic set of points {(<em>x, y</em>), (<em>x+w, y</em>), (<em>x, y+h</em>), (<em>x+w, y+h</em>)} (the corners of a rectangle)?</p> http://mathoverflow.net/questions/273/finding-monochromatic-rectangles-in-a-countable-coloring-of-r2/292#292 Answer by sdcvvc for Finding monochromatic rectangles in a countable coloring of R^2 sdcvvc 2009-10-11T17:30:01Z 2009-10-12T07:58:52Z <p>This is equivalent to CH.</p> <p>Quoting "Problems and Theorems in Classical Set Theory" by Komjath and Totik, chapter 16, Continuum hypothesis:</p> <blockquote> <p>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)</p> </blockquote> <p>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.</p> <p><hr /></p> <p>Previous version, with added explanation about Hamel basis:</p> <p>Using </p> <blockquote> <p>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.</p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/273/finding-monochromatic-rectangles-in-a-countable-coloring-of-r2/9978#9978 Answer by Vincent for Finding monochromatic rectangles in a countable coloring of R^2 Vincent 2009-12-28T20:33:50Z 2009-12-28T20:33:50Z <p>Take a look at this site: <a href="http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html" rel="nofollow">http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html</a></p>