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 is two-colored (i.e. we color the edges), we are guaranteed that a monochromatic triangle exists. We write this as . So what does this tell us about the triangles in ? 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 (i.e. that ), what we need to find is a pocket of which is dense with triangles. i.e. we want to contain a copy of , 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 such that and ! ( means “is a subgraph of”) For example, let be the graph with a 9-cycle removed. Then but does not contain a subgraph.
Ok. So 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 which does not contain a for which ? Yes! And we can even do the best possible! There exists a graph which is -free where ! 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 while avoiding containing a . 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 or using two colors.
Theorem. For all there exists a such that however the edges of are -colored there exists a monochromatic coply of , but .
O but there is more. There is also nothing special about the graph being complete!
Theorem. Let be a graph, then for all there exists such that any -coloring of the edges of yields a monochromatic copy of and .
In the above, cl is the clique number of (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 .
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 be a graph. Then for all there exists such that whenever is -colored there must exist a monochromatic induced copy of .
Every blog post should have at least one proof in it. So here is (a Folland-esque) one.
Proof. Let . Form by adding for each non-edge of a copy of . So . Apply the previous theorem to get such that -colored implies that there exists a monochromatic copy of . Inside that copy of the copy of must be induced, else have a copy of , a contradiction.
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 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:
The above is a cycle of triangles of length 12. So could we even ask for no short cycle of triangles?
Sparse Ramsey Theorem.
For all , there exists such that any -coloring of the edges of gives rise to a monochromatic triangles, but has no cycle of triangles of length less than .
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! :-)