南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）The Probabilistic Method

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-均0 There exists a two-coloring without monochromatic Kk

If ￾n k ⇥ · 21￾ ￾k 2 ⇥ 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?

Theorem(Erd6s 1963) If ()(1-)<1 then there is a k-paradoxical tournament of n players. Pick a random tournament T on n players [n]. Fixed any S∈ . Event As:no player in V\beat all players in S. PrAs=(1-2k)”-

If ￾n k ⇥ ￾1 ￾ 2￾k⇥n￾k < 1 then there is a k-paradoxical tournament of n players. Theorem (Erdős 1963) Pick a random tournament T on n players [n]. Fixed any S ￾ ￾[n] k ⇥ Event AS : no player in V \S beat all players in S. Pr[AS] = ￾ 1 ￾ 2￾k⇥n￾k

Theorem(Erd6s 1963) If()(1-2-k)”- 1 then there is a k-paradoxical tournament of n players. Pick a random tournament T on n players [n]. Event As:no player in \S beat all players in S. Pr[As=(1-2k)”-k Pr ≤∑(1-2k)-k <1 s∈() S∈()

If ￾n k ⇥ ￾1 ￾ 2￾k⇥n￾k < 1 then there is a k-paradoxical tournament of n players. Theorem (Erdős 1963) Pick a random tournament T on n players [n]. Event AS : no player in V \S beat all players in S. Pr[AS] = ￾ 1 ￾ 2￾k⇥n￾k Pr < 1 ￾ ⇧ ⇤ ⌥ S￾( [n] k ) AS ⇥ ⌃ ⌅ ⇥ ￾ S⇥( [n] k ) (1 ￾ 2￾k) n￾k

Theorem(Erd6s 1963) If ()(1-2-k)"<1 thon there is a k-paradoxical tournament of n players. Pick a random tournament T on n players [n]. Event As no player in \S beat all players in S. V<1 se() 0 S∈()

If ￾n k ⇥ ￾1 ￾ 2￾k⇥n￾k 0

Theorem(Erdos 1963) If (R)(1-2-k)"0 There is a k-paradoxical tournament on n players

If ￾n k ⇥ ￾1 ￾ 2￾k⇥n￾k 0 There is a k-paradoxical tournament on n players

The probabilistic Method Pick random ball from a box, 00 Pr[the ball is blue]>0 000 →There is a blue ball. Define a probability space O,and a property P: Pr[P(x)]>0 X >xE with the property P

The Probabilistic Method • Pick random ball from a box, Pr[the ball is blue]>0. ⇒ There is a blue ball. • Define a probability space Ω, and a property P: Pr x [P(x)] > 0 =￾ ⇤x ⇥ ￾ with the property P