Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleFrom monomials to words to graphs
Author(s) Cristina G. Fernandes, Edward L. Green, Arnaldo Mandel
TypeArticle in Journal
AbstractGiven 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 NP-complete. The latter problem is closely related to the recognition problem for comparability graphs.
KeywordsGröbner bases, Polynomials, Comparability graphs, Blocking polyhedron
URL http://www.sciencedirect.com/science/article/pii/S0097316503001833
JournalJournal of Combinatorial Theory, Series A
Pages185 - 206
Translation No
Refereed No