RT Part 9; Sparse Ramsey Theory

Well folks, this is it.  This will be the last Ramsey theory-focused post for awhile, I’m guessing.  At least we’re ending on a nice round number!

And I hope you agree that we are ending on a nice topic.  It’s one of my favorites because it says that some of my early intuition with Ramsey theory was wrong, or at least incomplete.  This post is really more of a survey of the theory.

From the first post in this sequence we know that whenever K_6 is two-colored (i.e. we color the edges), we are guaranteed that a monochromatic triangle exists.  We write this as K_6 \rightarrow K_3.  So what does this tell us about the triangles in K_6?  Well, in some sense, we might interpret this as saying that the triangles are “dense enough”.  We have just two many within a small area and that is what guarantees a monochromatic triangle.

So if we want to guaranteed the existence of a monochromatic triangle whenever we two color the edges of a graph G (i.e. that G \rightarrow K_3), what we need to find is a pocket of G which is dense with triangles.  i.e. we want G to contain a copy of K_6, right?

Wrong!  That’s pretty much the intuition that I had.  I thought that maybe you could get away with a little less but I had in the back of my mind that the density was in the end what was important.

Well, turns out that there exists a G such that G \rightarrow K_3 and K_6 \not\subseteq G!  (\subseteq means “is a subgraph of”)  For example, let G be the graph K_{10} with a 9-cycle removed.  Then G \rightarrow K_3 but does not contain a K_6 subgraph.

A minimal characterization was given by Ron Graham in 1968.

Ok.  So K_6 is not some magical edge density that must exist within a graph to get this property.  The structure can be exploited a little better than that.  Can we do better?  Is there a graph G which does not contain a K_5 for which G \rightarrow K_3?  Yes!  And we can even do the best possible!  There exists a graph G which is K_4-free where G \rightarrow K_3!  Folkman gave an example.

How do you show this?  Very delicately.  It’s a process known as amalgamation.  It’s quite complicated to describe without a marker and a whiteboard in front you, and I will not attempt it here.  But if you are curious, you can read more about it here.

The basic idea of it is that it is difficult to try to find a monochromatic K_3 while avoiding containing a K_4.  So instead we look for a monochromatic copy of specified bipartite graph.  These are easier to generate iteratively.  And so you go down this rabbit hole where you are creating a sequence of graphs, each of which contains the previous and each of which, using other Ramsey results such as the Hales-Jewett theorem, can guarantee you a little bit more.  Do this long enough and you are guaranteed to not get the right answer.  But!  With a complicated tweak, you can get the right answer.

I’m sure you gained essentially nothing from that.  But that’s probably where you would be if I had instead tried to struggle through an explanation of amalgamation.

The wonderful thing about amalgamation is that it can be generalized (or so Imre Leader claims, I haven’t seen the argument).  And with it, we get the result that there was nothing special about K_3 or using two colors.

Theorem.   For all s,k there exists a G such that however the edges of G are k-colored there exists a monochromatic coply of K_s, but K_{s+1} \not\subseteq G.

O but there is more.  There is also nothing special about the graph being complete!

Theorem.   Let H be a graph, then for all k there exists G such that any k-coloring of the edges of G yields a monochromatic copy of H and cl(G) = cl(H).

In the above, cl(G) is the clique number of G (pronunciation: clique rhymes with cheek, don’t let anyone tell you differently)- i.e. the size of the largest complete graph which is a subgraph of G.

And because it is often the case that “restricted theorems imply induced theorems”, the following seemingly much-stronger result is actually only a corollary of the many unproven statements above.

Corollary.   (Induced Ramsey Theory)
Let H be a graph.  Then for all k there exists G such that whenever E(G) is k-colored there must exist a monochromatic induced copy of H.

Every blog post should have at least one proof in it.  So here is (a Folland-esque) one.

Proof.   Let cl(H) = s.  Form H' by adding for each non-edge of H a copy of K_{s+1}-e.  So cl(H') = s.  Apply the previous theorem to get K_{s+1} \not\subseteq G such that E(G) k-colored implies that there exists a monochromatic copy of H'.  Inside that copy of H' the copy of H must be induced, else have a copy of K_{s+1}, a contradiction.                                                 \square

This seemingly great-strengthening of the previous results is apparently (according to Imre Leader) prevalent enough that I will call it a slogan.

Slogan.   Restricted Theorems Imply Induced Theorems.

But I know what you’ve probably been thinking throughout this post.  “Density” could mean something else than just containing a copy of a large complete graph.  Even a tiling of triangles with lots of edges added can still avoid a K_4 but appear pretty dense.  Well, there is one more result that I want to show you.

It has to deal with cycles of triangles.  If we have a lot of adjacent triangles what we get is cycles of triangles.  Meaning graphs that look like this:

(By the way, those lines are actually straight despite whatever illusion you see).

The above is a cycle of triangles of length 12.  So could we even ask for no short cycle of triangles?

Sparse Ramsey Theorem.  \text{(Ne\u{s}et\u{r}il and R\u{o}dl)}
For all k,g, there exists G such that any k-coloring of the edges of G gives rise to a monochromatic triangles, but G has no cycle of triangles of length less than g.

So there you have it.  The structure of the graph and the density of subgraphs are both important to guarantee these Ramsey properties.  But it turns out that although a high density is sufficient, it is not necessary.

Ok!  So that’s it for this series.  Next up is probably a fun post and then a short series on randomized algorithms.  Until next time!  :-)

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.

6 Responses to RT Part 9; Sparse Ramsey Theory

  1. Z Norwood says:

    I’m confused about your sixth paragraph. You’re saying that the graph G = K_{10} with a 9-cycle removed satisfies G \to K_3 but K_6 \not\subseteq G? Also, what do you mean by \subseteq here? I’m compelled to assume that here \subseteq means ‘is a subgraph of’, but when I see \subseteq as a relation on graphs, I first assume that it means ‘has the same vertex set as and is a subgraph of’ (e.g. G \subseteq K_n for every graph on [n], but K_4 \not\subseteq K_5).

    • Z Norwood says:

      I’m completely misunderstanding something, or [inclusive] you don’t really mean “Then G has a 2-coloring avoiding a monochromatic triangle” in paragraph 6.

      • JCummings says:

        \subseteq does just mean “is a subgraph of”. That was Imre’s notation although I do see now why it is confusing. I suppose the containment refers to a containment of the edge set. I’ll put a note above of that.

        And you are correct, that’s a typo. I’ll fix it now. Thanks for the catch!

  2. Z Norwood says:

    #Corrections: You say (paragraph 8) “There exists a graph G which is K_4-free where G \rightarrow K_4“. I think you mean …G \rightarrow K_3.

    I might be missing something, but I think it’s generally difficult for a K_4-free graph to contain a monochromatic copy of K_4.

  3. Z Norwood says:

    This is cool! I like this post.

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