ALGEBRAIC COMBINATORICS

Chomp on numerical semigroups
Algebraic Combinatorics, Volume 1 (2018) no. 3, p. 371-394
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 ℕ×T, where T is a finite abelian group.
Received : 2017-10-04
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},
     publisher = {MathOA foundation},
     volume = {1},
     number = {3},
     year = {2018},
     pages = {371-394},
     doi = {10.5802/alco.16},
     zbl = {06897706},
     mrnumber = {3856529},
     language = {en},
     url = {https://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] Barucci, Valentina; Dobbs, David E.; Fontana, Marco Maximality properties in numerical semigroups and applications to one-dimensional analytically irreducible local domains, Mem. Amer. Math. Soc., Volume 125 (1997) no. 598, x+78 pages | Article | MR 1357822 | Zbl 0868.13003

[2] Bermejo, Isabel; García-Llorente, Eva; García-Marco, Ignacio 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] Bouton, C. L. 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] Brouwer, Andries E. The game of Chomp (https://www.win.tue.nl/~aeb/games/chomp.html )

[5] Chappelon, Jonathan; García-Marco, Ignacio; Montejano, Luis Pedro; Ramírez Alfonsín, Jorge Luis 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] Chappelon, Jonathan; Ramírez Alfonsín, Jorge Luis 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] Deddens, James A. 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] Estrada, Mario; López, Alejandro 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] Farrán, José I.; García-Sánchez, Pedro A.; Heredia, Benjamin A.; Leamer, Micah J. The second Feng–Rao number for codes coming from telescopic semigroups, Des. Codes Cryptogr. (2017) | Article | Zbl 06898275

[10] Fenner, Stephen A.; Rogers, John Combinatorial game complexity: an introduction with poset games, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS (2015) no. 116, pp. 42-75 | MR 3409607

[11] Fröberg, Ralf; Gottlieb, Christian; Häggkvist, Roland On numerical semigroups, Semigroup Forum, Volume 35 (1987) no. 1, pp. 63-83 | Article | MR 880351 | Zbl 0614.10046

[12] Gale, David A curious Nim-type game, Amer. Math. Monthly, Volume 81 (1974), pp. 876-879 | Article | MR 0354029 | Zbl 0295.90045

[13] García-Marco, Ignacio; Knauer, Kolja Cayley posets (in preparation)

[14] García-Sánchez, Pedro A.; Rosales, José Carlos Numerical semigroups generated by intervals, Pac. J. Math., Volume 191 (1999) no. 1, pp. 75-83 | Article | MR 1725463 | Zbl 1009.20069

[15] Kunz, Ernst 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] López, Hiram H.; Villarreal, Rafael H. 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] Matthews, Gretchen L. 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] Morales, Marcel; Thoma, Apostolos Complete intersection lattice ideals, J. Algebra, Volume 284 (2005) no. 2, pp. 755-770 | Article | MR 2114578 | Zbl 1076.13006

[19] Ramírez Alfonsín, Jorge Luis The Diophantine Frobenius problem, Oxford University Press, Oxford Lecture Series in Mathematics and its Applications, Volume 30 (2005), xvi+243 pages | Article | MR 2260521 | Zbl 1134.11012

[20] Ramírez Alfonsín, Jorge Luis; Rødseth, Øystein J. 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] Rosales, José Carlos On symmetric numerical semigroups, J. Algebra, Volume 182 (1996) no. 2, pp. 422-434 | Article | MR 1391591 | Zbl 0856.20043

[22] Rosales, José Carlos; García-Sánchez, Pedro A. Numerical semigroups, Springer, Developments in Mathematics, Volume 20 (2009), x+181 pages | Article | MR 2549780 | Zbl 1220.20047

[23] Rosales, José Carlos; García-Sánchez, Pedro A.; García-García, Juan Ignacio; Branco, Manuel Batista Numerical semigroups with maximal embedding dimension, Int. J. Commut. Rings, Volume 2 (2003) no. 1, pp. 47-53 | MR 2056070 | Zbl 1090.20033

[24] Schuh, F. Spel van delers (The game of divisors), Nieuw Tijdschrift voor Wiskunde, Volume 39 (1952), pp. 299-304

[25] Selmer, Ernst S. 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] Sharifan, Leila; Zaare-Nahandi, Rashid 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