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

的 以d 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(份·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, e is colored 8 with prob 1/2 with prob 1/2 For a particular Kk,()edges Pr[KorK]=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(份·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 particular Kk, Pr[the Kk is monochromatic]=21-() number of Kk in Kn: () Pr[3 a monochromatic Kk] ≤（附·21- 0<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 DS who 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-2-)"<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. PrAs=(1-2k)”-k

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)”-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. PrAs=(（1-2n- Pr As ≤∑(1-2k)n-k <1 s∈() S∈(R)

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 (Erdos 1963) If (R)(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. se(l) 0 se()

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

Theorem (Erd6s 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