if ne R(k,l),for any 2-coloring of Kn, there exists a red Ki or a blue Ki. R(k,2)=k;R(2,)=1; R(k,)≤R(k,I-1)+R(k-1, Ramsey Theorem R(k,l)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: ⇥
R(k,k)≥n “]a2-coloring of K,no monochromatic Kk.” a random 2-coloring of K: Uv u,Kn,uniformly and independently VSE()event As:S is a monochromatic K& Pr[As]=2.2(2)=21-() As,Ar dependentsnT2 maxdegree of dependenyp()付(k”2） To prove:Pr 1>0 Se()
“∃ 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[Ail≤p ·ep(d+1)≤1 Pr[As]=21-() for some n ck2k/2 s()()了 with constant c e21-()(d+1)≤1 To prove:Pr >0 se(I) 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)三m对≤（贷）=0() 2 3 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 2 2 3 4 5 6 7 8 9 10 3 6 9 14 18 23 28 36 40-42 18 25 36-41 49-61 59-84 73-115 92-149 5 43-48 58-87 80-143 101-216 133-316 149-442 6 102-165 115-298 134-495 183-780 204-1171 7 205-540 217-1031 252-1713 292-2826 8 282-1870 329-3583 343-6090 9 565-6588 581-12677 10 798-23556
Ramsey Number k2k/2 ⇥ ⇥ R(k, k) ⇥ ⇤2k 2 k 1 ⌅ = O 4k k Lovász Local Lemma ⇥ l k 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 2 2 3 4 5 6 7 8 9 10 3 6 9 14 18 23 28 36 40–42 4 18 25 36–41 49–61 59–84 73–115 92–149 5 43–48 58–87 80–143 101–216 133–316 149–442 6 102–165 115–298 134–495 183–780 204–1171 7 205–540 217–1031 252–1713 292–2826 8 282–1870 329–3583 343–6090 9 565–6588 581–12677 10 798–23556
Muticolor if nR(k,l),for any 2-coloring of K, 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}. R(r;k1,…,k-2,kr-1,k)≤R(r-1;k1,…,k-2,R(2;k-1,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