Tell me more ×
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

1 Answer

up vote 1 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

Your Answer

 
discard

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.