Ramsey Theory
Ramsey Theory
"In any party of six people,either at least three ofthem are mutual strangers or at least three ofthem 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 28November,1928.-Read 1 December,198. 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)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 K r:(）,(rod.bine) Ramsey Theorem R(k,l)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,D,for any 2-coloring of Kn, there exists a red Kk or a blue Ki. R(k2)=k;R(2,)=I; R(k,)≤R(k,1-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)
if n=R(k,l),for any 2-coloring of Kn, there exists a red Kk or a blue Ki. R(k,)≤R(k,l-1)+R(k-1,) take n R(k,1-1)+R(k-1,1) arbitrary vertex v IS1+IT+1=n=R(k,-1)+R(k-1,) ≥Rku)knS or Ki1 in S Ki T≥Rk-1,0 orKin+ K Kiin T
S T if n≥ R(k,l), for any 2-coloring of Kn, there exists a red Kk or a blue Kl. R(k,l) ≤ R(k,l-1) + R(k-1,l) v take n = R(k,l-1) + R(k-1,l) arbitrary vertex v |S| + |T| + 1 = n = R(k,l-1) + R(k-1,l) |S| ≥ R(k,l-1) |T| ≥ R(k-1,l) or or Kk in S Kl-1 in S or Kk-1 in T Kl in T +v Kl +v Kk