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 ⇥