Content area
Abstract
This thesis deals with combinatorial 1-player games that behave in such a manner that if there is any way for the player to play from a given start position p to some terminal position t in, say, n moves, then however the player chooses to play the game from p, it will always end in position t and always in exactly n moves. A game with this property is called strongly convergent. The main contents of the thesis can be summarized as follows. (1) We prove that strong convergence is equivalent to having what we call the 'polygon property', which seemingly is a weaker condition. A lot of examples of strongly convergent games are presented. (2) In particular, the numbers game (invented by S. Mozes) is investigated thoroughly. This game is played on a graph with real numbers on the nodes. A legal move consists of choosing a node with a negative number, adding this number to the numbers of the neighbors, and finally reversing its sign. Weighted versions are also considered, with weights on both edges and nodes. We characterize the N-games, i.e., the weighted numbers games that are strongly convergent. The language of all legal play sequences, where the letters are the played nodes, is shown to be a greedoid for all start positions of every N-game. The question of deciding whether one position is reachable from another is discussed. Decidability is proved in certain cases. The set of games that can go in a loop is classified, and also those games that always terminate whatever the start position, to N-games. (3) The connection between the numbers game and Coxeter groups is explored. We show that the game group, i.e., the group of linear transformations of the position that is generated by the moves, is a Coxeter group for certain N-games. Conversely, every Coxeter group can be represented by any member of a whole family of N-games. This family contains the canonical geometric representation of the Coxeter group. Almost all phenomena that came up during the analysis of the games correspond in a natural way to well-known concepts in Coxeter group theory. For example, the graph on which the game is played is isomorphic to the Coxeter graph of the group. The polygon property of N-games motivates the definition of a class of axiomatically defined 'polygon posets'. We show how these polygon posets in a simple way correspond to what may be called ideals in the weak order of Coxeter groups.
