Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Are you talking about the real plane of the integer plane (grid points)? –  Arthur Nov 22 '12 at 18:08
    
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 –  Amr Nov 22 '12 at 18:10
    
I'm just trying to understand the problem. Does the square have to have sides paralell to the axes? –  Arthur Nov 22 '12 at 18:14
1  
Do you think the way I stated it is not clear ? –  Amr Nov 22 '12 at 18:15
    
Well, with the discrete-tag, and the fact that coloring problems are usually in the grid. No, I didn't think so. –  Arthur Nov 22 '12 at 18:16

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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 –  Andres Caicedo Nov 23 '12 at 7:23
    
@ Gerry Myerson, thank you –  Amr Nov 23 '12 at 11:03

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.