Hello! / Intro to Ramsey Theory

If you observe a group of 20 children playing outside, you may notice that you can always find either a group of 4 of them, each of which is friends with the other 3, or you can find a group of 4 of them, none of which is friends with the other 3.  There is always a group of 4 friends, or 4 strangers.  This may seem like an interesting sociological phenomenon.  However the reason for this does not lie in the cerebral cortex or because of an evolutionary advantage to form small, dependent tribes.  It lies in Ramsey theory and is the topic of my first series of blog posts.

So hello!  And welcome to my first blog post!  Similar to my other blog-mates, I plan on using this blog as a way to force myself to articulate and think about math topics which I find fun and interesting.  I am particularly interested in combinatorics and graph theory and the interaction between these fields and analysis and linear algebra.  I also like to think about math education and math in the “real world”.  So I anticipate the majority of my posts to be related to those topics.

As I just mentioned, I will start off with a fun topic that is easy to latch on to: Ramsey theory; named after the very impressive work that Frank Ramsey accomplished before his untimely death at the age of 26.  I will probably have 7 or 8 posts on this topic.  In the last paragraph of this post is a partial list of what I hope to cover.  This post will be a quick introduction to the theory.  So here we go!

Ramsey theory is one of the few areas of math that has a nice philosophical question behind it.  The underlying question is: “Does there exist complete randomness?”  A little more concretely:  “Can something have absolutely no structure to it?”  Maybe more to the point: “If a set of random stuff is big enough, can we always find some sort of structure within it?”  This is the sort of question that Ramsey theory attempts to model and answer.

The first example in Ramsey theory is typically 2-coloring the edges of a graph.  So say with have , the complete graph on 4 vertices, and we color each edge of this graph either red or blue.  One type of structure that we might look for is a monochromatic triangle, i.e. a triple of vertices where all three edges between these vertices are colored red or all three edges are colored blue.

It’s not too hard to see, however, that such a triangle does not have to exist.  It of course could exist, like the blue triangle in this coloring:

But it need not.  For instance, this coloring does not give a monochromatic triangle:

What we are after is a graph big enough that we always get a red triangle or a blue triangle, no matter how we color it.  Is there a complete graph large enough so that every coloring must include a monochromatic triangle?  The answer is yes.  Any coloring of the edges of a yields a monochromatic triangle.

To see why this is true, we give an arbitrary coloring and prove why there must exist monochromatic triangle.  Pick any vertex of the graph, like vertex below.   is incident with 5 edges.  Among these, at least three must be the same color, say red.

Now, one of two things is going to happen.  Either one of the edges between two of , or is also red, in which case we are guaranteed a red triangle:

Or all of these edges are blue, and hence we get this blue triangle:

That’s it!  Either way we get a monochromatic triangle.  Now try to find a coloring of which does not have a monochromatic triangle to prove that is the smallest complete graph which does the job.

The common way that this result is presented in combinatorics texts is this:   Among any 6 people, there are either three people who mutually know each other, or 3 people who mutually do not know each other.  And now we see some motivation for why the “sociological phenomenon” mentioned above holds.

This property of having a monochromatic triangle extends to larger complete graphs since any such graph contains a copy of .  What about when we 2-color the edges of a graph that is not complete?  When must a monochromatic exist?  Again, if that graph contains a as a subgraph then we know that we can find one.  But must that condition hold?  This is a very interesting question that I will return to in a later post.

What about if we want to find a monochromatic ?  Or ?  Or where is the largest positive integer that you can think of?

Well, it turns out that if you choose a large enough graph to color, you can always guarantee the existence of any size of monochromatic subgraph that you choose.

So we are starting to guarantee that we can find a lot of structure in our colored graphs.  Asserting that there exist an such that the complete graph on vertices has a monochromatic no matter which of the obscenely many ways to color it that you choose, doesn’t seem like quite as obvious a fact as the case probably seemed.

In the next post we will discuss what happens when you use more than 2 colors, or when the graph you are coloring has infinitely many vertices.  Eventually we will look at Ramsey theory on the integers, the technique of focusing, the growth of Ramsey numbers, playing -in-a-row tic-tac-toe with arbitrarily many colors in arbitrarily many dimensions, sparse Ramsey theory, and maybe some probabilistic techniques.