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 K_4, 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 K_6 yields a monochromatic triangle.

To see why this is true, we give K_6 an arbitrary coloring and prove why there must exist monochromatic triangle.  Pick any vertex of the graph, like vertex x below.  x 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 a, b or c 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 K_5 which does not have a monochromatic triangle to prove that K_6 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 K_6.  What about when we 2-color the edges of a graph that is not complete?  When must a monochromatic K_3 exist?  Again, if that graph contains a K_6 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 K_4?  Or K_5?  Or K_{N+1} where N 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 N such that the complete graph K_N on N vertices has a monochromatic K_{100000} 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 K_3 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 m-in-a-row tic-tac-toe with arbitrarily many colors in arbitrarily many dimensions, sparse Ramsey theory, and maybe some probabilistic techniques.

Advertisements

About Jay Cummings

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

8 Responses to Hello! / Intro to Ramsey Theory

  1. soffer801 says:

    Four things:
    1. https://whateversuitsyourboat.wordpress.com/feed/ is a link to your rss feed that you can copy into an RSS-aggregator
    2. There’s a way to embed images, instead of just linking to them.
    3. Typo $\latex …$. Get used to them. This happen all the damn time.
    4. This is so awesome.

  2. znorwood says:

    Excellent! I’m taking a Ramsey Theory course this term. =^]

  3. JCummings says:

    Thanks Andy! It’ll get more interesting, of course. I particularly like sparse Ramsey theory. If you haven’t seen that yet, stay tuned! :-) There’re also some cool results using probabilistic methods, but I might want to blog about those techniques first. Not sure.

    Zach – Are you taking it from Imre Leader? I sure hope so!

    Andy or Zach – Do you know how to embed the images? Late last night I looked for a little bit and was told that I might need a plugin, but it wasn’t clear how to get that plugin, as I think the dashboard has changed recently.

    • soffer801 says:

      I haven’t seen it, am interested, and will stay tuned. You guys are in my RSS feed now, so I’ll be sure not to miss anything.

      You should be able to just upload an image into the post. as one of the formatting options it gives you. You definitely don’t need any plugins

      So there’s a difference between WordPress and WordPress.com. WordPress is a blogging software. WordPress.com, what we’re both using, is a site that gives you most of the software for free. They block certain things though. Two of those things are plugins, and customizing themes.

    • Z Norwood says:

      soffer801 is right. But you should try PNGs or JPEGs or something, not PDFs.

  4. Pingback: Ramsey Theory Part 2; RT on Infinite, Colorful Graphs | whateversuitsyourboat

  5. Pingback: RT Part 9; Sparse Ramsey Theory | 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