Last time I mentioned that we’d now move from Ramsey theory on graphs to Ramsey theory on the naturals. By popular demand, and to Zach‘s dismay, as decided by a Nebraska Math Department poll last year we will declare that the naturals begin at 1: .

So the setup is as follows: we want to show that for any natural numbers and , there exists some such that however is -colored, we are guaranteed that an -term arithmetic progression exists.

So how do we show existence? Well, like with Ramsey theory on graphs, we will do so constructively. We will attempt to construct an -term arithmetic progression by showing that we are guaranteed that some smaller structure always exists, and that structure implies the larger structure.

Since I don’t want to write “-term monochromatic arithmetic progression” so many times, let’s abbreviate this as “-TMAP”.

The idea is to try to force a -TMAP to occur. Say we want to find an such that when is 2-colored there exists a 2-TMAP. Well, I’m sure you’ve already figured out that works. 2-color in some way. If 1 and 2 are given the same color, then you’re done. If not, then they are given different colors, say 1 is given red, 2 is given blue. But then if 3 is colored red, then 1,3 form a 2-TMAP And if 3 is blue, the 2,3 form one.

Ok, so that was stupid easy. But there is an underlying idea that is important. And that is, once we had stated that the first two colors didn’t form a monochromatic 2-term arithmetic progression, we were able to say that whatever color the third one got, we were guaranteed to get a 2-TMAP. Moreover, and what is really the key idea, is that we had different-colored ()-TMAPs which are all needing the same last number to be their color to become a -TMAP. Since one of the colors had to be chosen, we get a -TMAP. Feels sort of like induction.

This is the idea we want to exploit, and it is called *focusing*. Meaning we are able to “focus” on that last number.

Let’s figure out how to use it to show that any 2-coloring of guarantees a 3-TMAP, say our colors are represented by and . So we want to set it up so that two APs end on the same number, the first two numbers in the first AP are and the first two in the second AP are . That’ll do it for us.

Well, lets take an intermediate step and show that whenever we 2-color , if we do not get a 3-TMAP, then we are at least guaranteed a 3 term AP where either the first two terms are one color and the last term is another color, or the last two are the same and the first is the other. To see this just note that the first three can’t all be the same color, so one has to be different. Up to switching the colors, the three options are:

The first two are already of the desired form, for the second just observe that the fifth number can not be a or we’d have a 3-TMAP. So it must be a , which means it looks like the following, and we once again get what we asked for.

Color arbitrarily. Since there are ways to 2-color a 5-block (i.e. 5 consecutive integers), if we look at the first 33 disjoint 5-blocks, we are guaranteed that two of them look the same. Say blocks and . We just showed that these blocks have one of the three forms above. Without loss of generality, say the pair we just found looks like

We talk about this as a block with “same-same-different”. So now look at the last bit in the th 5-block. If it is a , then the first bullet in the th block, the second in the th block, and this last one form a 3-TMAP. If it is a then all the stars mentioned thus far form a 3-TMAP. It looks like this:

And how long did we have to go out? Well, 33 blocks of length 5, plus at most another chunk of the same size to account for the extra . So going out at most guarantees a 3-TMAP.

Well that was pretty neat-o. It’s the sort of strategy that if you were trying to prove such a result as this one, you would probably try eventually. But how far it can take us is rather surprising. In the next post we will investigate just that.

I should probably mention that the next several posts will be very close to a few lectures given by Imre Leader at the 2011 Memphis-Budapest Summer School in Combinatorics. Most posts thus far have come from various sources including his lectures, West‘s book, and Wikipedia.

All: When you write a new post, please add it to the Site Map. It appears there’s no way to make WordPress do this automatically. -_-

How does one do that? And what does that do for us?

Just edit the ‘Site Map’ page and append a link to your new post (I’ve already done this for this post, RT6) to the appropriate list. (Now that I think of it, you and I might be the only authors able to do this… Hotovy et al: Try to edit the ‘Site Map’ page (just stick a smiley face at the bottom or something) and see if you’re successful.)

It gives us a page with links to all the posts, organised by category. (More for our readership than for ‘us’, I guess.) At the rate you’re posting, we’re going to have 67 posts in ‘Combinatorics’ soon, and it’s not easy to find things when you’re forced to sort through the WP-generated ‘Combinatorics’ category page.

Also, WP doesn’t automatically sort posts in the category pages by subcategory or subsubcategory, which is annoying. AND it forces those few-line previews on you, so you can only see a few post headings at once.

I’m not dismayed that you’ve declared that . I’m just glad you now accept that the alternative convention is also common.

Btw, it seems is as common in Cambridge as . The latter irks me infinitely more than the former.

Pingback: RT Part 7; Van Der Waerden’s Theorem | whateversuitsyourboat

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