Author ORCID Identifier
Date Available
4-27-2017
Year of Publication
2017
Document Type
Doctoral Dissertation
Degree Name
Doctor of Philosophy (PhD)
College
Arts and Sciences
Department/School/Program
Mathematics
Advisor
Dr. Carl W. Lee
Abstract
The game of Subset Take-Away is an impartial combinatorial game posed by David Gale in 1974. The game can be played on various discrete structures, including but not limited to graphs, hypergraphs, polygonal complexes, and partially ordered sets. While a universal winning strategy has yet to be found, results have been found in certain cases. In 2003 R. Riehemann focused on Subset Take-Away on bipartite graphs and produced a complete game analysis by studying nim-values. In this work, we extend the notion of Take-Away on a bipartite graph to Take-Away on particular hypergraphs, namely oddly-uniform hypergraphs and evenly-uniform hypergraphs whose vertices satisfy a particular coloring condition. On both structures we provide a complete game analysis via nim-values. From here, we consider different discrete structures and slight variations of the rules for Take-Away to produce some interesting results. Under certain conditions, polygonal complexes exhibit a sequence of nim-values which are unbounded but have a well-behaved pattern. Under other conditions, the nim-value of a polygonal complex is bounded and predictable based on information about the complex itself. We introduce a Take-Away variant which we call “Take-As-Much-As-You-Want”, and we show that, again, nim-values can grow without bound, but fortunately they are very easily described for a given graph based on the total number of vertices and edges of the graph. Finally we consider Take-Away on a specific type of partially ordered set which we call a rank-complete poset. We have results, again via an analysis of nim-values, for Take-Away on a rank-complete poset for both ordinary play as well as misère play.
Digital Object Identifier (DOI)
https://doi.org/10.13023/ETD.2017.151
Recommended Citation
Barnard, Kristen M., "Some Take-Away Games on Discrete Structures" (2017). Theses and Dissertations--Mathematics. 44.
https://uknowledge.uky.edu/math_etds/44
