From Monomials to Words to graphs

Simple item page
dc.creatorFernandes, Cristina G.
dc.creatorGreen, Edward L.
dc.creatorMandel, Arnaldo
dc.date2003-02-20
dc.date.accessioned2026-07-07T04:55:27Z
dc.date.available2026-07-07T04:55:27Z
dc.descriptionGiven a finite alphabet X and an ordering on the letters, the map σsends each monomial on X to the word that is the ordered product of the letter powers in the monomial. Motivated by a question on Groebner bases, we characterize ideals I in the free commutative monoid (in terms of a generating set) such that the ideal <σ(I)> generated by σ(I) in the free monoid is finitely generated. Whether there exists an ordering such that <σ(I)> is finitely generated turns out to be NP-complete. The latter problem is closely related to the recognition problem for comparability graphs.
dc.description27 pages, 2 postscript figures, uses gastex.sty
dc.identifierhttps://arxiv.org/abs/math/0302252
dc.identifierhttp://arxiv.org/abs/math/0302252
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/66585
dc.subjectCommutative Algebra
dc.subjectCombinatorics
dc.subjectGroup Theory
dc.subject13P10;68R15;05C17;16Z05;68Q25
dc.titleFrom Monomials to Words to graphs
dc.typetext

Files

Collections

arXiv