"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)
if n=R(k,D,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 ISI+I71+1=n R(k,1-1)+R(k-1,1) N≥R) Kkin S Kil in S or Ki T≥Rk1,0rKmT 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
if n=R(k,l),for any 2-coloring of Kn, there exists a red Ki or a blue Ki. R(k2)=k;R(2,)=I; R(k,)≤R(k,l-1)+R(k-1,) Ramsey Theorem R(k,is finite. By induction: k+1-2 R(k,)≤(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) Ramsey Theorem R(k,l) is finite. R(k,l) ⇥ k + l 2 k 1 By induction: ⇥
Ramsey Number Lovasz Local Lemma (2可≤传)=0() k,112 3 4 5 6 8 9 10 111 1 1 1 1 A 1 2123 4 5 6 1 8 9 10 313 6 9 14 18 23 28 36 40-43 414 9 18 25 35-41 49-61 56-84 73-115 92-149 515 14 25 43-49 58-87 80-143 101-216 125-316 143-442 616 18 35-41 58-87 102-165 113-298 127-495 169-780 179-1171 71723 49-61 80-143 113-298 205-540 216-1031 233-1713 289-2826 1828 8 56-84 101-216127-495216-1031 282-1870 317-3583 317-6090 91936 73-115125-316169-780233-1713317-3583565-6588 580-12677 1011040-4392-149143-442179-1171289-2826317-6090 580-12677798-23556
Ramsey Number k2k/2 ⇥ ⇥ R(k, k) ⇥ ⇤2k 2 k 1 ⌅ = O 4k k Lovász Local Lemma ⇥
Muticolor if n=R(k,l),for any 2-coloring of Knt, there exists a red Kk or a blue Ki. R(R(k1,k2,,k) ifn≥R(r;k1,k2,.,k), for any r-coloring of K,there exists a monochromatic ki-clique with color i for some ie {1,2,...r}. R(r;k1,,k-2,k-1,k)≤R(r-1;k1,…,k-2,R(2;k-1,k) the mixing color trick: color
Multicolor if n≥ R(k,l), for any 2-coloring of Kn, there exists a red Kk or a blue Kl. R(Rr; (k1, k2, ... , , ... , kr) if n ≥ R(r; k1, k2, ... , kr), for any r-coloring of Kn, there exists a monochromatic ki-clique with color i for some i∈{1, 2, ..., r}. R(r; k1, ... , kr-2, kr-1, kr) ≤ R(r-1; k1, ... , kr-2, R(2; kr-1, kr)) the mixing color trick: color
Muticolor if n=R(k,l),for any 2-coloring of Knt, there exists a red Kk or a blue Ki. R(r;k1,k2,.,k) ifn≥R(r;k1,k2,.,k), for any r-coloring of Kn,there exists a monochromatic ki-clique with color i for some ie{1,2,...,r}. Ramsey Theorem R(r;k1,k2,...,k)is finite
R(r; k1, k2, ... , kr) Multicolor if n≥ R(k,l), for any 2-coloring of Kn, there exists a red Kk or a blue Kl. if n ≥ R(r; k1, k2, ... , kr), for any r-coloring of Kn, there exists a monochromatic ki-clique with color i for some i∈{1, 2, ..., r}. Ramsey Theorem R(r; k1, k2, ... , kr) is finite