0
$\begingroup$

The infinite Ramsey theorem reads as such:

Theorem. Let $X$ be some infinite set and colour the elements of $X^{(n)}$ (the subsets of $X$ of size $n$) in $c$ different colours. Then there exists some infinite subset $M$ of $X$ such that the size $n$ subsets of $M$ all have the same colour.

If I take $n=2$, I can identify $X$ with the vertices of a simple graph and $X^{(2)}$ as the possible edges. If I now take $c=2$, I can intepret the result as: "Any graph on infinitely many vertices has an infinite clique or an infinite independent set."

But what would the interpretations be for $c > 2$? There are more applications to the infinite Ramsey theorem in extremal graph theory, right?

$\endgroup$
2
  • $\begingroup$ Does coloring the edges of a graph not count as an interpretation? $\endgroup$ May 30, 2019 at 16:47
  • $\begingroup$ @MishaLavrov "There is always a colour used infinitely often in any colouring of $K_\omega$" is a result I can deduce in two sentences without using the theorem. Do you have something more particular in mind? $\endgroup$
    – SK19
    May 30, 2019 at 17:42

1 Answer 1

1
$\begingroup$

The standard interpretation of Ramsey's theorem for $c>2$ is that whenever the edges of $K_\omega$ are colored by finitely many colors, there is a monochromatic infinite clique in one of the colors.

(This is how we interpret $c>2$ in the finite case, too.)

Where the colors come from in any particular application of Ramsey's theorem is a different matter. "Colors" are just a more intuitive metaphor for partitioning the edge set of $K_\omega$, or for a function from $E(K_\omega)$ to a finite set.

$\endgroup$

You must log in to answer this question.

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