Impartial achievement and avoidance games for generating finite groups

• DOI: 10.1007/s00182-017-0602-x
• Publication Date: 2017-12-07T10:13:13Z
• Authors: Dana C. Ernst; Nándor Sieben
• Keywords: FOS: Mathematics; Mathematics - Combinatorics; Combinatorics (math.CO); Group Theory (math.GR); 0102 computer and information sciences; 91A46, 20D30; Mathematics - Group Theory; 01 natural sciences

28 pages, 44 figures. Revised in response to comments from referee<br/>We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some conjectures based on computer calculations. Our main computational and theoretical tool is the structure diagram of a game, which is a type of identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet intuitive visualizations of these games that capture the complexity of the positions.<br/>