The geometry of random tournaments
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908654862598144 |
|---|---|
| author | Sanchez, Mario Kolesnik, Brett |
| author_facet | Sanchez, Mario Kolesnik, Brett |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2009_09322 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | The geometry of random tournaments Sanchez, Mario Kolesnik, Brett Combinatorics Probability 05C20, 52B20 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. |
| title | The geometry of random tournaments |
| topic | Combinatorics Probability 05C20, 52B20 |
| url | https://arxiv.org/abs/2009.09322 |