19
$\begingroup$

Color every point in the real plane using the colors blue,yellow only. It can be shown that there exists a rectangle that has all vertices with the same color. Is it possible to show that there exists a square that has all vertices with the same color ? If it is not possible, please give me an example of a coloring of the real plane that does not have monochromatic squares.

To give the viewers an idea about other similar results (which they might find useful), for any coloring (2 colors) of the real plane:

1) There exists three collinear points having the same color, such that one of the points is the midpoint of the line segment that joins the other two.

2)For any two angles $\theta,\phi$ there exists a monochromatic triangle that has angles $\theta,\phi,180-(\theta+\phi)$

3)For any angle $\theta$, there exists a monochromatic parallelogram with angle $\theta$

Now its natural to ask if there are any monochromatic squares.

Thank you

$\endgroup$
  • $\begingroup$ Are you talking about the real plane of the integer plane (grid points)? $\endgroup$ – Arthur Nov 22 '12 at 18:08
  • 1
    $\begingroup$ I am talking about the real plane. The stronger version is for grid points. If you have a solution to the grid points please post it as an answer. It ll also be a solution to my problem $\endgroup$ – Amr Nov 22 '12 at 18:10
  • $\begingroup$ I'm just trying to understand the problem. Does the square have to have sides paralell to the axes? $\endgroup$ – Arthur Nov 22 '12 at 18:14
  • 1
    $\begingroup$ Do you think the way I stated it is not clear ? $\endgroup$ – Amr Nov 22 '12 at 18:15
  • $\begingroup$ Well, with the discrete-tag, and the fact that coloring problems are usually in the grid. No, I didn't think so. $\endgroup$ – Arthur Nov 22 '12 at 18:16
10
$\begingroup$

Molina, Oza, and Puttagunta, Sane bounds on Van der Waerden-type numbers, write,

The following is known: no matter how the lattice points of a coordinate plane are colored red and blue, there exists a square whose corners are the same color (a monochromatic square). In fact, using more than just two colors will still guarantee a monochromatic square (one whose vertices are the same color). So for all $c$ (the number of colors), there is a number $G(c)$ where all colorings with $c$ colors of the lattice points of a $G(c) \times G(c)$ grid will contain a monochromatic square. Unfortunately, the necessary number of points is unknown, but bounds are known. These bounds are enormous (roughly $G(c)\le2^{2^c}\times2^{2^{2^{2^{2c}}}}$).

The references they cite are

  1. W. Gasarch, C. Kruskal, and A. Parrish. Van der Waerden’s theorem: Variants and applications. [But the Chapter that is supposed to be about "The Square Theorem" isn't there]

  2. R. Graham, B. Rothchild, and J. Spencer. Ramsey Theory. Wiley, 1990.

  3. B. Landmann and A. Robertson. Ramsey Theory over the integers. AMS, 2003.

$\endgroup$
  • 1
    $\begingroup$ The following slides of a talk are also relevant (Listed as work in progress on Gasarch's page): "Rectangle Free Colorings of Grids" (with Fenner, Glover, and Purewal) cs.umd.edu/~gasarch/papers/gridtalk.pdf $\endgroup$ – Andrés E. Caicedo Nov 23 '12 at 7:23
  • $\begingroup$ @ Gerry Myerson, thank you $\endgroup$ – Amr Nov 23 '12 at 11:03
2
$\begingroup$

The case for mono-color squares in a 2-colored grid has been solved:

  • An infinite $13$-wide strip of grid can be colored to avoid mono squares
  • a $14{\times}14$ grid can be colored to avoid mono squares
  • a $14{\times}15$ grid must contain a mono-colored square

R Bacher and S Eliahou: Extremal binary matrices without constant 2-squares

A version of a $14{\times}14$ grid without a mono-colored square is shown, adapted from an image in the paper:

enter image description here

$\endgroup$
  • $\begingroup$ Note that this is for the version of the problem where we only consider squares parallel to the axes; in fact, the picture you gave has many monochromatic squares of the form (i,j), (i+3, j+2), (i+1, j+5), (i-2, j+3). For the version where we consider all squares (see the comments of the original post), the impossibility result you quote still stands, but it might be impossible even on some smaller grids. $\endgroup$ – Ravi Fernando Jan 7 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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