Chomp on numerical semigroups. (English) Zbl 1394.91066
Summary: 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 \(\mathbb{N} \times T\), where \(T\) is a finite abelian group.
MSC:
| 91A46 | Combinatorial games |
| 06A07 | Combinatorics of partially ordered sets |
| 20M14 | Commutative semigroups |
Keywords:
chomp game; poset game; infinite poset; numerical semigroup; symmetric semigroup; Apéry setReferences:
| [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., 125, 598, (1997) · Zbl 0868.13003 · doi:10.1090/memo/0598 |
| [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., 81, 1-19, (2017) · Zbl 1365.14066 · doi:10.1016/j.jsc.2016.11.001 |
| [3] | Bouton, C. L., Nim, a game with a complete mathematical theory, Ann. Math., 3, 1-4, 35-39, (190102) · JFM 32.0225.02 · doi:10.2307/1967631 |
| [4] | Brouwer, Andries E., The game of Chomp · Zbl 1184.91056 |
| [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, 136, 238-251, (2015) · Zbl 1322.06001 · doi:10.1016/j.jcta.2015.07.006 |
| [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, 87, 2, 313-330, (2013) · Zbl 1284.20069 · doi:10.1007/s00233-012-9458-3 |
| [7] | Deddens, James A., A combinatorial identity involving relatively prime integers, J. Comb. Theory, Ser. A, 26, 2, 189-192, (1979) · Zbl 0414.05005 · doi:10.1016/0097-3165(79)90069-4 |
| [8] | Estrada, Mario; López, Alejandro, A note on symmetric semigroups and almost arithmetic sequences, Commun. Algebra, 22, 10, 3903-3905, (1994) · Zbl 0832.20083 · doi:10.1080/00927879408825056 |
| [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) · Zbl 1402.94117 · doi:10.1007/s10623-017-0426-5 |
| [10] | Fenner, Stephen A.; Rogers, John, Combinatorial game complexity: an introduction with poset games, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 116, 42-75, (2015) · Zbl 1409.68137 |
| [11] | Fröberg, Ralf; Gottlieb, Christian; Häggkvist, Roland, On numerical semigroups, Semigroup Forum, 35, 1, 63-83, (1987) · Zbl 0614.10046 · doi:10.1007/BF02573091 |
| [12] | Gale, David, A curious nim-type game, Amer. Math. Monthly, 81, 876-879, (1974) · Zbl 0295.90045 · doi:10.2307/2319446 |
| [13] | García-Marco, Ignacio; Knauer, Kolja, Cayley posets |
| [14] | García-Sánchez, Pedro A.; Rosales, José Carlos, Numerical semigroups generated by intervals, Pac. J. Math., 191, 1, 75-83, (1999) · Zbl 1009.20069 · doi:10.2140/pjm.1999.191.75 |
| [15] | Kunz, Ernst, The value-semigroup of a one-dimensional Gorenstein ring, Proc. Am. Math. Soc., 25, 748-751, (1970) · Zbl 0197.31401 · doi:10.2307/2036742 |
| [16] | López, Hiram H.; Villarreal, Rafael H., Computing the degree of a lattice ideal of dimension one, J. Symb. Comput., 65, 15-28, (2014) · Zbl 1322.13009 · doi:10.1016/j.jsc.2014.01.002 |
| [17] | Matthews, Gretchen L., On numerical semigroups generated by generalized arithmetic sequences, Commun. Algebra, 32, 9, 3459-3469, (2004) · Zbl 1070.20069 · doi:10.1081/AGB-120039623 |
| [18] | Morales, Marcel; Thoma, Apostolos, Complete intersection lattice ideals, J. Algebra, 284, 2, 755-770, (2005) · Zbl 1076.13006 · doi:10.1016/j.jalgebra.2004.10.011 |
| [19] | Ramírez Alfonsín, Jorge Luis, The Diophantine Frobenius problem, 30, xvi+243 pp., (2005), Oxford University Press · Zbl 1134.11012 · doi:10.1093/acprof:oso/9780198568209.001.0001 |
| [20] | Ramírez Alfonsín, Jorge Luis; Rødseth, Øystein J., Numerical semigroups: apéry sets and Hilbert series, Semigroup Forum, 79, 2, 323-340, (2009) · Zbl 1200.20047 · doi:10.1007/s00233-009-9133-5 |
| [21] | Rosales, José Carlos, On symmetric numerical semigroups, J. Algebra, 182, 2, 422-434, (1996) · Zbl 0856.20043 · doi:10.1006/jabr.1996.0178 |
| [22] | Rosales, José Carlos; García-Sánchez, Pedro A., Numerical semigroups, 20, x+181 pp., (2009), Springer · Zbl 1220.20047 · doi:10.1007/978-1-4419-0160-6 |
| [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, 2, 1, 47-53, (2003) · Zbl 1090.20033 |
| [24] | Schuh, F., Spel Van delers (the game of divisors), Nieuw Tijdschrift voor Wiskunde, 39, 299-304, (1952) |
| [25] | Selmer, Ernst S., On the linear Diophantine problem of Frobenius, J. Reine Angew. Math., 293/294, 1-17, (1977) · Zbl 0349.10009 · doi:10.1515/crll.1977.293-294.1 |
| [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, 213, 3, 360-369, (2009) · Zbl 1167.13001 · doi:10.1016/j.jpaa.2008.07.007 |
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.
