"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)
Theorem (Erdos 1947) If(份-21-均<1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. For each edge ee Kn, with prob 1/2 e is colored with prob 1/2 For a particular Kk, Pr[Kk or Kk ]=21-()
If n k ⇥ · 21 k 2 ⇥ < 1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. Theorem (Erdős 1947) e is colored with prob 1/2 with prob 1/2 For a particular Kk , Pr[ or ] = 21 k 2 ⇥ Kk Kk For each edge e Kn
Theorem (Erdos 1947) If(份-21-均<1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. For a particular Kk, PrI Kk or Kk 1=21-() number of Kk in Kn: Pr[a monochromatic Kk] ≤(）2- 0<1
If n k ⇥ · 21 k 2 ⇥ < 1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. Theorem (Erdős 1947) For a particular Kk , number of Kk in Kn: n k ⇥ Pr[ a monochromatic Kk ] ⇤ n k ⇥ · 21 k 2 ⇥ < 1 Pr[ or ] = 21 k 2 ⇥ Kk Kk
Theorem (Erdos 1947) If(份-21-均<1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. For a random two-coloring: Pr[a monochromatic Kk]>0 There exists a two-coloring without monochromatic Kk
If n k ⇥ · 21 k 2 ⇥ < 1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. Theorem (Erdős 1947) For a random two-coloring: Pr[¬ a monochromatic Kk ] > 0 There exists a two-coloring without monochromatic . Kk