We consider the two-player game chomp on posets associated to numerical semigroups and show that the analysis of strategies for chomp is strongly related to classical properties of semigroups. We characterize which player has a winning-strategy for symmetric semigroups, semigroups of maximal embedding dimension and several families of numerical semigroups generated by arithmetic sequences. Furthermore, we show that which player wins on a given numerical semigroup is a decidable question. Finally, we extend several of our results to the more general setting of subsemigroups of , where is a finite abelian group.
Revised: 2018-02-15
Accepted: 2018-02-19
Published online: 2018-06-28
DOI: https://doi.org/10.5802/alco.16
Classification: 05E40, 91A46, 06A07
Keywords: chomp game, poset game, infinite poset, numerical semigroup, symmetric semigroup, Apéry set
@article{ALCO_2018__1_3_371_0,
author = {Garc\'\i a-Marco, Ignacio and Knauer, Kolja},
title = {Chomp on numerical semigroups},
journal = {Algebraic Combinatorics},
pages = {371--394},
publisher = {MathOA foundation},
volume = {1},
number = {3},
year = {2018},
doi = {10.5802/alco.16},
zbl = {06897706},
mrnumber = {3856529},
language = {en},
url = {alco.centre-mersenne.org/item/ALCO_2018__1_3_371_0/}
}
García-Marco, Ignacio; Knauer, Kolja. Chomp on numerical semigroups. Algebraic Combinatorics, Volume 1 (2018) no. 3, pp. 371-394. doi : 10.5802/alco.16. https://alco.centre-mersenne.org/item/ALCO_2018__1_3_371_0/
[1] Maximality properties in numerical semigroups and applications to one-dimensional analytically irreducible local domains, Mem. Amer. Math. Soc., Volume 125 (1997) no. 598, p. x+78 | Article | MR 1357822 | Zbl 0868.13003
[2] Algebraic invariants of projective monomial curves associated to generalized arithmetic sequences, J. Symb. Comput., Volume 81 (2017), pp. 1-19 | Article | MR 3594321 | Zbl 1365.14066
[3] Nim, a game with a complete mathematical theory, Ann. Math., Volume 3 (1901/02) no. 1-4, pp. 35-39 | Article | MR 1502275 | Zbl 32.0225.02
[4] The game of Chomp (https://www.win.tue.nl/~aeb/games/chomp.html)
[5] Möbius function of semigroup posets through Hilbert series, J. Comb. Theory, Ser. A, Volume 136 (2015), pp. 238-251 | Article | MR 3383277 | Zbl 1322.06001
[6] On the Möbius function of the locally finite poset associated with a numerical semigroup, Semigroup Forum, Volume 87 (2013) no. 2, pp. 313-330 | Article | MR 3110597 | Zbl 1284.20069
[7] A combinatorial identity involving relatively prime integers, J. Comb. Theory, Ser. A, Volume 26 (1979) no. 2, pp. 189-192 | Article | MR 530291 | Zbl 0414.05005
[8] A note on symmetric semigroups and almost arithmetic sequences, Commun. Algebra, Volume 22 (1994) no. 10, pp. 3903-3905 | Article | MR 1280099 | Zbl 0832.20083
[9] The second Feng–Rao number for codes coming from telescopic semigroups, Des. Codes Cryptogr. (2017) | Article | Zbl 06898275
[10] Combinatorial game complexity: an introduction with poset games, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS (2015) no. 116, pp. 42-75 | MR 3409607 | Zbl 1409.68137
[11] On numerical semigroups, Semigroup Forum, Volume 35 (1987) no. 1, pp. 63-83 | Article | MR 880351 | Zbl 0614.10046
[12] A curious Nim-type game, Amer. Math. Monthly, Volume 81 (1974), pp. 876-879 | Article | MR 0354029 | Zbl 0295.90045
[13] Cayley posets (in preparation)
[14] Numerical semigroups generated by intervals, Pac. J. Math., Volume 191 (1999) no. 1, pp. 75-83 | Article | MR 1725463 | Zbl 1009.20069
[15] The value-semigroup of a one-dimensional Gorenstein ring, Proc. Am. Math. Soc., Volume 25 (1970), pp. 748-751 | Article | MR 0265353 | Zbl 0197.31401
[16] Computing the degree of a lattice ideal of dimension one, J. Symb. Comput., Volume 65 (2014), pp. 15-28 | Article | MR 3181378 | Zbl 1322.13009
[17] On numerical semigroups generated by generalized arithmetic sequences, Commun. Algebra, Volume 32 (2004) no. 9, pp. 3459-3469 | Article | MR 2097471 | Zbl 1070.20069
[18] Complete intersection lattice ideals, J. Algebra, Volume 284 (2005) no. 2, pp. 755-770 | Article | MR 2114578 | Zbl 1076.13006
[19] The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications, Volume 30, Oxford University Press, 2005, xvi+243 pages | Article | MR 2260521 | Zbl 1134.11012
[20] Numerical semigroups: Apéry sets and Hilbert series, Semigroup Forum, Volume 79 (2009) no. 2, pp. 323-340 | Article | MR 2538729 | Zbl 1200.20047
[21] On symmetric numerical semigroups, J. Algebra, Volume 182 (1996) no. 2, pp. 422-434 | Article | MR 1391591 | Zbl 0856.20043
[22] Numerical semigroups, Developments in Mathematics, Volume 20, Springer, 2009, x+181 pages | Article | MR 2549780 | Zbl 1220.20047
[23] Numerical semigroups with maximal embedding dimension, Int. J. Commut. Rings, Volume 2 (2003) no. 1, pp. 47-53 | MR 2056070 | Zbl 1090.20033
[24] Spel van delers (The game of divisors), Nieuw Tijdschrift voor Wiskunde, Volume 39 (1952), pp. 299-304
[25] On the linear Diophantine problem of Frobenius, J. Reine Angew. Math., Volume 293/294 (1977), pp. 1-17 | Article | MR 0441855 | Zbl 0349.10009
[26] Minimal free resolution of the associated graded ring of monomial curves of generalized arithmetic sequences, J. Pure Appl. Algebra, Volume 213 (2009) no. 3, pp. 360-369 | Article | MR 2477055 | Zbl 1167.13001
