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
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,) Ramsey Theorem R(k,l)is finite. By induction: R(k,L)≤ k+1-2 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: ⇥
R(k,k)≥n 臼a2-coloring of K,no monochromatic K.” a random 2-coloring of Kn: uv Viu,vEKn,uniformly and independently w VSE()event As:S is a monochromaticK Pr[As]=2·2-()=21-() As,Ar dependentsnT2 max degree of dependency8 graph(）份('"2） To prove:Pr s∈()
“∃ a 2-coloring of Kn, no monochromatic Kk.” a random 2-coloring of Kn : ⇥S [n] k ⇥ event AS : S is a monochromatic Kk Pr ⇧ ⇤ ⌥ S( [n] k ) AS ⇥ ⌃ ⌅ > 0 R(k,k) ≥ n ∀{u,v}∈Kn, uniformly and independently uv uv AS, AT dependent |S ⇥ T| 2 To prove: Pr[AS] = 2 · 2( k 2) = 21( k 2) max degree of dependency graph d ⇥ k 2 ⇥ n k 2 ⇥
Lovasz Local Lemma 。 Vi,Pr[Al≤p ep(d+1)≤1 Pr[As]=21-() for some n =ck2k/2 "6t with constant c e21-()(d+1)≤1 To prove:Pr s∈() R(k,)≥n=2(k2k/2)
Pr ⇧ ⇤ ⌥ S( [n] k ) AS ⇥ ⌃ To prove: ⌅ > 0 Pr[AS] = 21( k 2) d ⇥ k 2 ⇥ n k 2 ⇥ Lovász Local Lemma • ∀i, Pr[Ai] ≤ p • ep(d + 1) ≤ 1 Pr ⇤ n i=1 Ai ⇥ > 0 R(k,k) ≥ n = (k2k/2) for some e21( k 2) (d + 1) 1 with constant c n = ck2k/2
Ramsey Number Lovasz Local Lemma 2三剑≤（使）-o() k,212 7 8 10 1111 1 1 1 1 1 2123 4 5 7 8 9 10 3136 9 14 18 23 28 36 40-43 4149 18 25 35-41 49-61 56-84 73-115 92-149 51514 25 43-49 58-87 80-143 101-216125-316 143-442 61618 35-4158-87 102-165113-298127-495 169-780 179-1171 71723 496180-143 113-298205-540216-1031233-1713 289-2826 81828 56-84101-216127-495216-1031282-1870317-3583 317-6090 91936 73-115125-316169-780233-1713317-3583565-6588580-12677 1011040-4392-149143-442179-1171289-2826317-6090580-12677798-23556
Ramsey Number k2k/2 ⇥ ⇥ R(k, k) ⇥ ⇤2k 2 k 1 ⌅ = O 4k k Lovász Local Lemma ⇥
Multicolor if nz R(k,D),for any 2-coloring of K there exists a red Kk or a blue K. 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 ie1,2,....rh. R(T:k1,,k-2,k-l,k)≤R(t-1;k1,,k-2,R(2;k1,k) the mixing color trick: 个 color
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}. R(r; k1, ... , kr-2, kr-1, kr) ≤ R(r-1; k1, ... , kr-2, R(2; kr-1, kr)) the mixing color trick: color