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

Ramsey Theory

Ramsey Theory

"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 nz R(k,D,for any 2-coloring of Kn, there exists a red Kk or a blue Ki. 2-coloring of K f:(）,(-od.biuo) Ramsey Theorem R(k)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 K. R(k,2)=k;R(2,)=1; R(k,)≤R(k,l-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+1T+1=n=R(k,l-1)+R(k-1,0 S≥1) Kkin S Kil in S or K T≥R(k-1,D Kk-1 in T 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 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