Ramsey's Number Theorem Proof

Ramsey's Theorem states that for every positive integers say k1 and k2, there exists an integer R(k1, k2) known as ramsey number, such that any graph with R(k1, k2) nodes contain a clique with atleast 'k1' nodes or independent set with atleast 'k2' nodes.

Ramsey's Number Theorem


is proven by induction of 'n'.

If n=1, then it just states that any partition of an infinite set into a finite number of subsets must //include an infinite set; (i.e.,the union of a finite number of finite sets is finite).

This would be easier to prove, as there are finite number of sets, there is the largest set of size x. Let the number of sets be 'y'. Then the size of the union is not more than xy.

If w->(w)nk
then it can be represented as, w->(w)n+1k

Let 'f' be some coloring of [S]n+1 by k, Where 'S' is an infinite subset of 'w'.

The value of x can be defined as:
fx:[Sx]n->k by fx(X)=f(x U X).

As 'S' is infinite, by the induction hypothesis, this is said to have an infinite homogeneous set.

Sequence of Integers (ni)iw and Sequence of Infinite Subsets of w , (Si)iw can be defined by induction.

Let n0=0 and let S0=w.
Given ni and Si for i<=j we can define Sj as an infinite homogeneous set for fni:[Sj−1]n->k and njas the least element of Sj . Obviously N=ni is infinite, and it is also homogeneous, since each ni is contained in Sj for each ji .
Code to add this calci to your website Expand embed code Minimize embed code

The online proof of Ramsey's Number Theorem is made easier here.

english Calculators and Converters

Ask a Question