Theorem (Erdos 1947) If(份·2l-(<1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. For a random two-coloring: Pr[3a monochromatic Kk]<1 Pr[3 a monochromatic Kk]>0 There exists a two-coloring without monochromatic Kk.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) Pr[￾ a monochromatic Kk ] < 1 For a random two-coloring: Pr[¬￾ a monochromatic Kk ] > 0 There exists a two-coloring without monochromatic . Kk