Ramsey’s theorem

Ramsey’s theorem states that a particular arrows relation,


holds for any integers n and k.

In words, if f is a functionMathworldPlanetmath on sets of integers of size n whose range is finite then there is some infinite Xω such that f is constant on the subsets of X of size n.

As an example, consider the case where n=k=2, and f:[ω]2{0,1} is defined by:

f({x,y})={1 if x=y2 or y=x20otherwise

Then let Xω be the set of integers which are not perfect squaresMathworldPlanetmath. This is clearly infinite, and obviously if x,yX then neither x=y2 nor y=x2, so f is homogeneous on X.

Title Ramsey’s theorem
Canonical name RamseysTheorem
Date of creation 2013-03-22 12:55:49
Last modified on 2013-03-22 12:55:49
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 9
Author mathcam (2727)
Entry type Theorem
Classification msc 05D10
Related topic RamseysTheorem2
Related topic GraphTheory