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