Relator games on groups. (English) Zbl 1490.91035
Summary: We define two impartial games, the Relator Achievement Game REL and the Relator Avoidance Game RAV. Given a finite group \(G\) and generating set \(S\), both games begin with the empty word. Two players form a word in \(S\) by alternately appending an element from \(S \cup S^{-1}\) at each turn. The first player to form a word equivalent in \(G\) to a previous word wins the game REL but loses the game RAV. Alternatively, one can think of REL and RAV as make a cycle and avoid a cycle games on the Cayley graph \(\Gamma (G, S)\). We determine winning strategies for several families of finite groups including dihedral, dicyclic, and products of cyclic groups.
MSC:
| 91A46 | Combinatorial games |
| 91A05 | 2-person games |
| 91A43 | Games involving graphs |
| 20D60 | Arithmetic and combinatorial problems involving abstract finite groups |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
References:
| [1] | R. Alvarado, M. Averett, B. Gaines, C. Jackson, M.L. Karker, M.A. Marciniak, F. Su and S. Walker, The game of cycles, preprint. · Zbl 1479.91058 |
| [2] | M. Anderson and F. Harary, Achievement and avoidance games for generating abelian groups, Internat. J. Game Theory 16, No. 4 (1987), 321-325. · Zbl 0627.90096 |
| [3] | B.J. Benesh, D.C. Ernst, and N. Sieben, Impartial avoidance and achievement games for generating symmetric and alternating groups, Int. Electron. J. Algebra 20 (2016), 70-85. · Zbl 1342.91007 |
| [4] | B.J. Benesh, D.C. Ernst, and N. Sieben, Impartial avoidance games for generating finite groups, North-West. Eur. J. Math. 2 (2016), 83-103. · Zbl 1414.91077 |
| [5] | B.J. Benesh, D.C. Ernst, and N. Sieben, Impartial achievement games for generating general-ized dihedral groups, Australas. J. Combin. 68 (2017), 371-384. · Zbl 1415.91073 |
| [6] | B.J. Benesh, D.C. Ernst, and N. Sieben, Impartial achievement games for generating nilpotent groups , J. Group Theory 22, No. 3 (2019), 515-527. · Zbl 1472.91010 |
| [7] | B.J. Benesh and M.R. Gaetz, A q-player impartial avoidance game for generating finite groups, Internat. J. Game Theory 47, No. 2 (2018), 451-461. · Zbl 1416.91052 |
| [8] | D.C. Ernst and N. Sieben, Impartial achievement and avoidance games for generating finite groups, Internat. J. Game Theory 47, No. 2 (2018), 509-542. · Zbl 1416.91057 |
| [9] | P. Frankl, On a pursuit game on Cayley graphs, Combinatorica 7 (1987), 67-70. · Zbl 0621.05017 |
| [10] | F. Lehner, Firefighting on trees and Cayley graphs, Australas. J. Combin. 75 (2019), 66-72. · Zbl 1429.05090 |
| [11] | S.-Y.R. Li, N -person Nim and N -person Moore’s games, Internat. J. Game Theory 7 (1978), 31-36. · Zbl 0382.90101 |
| [12] | R. Nowakowski, C. Santos, and A. Silva, Three-player nim with podium rule, Internat. J. Game Theory January (2020), 1-11. |
| [13] | R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math. 43, No. 2-3 (1983), 235-239. · Zbl 0508.05058 |
| [14] | A. Quilliot, Jeux et pointes fixes sur les graphes, Thèse de 3ème cycle, Université de Paris VI, (1978), 131-145. |
| [15] | A. N. Siegel, Combinatorial Game Theory, Volume 146 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 2013. · Zbl 1288.91003 |
| [16] | F. Su, Mathematics for Human Flourishing, Yale University Press, New Haven, CT, 2020. · Zbl 1428.00004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
