Ramsey Theory
Ramsey Theory
"In any party of six people,either at least three of them are mutual strangers or at least three ofthem are mutual acquaintances" Color edges of K6 with 2 colors. There must be a monochromatic K3. Frank P.Ramsey (1903-1930)
Frank P. Ramsey (1903-1930) “In any party of six people, either at least three of them are mutual strangers or at least three of them are mutual acquaintances” Color edges of K6 with 2 colors. There must be a monochromatic K3
"In any party of six people,either at least three of them are mutual strangers or at least three of them are mutual acquaintances" Color edges of K6 with 2 colors. There must be a monochromatic K3. ON A PROBLEM OF FORMAL LOGIC By F.P.RAMSEY. [Received 28 November,1928.-Read 13 December,1928.) This paper is primarily concerned with a special case of one of the leading problems of mathematical logic,the problem of finding a regular Frank P.Ramsey procedure to determine the truth or falsity of any given logical formula'. But in the course of this investigation it is necessary to use certain (1903-1930) theorems on combinations which have an independent interest and are most conveniently set out by themselves beforehand
Frank P. Ramsey (1903-1930) “In any party of six people, either at least three of them are mutual strangers or at least three of them are mutual acquaintances” Color edges of K6 with 2 colors. There must be a monochromatic K3
R(k,l)A the smallest integer satisfying: if n=R(k,D),for any 2-coloring of Kn, there exists a red Kk or a blue Ki. 2-coloring of Kn f:(）,(coz.biuo) Ramsey Theorem R(kl)is finite. Frank P.Ramsey (1903-1930) R(3,3)=6
R(k,l) the smallest integer satisfying: Ramsey Theorem R(k,l) is finite. 2-coloring of Kn f : [n] 2 ⇥ {red, blue} if n≥ R(k,l), for any 2-coloring of Kn, there exists a red Kk or a blue Kl. R(3,3) = 6 Frank P. Ramsey (1903-1930)
if n=R(k,l),for any 2-coloring of Kn, there exists a red Kk or a blue Ki. R(k,2)=k;R(2,)=1; R(k,)≤R(k,I-1)+R(k-1,)
if n≥ R(k,l), for any 2-coloring of Kn, there exists a red Kk or a blue Kl. R(k,2) = k ; R(2,l) = l ; R(k,l) ≤ R(k,l-1) + R(k-1,l)