RT Part 7; Van Der Waerden’s Theorem

Last time we saw how we can use the technique of focusing to show that however one 2-colors [330], there always exists a 3-term, monochromatic arithmetic progression.  As with last time, let’s abbreviate “k-term monochromatic arithmetic progression” as “k-TMAP”.  We now want to see how we can expand our previous work to more colors.  Let’s think about trying to guarantee a 3-TMAP when three colors are used.

I won’t work out all the details because it’s fairly similar to what we did last time.  But we should at least recognize how the two cases are different.

Similar to last time, when a block of length 7 is three-colored, if there is no 3-TMAP then there must be an AP where the first two terms are one color, and the third is another.  We will refer to this as the “same-same-different pattern”.  For instance, using \bullet, \star, and  * as our colors, a same-same-different may look like this

Since there are 3^7 ways to 3-color a 7-block (an m-block is a block of length m), among the first 3^7+1 such blocks there must be two which are exactly the same.  Assume they are k blocks apart.  Since every 7-block has the same-same-different property, our picture looks something like this:

Note that if the last dot in the picture was color \bullet or \star, we would get a 3-TMAP.  So, assume that it is a different color, say *.  Now stop for a minute and think about how we may proceed.  We can’t really say anything helpful about what that last block will look like….

Well, we still want to try to use this awesome technique of focusing.  And how it works is that you want to set it up so that all the colors have a 2-term arithmetic progression in their color, and each of these need the same bit to be their color to expand it to a 3-TMAP.  It would be helpful to be able to say more about that last block.

But again, there is no guarantee that it looks like anything we want.  It seems much more difficult to guarantee that there are three blocks that look alike which are equally spaced between each other.  The “equally spaced” is the tough part, and it is crucial in order to guarantee an arithmetic progression.

[pause for a moment and think you how you might try to fix this problem.]

Did you get it?  If you were thinking about generating lots and lots of blocks and then showing that there must be three out of those gazillion which are equally spaced, then….. fine….. that might work….. but it’s really inefficient and also difficult to work out.  And later on we’ll be interested to see how fast these Ramsey numbers are growing.  So we want to find the best bound that we can.  And once you think about it, it becomes clear that even on the scale of inefficiency that we are about to see, that is a very inefficient approach.

So how else can we do it?  Well (and this may not seem efficient at all), above we have a B-block (B is defined in the underscore above).  And there are (only?) 3^B ways to color such as block.  So we can do what we did before and go out far enough in order to guarantee that two of these huge blocks look the same.  We get a picture like this:

where the first two large boxes are copies of the same B-block.  And we know that any B-block has the properties we showed in our first long picture above.  So without loss of generality, assume that it looks exactly like our first picture.

In this picture above we only emphasized the important bits that will be used for focusing.  The three big boxes shown have many more B-blocks between them, and the third we have asserted nothing about it yet except that, by choice, its distance from the middle B-block is the same as the distance between the first and the second B-blocks.  Then, just like in the last post, you can see that the last bit shown must complete a monochromatic AP of length 3.

Cool!  So how much damage did this approach incur?  Well, in the worst case scenario (which is what we’re interested in), we would have to go out

2B(3^B+1) = 2\cdot 2 \cdot 7(3^7+1)(3^{2\cdot 7(3^7+1)}+1).

Ouch.

And with a little thought you can probably convince yourself that we could iterate this general process to find a bound on any finite number of colors and any finite AP length.

For instance, for length 3 APs using 4 colors, you can show that the required length is roughly

In general, iterating with k colors we can find a bound of

where the tower of k‘s has height k.

Therefore doing this process again and again and so on down the road, we get the following.

Van der Waerden’s Theorem.

For all m,k \in \mathbb{N} there exists and n such that whenever [n] is k-colored there exists a monochromatic arithmetic progression of length m.

\square

Addition:  I discovered a nice topological proof of this result on another blog.  Check it out!

Next time we’ll discuss how fast these Ramsey numbers are growing.  After that we’ll play m-in-a-row tic-tac-toe with arbitrarily many colors in arbitrarily many dimensions.  But I won’t get to it until the end of the quarter, probably.  In the mean time, read some measure theory.

Advertisements

About Jay Cummings

I am a fifth year mathematics Ph.D. student at UCSD.
This entry was posted in Combinatorics, Ramsey Theory. Bookmark the permalink.

3 Responses to RT Part 7; Van Der Waerden’s Theorem

  1. Pingback: RT Part 8; Hales-Jewett and how to make Tic-Tac-Toe Interesting | whateversuitsyourboat

  2. Pingback: Hales-Jewett Theorem | YAMB

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s