Upset Paths and 2-Majority Tournaments

<p>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.</p>

Name thesis:degree_name

Master of Arts in Mathematics

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Mathematics

Year dc:date.available

2016

Author dc:creator

• Alshaikh, Rana Ali

Contributors dc:contributor

• Jeremy Aikin

• upset paths
• 2-majority tournaments
• UP-sets.
• Discrete Mathematics and Combinatorics

Repository record dc:identifier

https://scholarworks.lib.csusb.edu/etd/356

OAI identifier oai:identifier

oai:scholarworks.lib.csusb.edu:etd-1421