# Why is the Ramseys theorem a generalization of the Pigeonhole principle

German Wikipedia states that the Ramseys theorem is a generalization of the Pigeonhole principle source

But does not say why this is true. I am doing a presentation about the Ramsey theory and also wanna explain why this is true, but as not really an mathematician myself I cant figure it out by myself.

So my question is:

What is an easy explanation for the fact that the Ramseys theorem is a generalization of the Pigeonhole principle?

Thanks for any help in advance

• I never heard Ramsey's theorem called a simplification of the pigeonhole principle. I'd call it a generalization. Isn't that what "Verallgemeinerung" means? – bof Jun 11 '15 at 11:59
• That seems right, I have translated "Verallgemeinerung" the wrong way. Thanks for that input, have edited it! – Jakob Abfalter Jun 11 '15 at 12:04
• Do you need an explanation of how Ramsey's theorem is a generalization of the pigeonhole principle, or does that seem clear? – MJD Jun 11 '15 at 12:05
• Thats exaclty what I am looking for – Jakob Abfalter Jun 11 '15 at 12:05

Ramsey's theorem, in general, says that for given $n, t,$ and $k$, there is a number $R$ (depending on $(n,t,k)$) such that for every $R$-element set $S$ and every $k$-coloring of the $t$-element subsets of $S$ $$f : S^{\{1,2,\ldots, t\}} \to \{1,2,\ldots, k\}$$ there is an $n$-element subset $S'\subset S$ such that $f$ is constant when restricted to the $t$-element subsets of $S'$.
The Ramsey theorem for graphs takes $S$ to be the set of vertices of an $R$-clique, and $t=2$; by coloring 2-sets of vertices we are coloring edges of the clique. $S'$ is then the $n$-vertex subgraph of $S$ whose edges are all the same color.
The pigeonhole principle takes $S$ to be some unstructured set and $t=1$. Then $f$ is a $k$-coloring of the $1$-sets of $S$ (that is, the elements) and the pigeonhole principle tells us that for any given $n$ and $k$, there is an $R(n, 1, k)$, namely $R=kn-k+1$, so that whenever $S$ has $R$ elements, there must be an $n$-element subset $S'$ on which $f$ is constant.