南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Ramsey Theory-1

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)

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