Is there a Ramsey's theorem equivalent for vertex colorings?

Question

Ramsey's theorem states that any 2-color edge coloring of a sufficiently large graph contains a monochromatic complete subgraph. Does there exist something like Ramsey's theorem but for vertex colorings? Like, for any 2-color vertex coloring of a sufficiently large graph contains a monochromatic complete subgraph (but this time with the vertices colored and not the edges). Or is there someway to translate the vertex problem in an edge coloring problem such that we can use Ramsey's theorem?

Answer 1

For vertex colouring the theorem is called "The Pigeon Hole Principle". It says that no matter how you colour the vertices of the complete graph with $(n-1)r+1$ vertices with $r$ colours you can always find a mono-chromatic copy of $K_n$.

Moreover, there exists a colouring of the complete graph with $(n-1)r$ vertices with $r$ colours with no monochromatic $K_n$.

Nobody cares about this because the answer is trivial.

Answer 2

Questions of Ramsey theory often look something like this:

• We have a set with $n$ elements
• We assign colors to its $k$-sets (that is, its $\binom n k$ subsets of size $k$).
• Must there be a $w$-set whose $k$-sets are all one color?

Phrased in this way, the typical example, coloring the edges of $K_6$, looks like this:

• We have a set with $6$ elements
• We assign one of two colors to each of its $2$-sets, (there are $\binom 62=15$ of these)
• Is there a $3$-set whose $2$-sets are all the same color?

The answer is that there must be, but if we replace $n=6$ in the first line with $n=5$, there need not be. (The essentially unique counterexample is $\{ \color{darkred}{\{1, 2\}}, \color{darkblue}{\{1, 3\}}, \color{darkblue}{\{1, 4\}}, \color{darkred}{\{1, 5\}}, \color{darkred}{\{2, 3\}}, \color{darkblue}{\{2, 4\}}, \color{darkblue}{\{2, 5\}}, \color{darkred}{\{3, 4\}}, \color{darkblue}{\{3, 5\}}, \color{darkred}{\{4, 5\}} \}$.)

Note that we've scrubbed out the graph terminology completely. Graph edges have become $2$-sets, but nothing has really changed. Graph edges can be completely identified with $2$-sets of vertices; there's no difference.

If you're asking about graph vertices instead of edges, you've changed the $2$-sets to $1$-sets. But $1$-sets, that is subsets with only 1 element, are no different from elements themselves. So the formulation is:

• We have a set with $n$ elements
• We assign one of $r$ colors to each of its… elements
• Is there a $k$-set whose… elements… are all the same color?

And the answer is pretty obvious. (As N.S. and Qiaochu pointed out, it's essentially the pigeonhole principle. Which, I should add, is usually regarded as a simple example of a Ramsey-type theorem.)

But you can go in the other direction too. Instead of looking at $1$-sets, you can look at $3$-sets:

• We have a set with $n$ elements
• We assign one of several colors to each of its 3-sets (there are $\binom n3$ of these)
• Is there a $k$-set whose 3-sets are all the same color?

Here we're coloring the “triangles” of a complete graph, and asking if there must be a smaller complete graph whose “triangles” are all the same color. As with the $2$-set case, the answer is yes, if $n$ is sufficiently large. And in fact the general theorem is true:

Let $k, s, r$ be given. Take a set of $n$ elements, and assign $r$ colors to each of its $s$-sets, then there must always be a $k$-element subset whose $s$-sets have all been assigned the same color, if $n$ is sufficiently large.

Taking the special case $s=2$ gives us the usual Ramsey graph theorem; taking $s=1$ gives us the pigeonhole principle.

The keyword to search for here is “hypergraph Ramsey numbers”.