论文标题
随机比赛的几何形状
The geometry of random tournaments
论文作者
论文摘要
比赛是图的方向。每个边缘代表一场针对获胜者的比赛。得分顺序列出了每个团队的胜利数量。 Landau（1953）表征了完整图的得分序列。 Moon（1963）表明，对于随机锦标赛的平均得分序列，相同的条件是必要的，并且足够。 我们提供了这些结果的简短和自然证明，这些证据使用凸几何形状的地位为任何图。地位量是立方体的线性图像。 Moon的定理通过将带有分布和线性图的立方体的元素确定为期望运算符。我们对Landau定理的证明将划界与混合细分理论结合在一起。我们还表明，任何平均得分序列都可以通过在亚福特赛中随机而确定性的比赛来实现。
A tournament is an orientation of a graph. Each edge represents a match, directed towards the winner. The score sequence lists the number of wins by each team. Landau (1953) characterized score sequences of the complete graph. Moon (1963) showed that the same conditions are necessary and sufficient for mean score sequences of random tournaments. We present short and natural proofs of these results that work for any graph using zonotopes from convex geometry. A zonotope is a linear image of a cube. Moon's Theorem follows by identifying elements of the cube with distributions and the linear map as the expectation operator. Our proof of Landau's Theorem combines zonotopal tilings with the theory of mixed subdivisions. We also show that any mean score sequence can be realized by a tournament that is random within a subforest, and deterministic otherwise.
