We have talked about Ramsey theory on graphs. But what other structures can we do Ramsey theory on? Well, how about numbers? Remember that the basic idea behind Ramsey theory is to try to guarantee the existence of some sort of “structure” in something by making that something big enough.
For graphs, we colored the edges with colors and proved that if we picked a big enough graph, then we can guarantee that some complete subgraph of a pre-specified size is monochromatic. Using colors is nice because it is an easy way to give the things you are talking about a quality which can be easily generalized (to a property, a structure, a relationship, etc.). This is important because although Ramsey theory is interesting in its own right, it’s always good to build your theory in a way so that it will be useful either in the building of other theory, or as a tool to solve problems.
For instance, in my last post on the Happy Ending Theorem, because of this abstract framework of colorings of graphs, we were able to set up the Happy Ending problem in such a way that we could effortlessly relate the “colors” to the thing we really cared about in that case: a property of triples of points. And since everything is a graph, we were able to use our previous work very nicely.
So as we move onward to doing Ramsey theory on the natural numbers, we stick with considering colorings of them. So all that’s left is to specify what structure we are looking for. We want to choose something that is simple enough that it is applicable and natural (like monochromatic subgraphs), but also interesting and non-trivial.
There are a few pretty good choices. We choose to first look for monochromatic arithmetic progression of a specified length. i.e. if we -color a set of integers, when can we guarantee that a monochromatic arithmetic progression of length exists? So what we do not specify is the common difference of the progression. Any common difference is a candidate. Say we -color the integers from . Can we pick large enough so that no matter how we color them we are guaranteed such a progression?
Or maybe no such exists. Maybe there exists some such that there exists a way to color every positive integer and avoid a monochromatic arithmetic progression of length 100,000,000. It is not obvious to me at least that with, say, 100,000 colors at my disposal, that I can not find a way to color the positive integers to avoid a monochromatic arithmetic progression of length 100,000,000. That is a really long ways to go in a systematic way while using only 1 of your 100,000 colors. It’s the kind of thing where I wouldn’t really be surprised if such a coloring existed. Seems like some coloring based on basic number theory facts has got to work, doesn’t it?
Well, as you may have guessed, no such coloring does exist. There is a Ramsey-type theorem that we will discuss next time that says the we mentioned above always does exist. A pretty cool result.
I will get to this more in a few days. As a quick exercise, notice that 3 paragraphs back I casually asserted that if no such exists, then there must exist a coloring of all of that avoids a monochromatic arithmetic progression of length . First think about why this implication isn’t completely immediate, but then realize that the proof is not too bad at all.