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

  • 4
    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
up vote 1 down vote accepted

The pigeonhole principle states that for a given number of pigeons, if only there are enough holes then at least one empty hole is guaranteed to exist.

Ramsey' s theorem states that if only there are enough vertices then at least one thingy (e.g., red or blue triangle) is guaranteed to exist.

  • 4
    I'd revise the summary of "pigeonhole principle" to say for a given number of holes, if there are enough pigeons (or other items), there will exist a hole with more than one pigeon/item. – hardmath Jun 11 '15 at 12:25

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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