Theorem (Erdos 1947) If(W·2l-(⑤<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 eiscolored 8 with prob 1/2 For a particular Kk,(edges Pr[Kk or Kk]=2l-(⑤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 , ￾k 2 ⇥ edges Pr[ or ] = 21￾ ￾k 2 ⇥ Kk Kk For each edge e ￾ Kn