2
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ This is false with no hypotheses on the edges. If you're still coloring the vertices of the complete graph then this has nothing to do with the graph structure and is just the pigeonhole principle applied to the vertices as a set. $\endgroup$ Dec 27, 2020 at 19:03
  • $\begingroup$ I see, but what if the graph isn't complete anymore? Can we say sometime about the existence of monochromatic complete subgraphs? $\endgroup$
    – PhPanda
    Dec 27, 2020 at 19:07
  • 1
    $\begingroup$ If you want to constrain the number / density of edges then, ignoring color, the result you want is Turan's theorem: en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem $\endgroup$ Dec 27, 2020 at 19:11
  • $\begingroup$ @PhPanda If the graph is not complete, and you are using a single colour, the question of determining the Ramsey number becomes equivalent to the MaxClique problem, which I think is NP complete. For multicolours I think the problem is also closely related to the max clique. $\endgroup$
    – N. S.
    Dec 27, 2020 at 20:21

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ Well, it's not that nobody cares about it, it's just that the graph structure is irrelevant and the statement in this case just is the pigeonhole principle (which people care about quite a lot). $\endgroup$ Dec 27, 2020 at 19:04
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .