飞矛盾的竞赛图的存在性 问：对任意有穷的k,是否总存在一个k矛盾的竞赛图？ 定理(Erd6s1947) 若()(1-2-k)”-k <1,则存在n个节点的k矛盾的竞赛图. 证：随机取一个包含n个节点的竞赛图T(V,) 口对k子集S,令As:不存在V八S中玩家打败了S的所有玩家 P(A)=(1-2-k)n-k →P(U,A)≤∑Pay)=()(1-2)m-<1 →P(∩a)>0 即存在一个k矛盾的竞赛图.𝒌矛盾的竞赛图的存在性 问：对任意有穷的𝒌，是否总存在一个𝒌矛盾的竞赛图？ 7 定理(Erdős 1947) 若 𝒏 𝒌 𝟏 − 𝟐 −𝒌 𝒏−𝒌 < 𝟏，则存在𝒏个节点的𝒌矛盾的竞赛图.  证：随机取一个包含𝒏个节点的竞赛图𝑻 𝑽,𝑬  对𝒌子集𝑺,令𝑨𝑺 :不存在𝑽\𝐒中玩家打败了𝑺的所有玩家 𝑷 𝑨𝑺 = 𝟏 − 𝟐 −𝒌 𝒏−𝒌 ⟹ 𝑷 ራ𝑺 𝑨𝑺 ≤ ෍𝑺 𝑷 𝑨𝑺 = 𝒏 𝒌 𝟏 − 𝟐 −𝒌 𝒏−𝒌 < 𝟏 ⟹ 𝑷 ሩ𝑺 𝑨𝒔 > 𝟎 即存在一个𝒌矛盾的竞赛图