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 D\S 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 (Erdos 1963) If ()(1-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)-
If n k ⇥ 1 2k⇥nk < 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 2k⇥nk
Theorem (Erdos 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)”- Pr As≤∑(1-2)m-k<1 s∈() s∈(R)
If n k ⇥ 1 2k⇥nk < 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 2k⇥nk Pr < 1 ⇧ ⇤ ⌥ S( [n] k ) AS ⇥ ⌃ ⌅ ⇥ S⇥( [n] k ) (1 2k) nk
Theorem (Erdos 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 V As <1 se(g)」 s∈()
If n k ⇥ 1 2k⇥nk < 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 < 1 ⇧ ⇤ ⌥ S( [n] k ) AS ⇥ ⌃ ⌅ Pr[T is k-paradoxical] = 1 Pr ⇧ ⇤ ⌥ S( [n] k ) AS ⇥ ⌃ ⌅ > 0
Theorem (Erd6s 1963) If ()(1--k)<1 then there is a k-paradoxical tournament of n players. Pick a random tournament T on n players [n]. PrT is k-paradoxical>0 There is a k-paradoxical tournament on n players
If n k ⇥ 1 2k⇥nk < 1 then there is a k-paradoxical tournament of n players. Theorem (Erdős 1963) Pick a random tournament T on n players [n]. Pr[T is k-paradoxical] > 0 There is a k-paradoxical tournament on n players