## 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!  :-)

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

• JCummings says:

Sheesh! Several typos! Thanks, yeah that does seem impossible.

3. Z Norwood says:

This is cool! I like this post.