German Wikipedia states that the Ramsey`s 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 can`t figure it out by myself.
So my question is:
What is an easy explanation for the fact that the Ramsey`s theorem is a generalization of the Pigeonhole principle?
Thanks for any help in advance
Best Answer
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.