Back to search

Hosted by Utah State University Libraries

On Fractional Realizations of Tournament Score Sequences

Abstract

dc:description.abstract

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 n-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.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Mathematics and Statistics
Grantor dc:publisher
Hosted by Utah State University Libraries

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Murphy, Kaitlin S.
Contributors dc:contributor
  • David E. Brown
  • Andreas Malmendier
  • Brynja Kohler

Subjects

dc:subject × 14

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Utah State University
Base URL
digitalcommons.usu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Murphy, Kaitlin S.. On Fractional Realizations of Tournament Score Sequences. Thesis thesis, Hosted by Utah State University Libraries, https://digitalcommons.usu.edu/etd/7592