The geometry of random tournaments
From MaRDI portal
Combinatorial aspects of tessellation and tiling problems (05B45) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Discrete approximations in optimal control (49M25) Large deviations (60F10) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Analysis of algorithms (68W40)
Abstract: 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.
Recommendations
This page was built for publication: The geometry of random tournaments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6349459)
