Consider the following theorem:
For any finite coloring of NxN there exists
a square such that all corners are the same color.
There are several proofs of this:

This can be proven from the HalesJewitt theorem.
(Advantage: automatically get out the full
GallaiWitt theorem with this approach.)

This can be proven from the GallaiWitt theorem trivially.

This can be proven by using VDW theorem on the diagonal.

This can be proven by using VDW theorem on the side.

This can be proven by directly.
It has a VDW flavor to it but can be shown to HS students
who have not seen VDW theorem (I've done it).
The following theorem can be proven from the
polynomial HalesJewitt Theorem:
For any finite coloring of NxN there exists an s &ge 2
and an s by s^{2}
rectangle such that all corners are the same color.
I have tried to prove this from scratch, from Poly vdw theorem,
from GallaiWitt, from ordinary HalesJewitt.
Have not managed it.

Is there a proof either from scratch, from poly vdw, or from Ordinary HJ?
If so then please comment.

Normally one asks for an elementary or (I prefer the phrase)
purely combinatorial.
Even so, I can't rephrase my question with this term
since there is a purely combinatorial proof of
Poly HalesJewitt. (See either
Walters paper
or
the rough draft of the book on VDW stuff I am coauthoring with Andy Parrish
pages 7789.)
Very neat problem...rjlipton
ReplyDeleteI have a meeting in a minuteso this may be very half baked. Did you try using the polynomial method. Its likely you might be able to write down a polynomial for each prime p so that counts the number nonsolutions mod p. Then, use ChevalleyWarning and Ax to get a contradiction....there will be too many nonsolutions...dick
ReplyDeleteHi Bill,
ReplyDeleteNice problems... in both, do you mean axisparallel?
YES in both problems I DO mean
ReplyDeleteaxisparallel. Though axisnotnecc parallel might be a good problem also.
The axisparallel problem proofs
lead to VDW_type large bounds
on things. the axisnotneccparallel
might lead to much smaller numbres.
But for now, lets solve THIS problem.
Bill, that seems closed minded to demand first a solution to exactly the problem you asked. Doesn't math teach us that the best way to solve a problem is often to solve a different problem first and then get the desired result as a corollary? Perhaps there's a really neat way to force a rotated n by n^2 rectangle which we could generalize to get one parallel to the axes.
ReplyDeletesatisfy condition В of Theorem В and. (ii) {pv2}v is bounded away from one. Proof: From condition (i) and Theorem B, Sx2lsx * 1. Now we can write sxs. 2„ 2 ...
ReplyDeleteAndy Parrish is, of course,
ReplyDeletecorrect solving the
nonnessaxisparallel may lead to insights for the problem I am asking about.
OKAY SOMEONE please solve.
Bill  this is an interesting problem. Can you describe in your own language the intuition behind: 1) the direct proof of s x s, 2) the combinatorial extension of HJ to poly HJ?
ReplyDeletenever mind, I found the information from Bill's post here: http://lucatrevisan.wordpress.com/2007/01/26/themultidimensionalpolynomialvanderwaerdentheorem/
ReplyDeleteI love this problem!