UVM Theses and Dissertations
Format:
Online
Author:
Martin, Jo Ryder
Dept./Program:
Mathematics and Statistics
Year:
2020
Degree:
M.S.
Abstract:
Hat guessing games--logic puzzles where a group of players must try to guess the color of their own hat--have been a fun party game for decades but have become of academic interest to mathematicians and computer scientists in the past 20 years. In 2006, Søren Riis, a computer scientist, introduced a new variant of the hat guessing game as well as an associated graph invariant, the guessing number, that has applications to network coding and circuit complexity. In this thesis, to better understand the nature of the guessing number of undirected graphs we apply the concept of saturation to guessing numbers and investigate the extremal and saturation numbers of guessing numbers. We define and determine the extremal number in terms of edges for the guessing number by using the previously established bound of the guessing number by the chromatic number of the complement. We also use the concept of graph entropy, also developed by Søren Riis, to find a constant bound on the saturation number of the guessing number.