3
$\begingroup$

The [infinite] Ramsey theorem states that

Let $n$ and $k$ be natural numbers. Every partition $\{X_1,\ldots ,X_k\}$ of $[\omega]^n$ into $k$ pieces has an infinite homogeneous set. Equivalently, for every $F\colon [\omega]^n\to \{1, . . . , k\}$ there exists an infinite $H \subseteq \omega$ such that $F$ is constant on $[H]^n$.

Where $[X]^k := \{ Y \subset X | |Y| = k\}$.

Now, when $k=2$ we can interpret this as coloring edges of a complete graph. But what happens when $k>2$, is there some geometrical or graphic, in a similar sense, to which we can turn this state into?

  • 0
    An "arbitrary" downvote reminded me of this very old question, so it seemed reasonable to revamp the tags, and match them to the newer ones we have added to the site since the question was asked originally.2013-11-10

1 Answers 1

3

Partitioning $[\omega]^{(n)}$ into $k$ pieces can be interpreted as colouring the complete $n$-uniform hypergraph, with vertex set $\omega$, in $k$ colours.

When $n=2$ the complete $2$-uniform hypergraph is the complete graph with vertex set $\omega$.

For a definition of hypergraph see http://en.wikipedia.org/wiki/Hypergraph. Briefly it is the generalisation of a graph where edges can join more than two vertices. And by complete $n$-uniform I mean all the edges contain exactly $n$ vertices and every possible edge of size $n$ is in the hypergraph.

  • 0
    This was too obvious, how could I have missed it? :)2010-09-14