正在加载图片...
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