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 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(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 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 (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 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 (R)(1-2-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