Introduction to Ramsey Theory: Students' Projects

Subsection 14.10.1 Dhruv Mubayi''s Favourite Proof

Dr. Mubayi is a Fellow of the American Mathematical Society and a recipient of the Simons Fellowship in Mathematics and the Humboldt Research Award. [14.10.3.1].

This is from Professor Mubayi's reply to our message:

Many Ramsey theory proofs boil down to density arguments (just look at the densest color class). I think it is more interesting to consider proofs that really use the "Ramsey"ness.

So from this point of view the most basic proofs are the most interesting, say for \(r(p,p)\) or better, for \(r(3,3,3,\ldots, 3)\) or even the more advanced constructions for off diagonal \(r(3,t)\) or \(r(4,t)\text{.}\)

The point is that for each of these, the densest graphs that forbid one of the structures are very poor ones from the Ramsey theoretic viewpoint. In particular, these proofs/constructions are more interesting than, say the proof for \(r(C_4, C_4, \ldots, C_4)\) which relies on Turan results. Similarly, the many proofs for van der Waerden?s theorem rest on density results so they are less "Ramsey" in nature. I like them too, but they have less a flavour of Ramsey and more of just an extremal result. [14.10.3.2]

Professor Mubayi's message reminded us about a "non–density proof" that we have learned in our Ramsey Theory class.

This means that any three–edge colouring of \(K_{17}\) yields a monochromatic \(K_3\text{,}\) but that there is a three–edge colouring of \(K_{16}\) that has no monochromatic \(K_3\)s.

Consider a three colouring of the graph \(K_{17}\) with colours \(\color{red}{\text{red}}\text{,}\) \(\color{green}{\text{green}}\text{,}\) and \(\color{blue}{\text{blue}}\text{.}\)

Let \(x\) be a vertex in \(K_{17}\text{.}\) This vertex is incident to 16 edges. By the generalized pigeonhole principle, there exists a colour that has at least 6 incident edges. Let it be \(\color{green}{\text{green}}\) without loss of generality.

Let \(Y_i = \{y_1, y_2, \ldots, y_6\}\) be neighbours of vertex \(x\) such that \(\{x, y_i\}\) is also \(\color{green}{\text{green}}\) for \(1 \leq j \leq 6\text{.}\)

If there exists an edge joining any two of these vertices, we have found a \(\color{green}{\text{green } K_3}\text{.}\) Otherwise, there is a \(K_6\) coloured with two colours, and by Ramsey's theorem, \(K_6\) is large enough to guarantee a monochromatic \(K_3\) when coloured with two colours. So there is either a \(\color{red}{\text{red }K_3}\) or \(\color{blue}{\text{blue }K_3}\text{.}\) [14.10.3.3]

As depicted in the image, it is possible to 3–colour edges of \(K_{16}\) and avoid monochromatic triangles.

Subsection 14.10.2 Reflection

It was fascinating to read that Dhruv Mubayi prefers "elementary" Ramsey theory proofs over those that use density arguments. In our project, Dr. Butler, Dr. Fox, Dr. Gasarch, Dr. Leader, and Dr. Spencer pointed out to various "elementary" proofs among their favourites.