R 以 The probabilistic Method Paul Erdos
The Probabilistic Method Paul Erdős
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 l0● with prob 1/2 For a particular Kk,(edges Pr[Kk Or K]=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(份-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, Pr[the Kk is monochromatic]=21-() number of Kk in Kn: () Pr[3a monochromatic Kk] ≤(2- ）<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(份-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 random two-coloring: Pr[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) For a random two-coloring: Pr[¬ a monochromatic Kk ] > 0 There exists a two-coloring without monochromatic . Kk
Tournament T(V,E) n players,each pair has a match. u points to v iff u beats v. k-paradoxical: For every k-subset S of V, there is a player in S who 4 beats all players in S. "Does there exist a k-paradoxical tournament for every finite k?
Tournament n players, each pair has a match. u points to v iff u beats v. k-paradoxical: For every k-subset S of V, there is a player in V \ S who beats all players in S. T(V, E) “Does there exist a k-paradoxical tournament for every finite k?