Contrary to popular belief, we can’t all be winners.
Suppose 6 people compete in a chess tournament in which all pairs of players compete directly and no ties are allowed; i.e., 6 people compete in a ‘round robin tournament’. Each player is assigned a ‘score’, namely the number of games they won, and the ‘score sequence’ of the tournament is a list of the players’ scores. Determining whether a given potential score sequence actually is a score sequence proves to be difficult. For instance, (0, 0, 3, 3, 3, 6) is not feasible because two players cannot both have score 0. Neither is the sequence (1, 1, 1, 4, 4, 4) because the sum of the scores is 16, but only 15 games are played among 6 players. This so called ‘tournament score sequence problem’ (TSSP) was solved in 1953 by the mathematical sociologist H. G. Landau. His work inspired the investigation of round robin tournaments as directed graphs.
We study a modification in which the TSSP is cast as a system of inequalities whose solutions form a polytope η-dimensional space. This relaxation allows us to investigate the possibility of fractional scores. If, in a ‘round-robin’-ish tournament, Players A and B play each other 3 times, and Player A wins 2 of the 3 games, we can record this interaction as a 2/3 score for Player A and a 1/3 score for Player B. This generalization greatly impacts the nature of possible score sequences. We will also entertain an interpretation of these fractional scores as probabilities predicting the outcome of a true round robin tournament.
The intersection of digraph theory, polyhedral combinatorics, and linear programming is a relatively new branch of graph theory. These results pioneer research in this field.
| Identifer | oai:union.ndltd.org:UTAHS/oai:digitalcommons.usu.edu:etd-8725 |
| Date | 01 August 2019 |
| Creators | Murphy, Kaitlin S. |
| Publisher | DigitalCommons@USU |
| Source Sets | Utah State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | All Graduate Theses and Dissertations |
| Rights | Copyright for this work is held by the author. Transmission or reproduction of materials protected by copyright beyond that allowed by fair use requires the written permission of the copyright owners. Works not in the public domain cannot be commercially exploited without permission of the copyright owner. Responsibility for any use rests exclusively with the user. For more information contact digitalcommons@usu.edu. |
Page generated in 0.0029 seconds