Return to search

Upset Paths and 2-Majority Tournaments

In 2005, Alon, et al. proved that tournaments arising from majority voting scenarios have minimum dominating sets that are bounded by a constant that depends only on the notion of what is meant by a majority. Moreover, they proved that when a majority means that Candidate A beats Candidate B when Candidate A is ranked above Candidate B by at least two out of three voters, the tournament used to model this voting scenario has a minimum dominating set of size at most three. This result gives 2-majority tournaments some significance among all tournaments and motivates us to investigate when a given tournament can be considered a 2-majority tournament. In this thesis, we prove, among other things, that the presence of an upset path in a tournament allows us to conclude the tournament is realizable as a 2-majority tournament.

Identiferoai:union.ndltd.org:csusb.edu/oai:scholarworks.lib.csusb.edu:etd-1421
Date01 June 2016
CreatorsAlshaikh, Rana Ali
PublisherCSUSB ScholarWorks
Source SetsCalifornia State University San Bernardino
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceElectronic Theses, Projects, and Dissertations

Page generated in 0.0014 seconds