Details:
Title  From monomials to words to graphs  Author(s)  Cristina G. Fernandes, Edward L. Green, Arnaldo Mandel  Type  Article in Journal  Abstract  Given 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 Gröbner 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 ≺ such that 〈σ≺(I)〉 is finitely generated turns out to be NPcomplete. The latter problem is closely related to the recognition problem for comparability graphs.  Keywords  Gröbner bases, Polynomials, Comparability graphs, Blocking polyhedron  ISSN  00973165 
URL 
http://www.sciencedirect.com/science/article/pii/S0097316503001833 
Language  English  Journal  Journal of Combinatorial Theory, Series A  Volume  105  Number  2  Pages  185  206  Year  2004  Edition  0  Translation 
No  Refereed 
No 
