南京大学：《概率与计算 Probability and Computing》课程教学资源（课件讲稿）random2

"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)

Theorem (Erdos 1947) If(份-21-均<1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. For each edge ee Kn, with prob 1/2 e is colored with prob 1/2 For a particular Kk, Pr[Kk or Kk ]=21-()

If ￾n k ⇥ · 21￾ ￾k 2 ⇥ < 1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. Theorem (Erdős 1947) ￾ e is colored with prob 1/2 with prob 1/2 For a particular Kk , Pr[ or ] = 21￾ ￾k 2 ⇥ Kk Kk For each edge e ￾ Kn

Theorem (Erdos 1947) If(份-21-均<1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. For a particular Kk, PrI Kk or Kk 1=21-() number of Kk in Kn: Pr[a monochromatic Kk] ≤(）2- 0<1

If ￾n k ⇥ · 21￾ ￾k 2 ⇥ < 1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. Theorem (Erdős 1947) For a particular Kk , number of Kk in Kn: ￾n k ⇥ Pr[￾ a monochromatic Kk ] ⇤ ￾n k ⇥ · 21￾ ￾k 2 ⇥ < 1 Pr[ or ] = 21￾ ￾k 2 ⇥ Kk Kk

Theorem (Erdos 1947) If(份-21-均0 There exists a two-coloring without monochromatic Kk

If ￾n k ⇥ · 21￾ ￾k 2 ⇥ 0 There exists a two-coloring without monochromatic . Kk

Theorem (Erdos 1947) If(份-21-均L2k2」

If ￾n k ⇥ · 21￾ ￾k 2 ⇥ ￾2k/2⇥

R(k,)>? "3 a 2-coloring of Kn,no monochromatic Kk." The Probabilistic Method: a random 2-coloring of K ∀S∈() event As:S is a monochromatic Kk To prove: 9ped站 Ls∈()」

“∃ a 2-coloring of Kn, no monochromatic Kk.” The Probabilistic Method: a random 2-coloring of Kn ⇥S ￾ ￾[n] k ⇥ event AS : S is a monochromatic Kk Pr ￾ ⇧ ⇤ ⌥ S￾( [n] k ) AS ⇥ ⌃ ⌅ > 0 To prove: Dependency! R(k,k) > ?

Lovasz Sieve Bad events:A1,A2,...,An None of the bad events occurs: The probabilistic method:being good is possible

Lovász Sieve • Bad events: • None of the bad events occurs: • The probabilistic method: being good is possible A1, A2,..., An Pr￾ ⇤ n i=1 Ai ⇥ Pr￾ ⇤ n i=1 Ai ⇥ > 0

events:A1,A2,...,An dependency graph:D(V,E) V={1,2,,n} ijEE Ai and Aj are dependent d:max degree of dependency graph A2 A(X1,X4) A4(X4) A3 A2(X1,X2) A5(X3) A3(X2,X3) A5 A4 X1,...,X4 mutually independent

A1 A2 A3 A5 A4 X1,...,X4 mutually independent A1(X1,X4) A2(X1,X2) A3(X2,X3) A4(X4) A5(X3) events: A1, A2, ... , An d : max degree of dependency graph dependency graph: D(V,E) V = { 1, 2, ..., n } ij ∈E Ai and Aj are dependent

events:A1,A2,...,An d:max degree of dependency graph Lovasz Local Lemma ·Vi,Pr[Al≤p ·ep(d+1)≤1 >l General Lovasz Local Lemma 3c1,.,xn∈[0,1) ∀i,PrA≤(1-x) →- i=1 jvi

events: A1, A2, ... , An d : max degree of dependency graph Lovász Local Lemma • ∀i, Pr[Ai] ≤ p • ep(d + 1) ≤ 1 Pr￾ ⇤ n i=1 Ai ⇥ > 0 General Lovász Local Lemma 9x1,...,xn 2 [0, 1) 8i,Pr[Ai]  xi Y j⇠i (1 ￾ xj ) Pr " ^ n i=1 Ai # ￾ Y n i=1 (1 ￾ xi)