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)?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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:
Using
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.
$\begingroup$
$\endgroup$
Take a look at this site: http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html
