Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Asaf Karagila Nov 10 '13 at 12:33
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
This was too obvious, how could I have missed it? :) –  Asaf Karagila Sep 14 '10 at 10:32
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.