The Probabilistic Method Paul Erdos
The Probabilistic Method Paul Erdős
Ramsey Number "In any party of six people,either at least three of them are mutual strangers or at least three of them are mutual acquaintances" For any two coloring of K6, there is a monocbromatic K3. Ramsey's Theorem If n =R(k,k),for any two coloring of Kn,there is a monochromatic Kk. Ramsey number:R(k,k)
Ramsey Number • For any two coloring of , there is a monochromatic . “In any party of six people, either at least three of them are mutual strangers or at least three of them are mutual acquaintances” K6 K3 Ramsey’s Theorem If n R(k,k), for any two coloring of Kn, there is a monochromatic Kk . Ramsey number: R(k,k)
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
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 Ki subgraph. For a particular Kk, Prlthe K&is monochromatic]=21-( number of Kk in Kn: ( Pr[3 a monochromatic Kk] ≤（阳·21-③<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 , Pr[the Kk is monochromatic] = 21 k 2 ⇥ number of Kk in Kn: n k ⇥ Pr[ a monochromatic Kk ] ⇤ n k ⇥ · 21 k 2 ⇥ < 1
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