南京大学：《组合数学》课程教学资源（课堂讲义）Ramsey理论 Ramsey theory

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