RT Part 6; The Technique of Focusing

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: \mathbb{N} = \{1,2,3, \dots\}.

So the setup is as follows: we want to show that for any natural numbers k and m, there exists some N such that however [N] = {1,2,\dots, N} is k-colored, we are guaranteed that an m-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 m-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 “m-term monochromatic arithmetic progression” so many times, let’s abbreviate this as “m-TMAP”.

The idea is to try to force a m-TMAP to occur.  Say we want to find an N such that when [N] is 2-colored there exists a 2-TMAP.  Well, I’m sure you’ve already figured out that N = 3 works.  2-color {1,2,3} 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 k different-colored (m-1)-TMAPs which are all needing the same last number to be their color to become a m-TMAP.  Since one of the colors had to be chosen, we get a m-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 [330] guarantees a 3-TMAP, say our colors are represented by \bullet and \star.  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 \bullet and the first two in the second AP are \star.  That’ll do it for us.

Well, lets take an intermediate step and show that whenever we 2-color [5], 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 \bullet or we’d have a 3-TMAP.  So it must be a \star, which means it looks like the following, and we once again get what we asked for.

Color [330] arbitrarily.  Since there are 2^5 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 B and B+t.  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 (B+2t)th 5-block.  If it is a \bullet, then the first bullet in the Bth block, the second in the (B+t)th block, and this last one form a 3-TMAP.  If it is a \star 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 t.  So going out at most 2(33\cdot5) =330 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.

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.

7 Responses to RT Part 6; The Technique of Focusing

  1. Z Norwood says:

    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. -_-

  2. JCummings says:

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

    • Z Norwood says:

      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.

      • Z Norwood says:

        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.

  3. Z Norwood says:

    I’m not dismayed that you’ve declared that 0\notin \mathbb{N}. I’m just glad you now accept that the alternative convention is also common.

    Btw, it seems 0\in \mathbb{N} is as common in Cambridge as \subset = \subseteq. The latter irks me infinitely more than the former.

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

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

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