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


TitleIndependent sets from an algebraic perspective.
Author(s) Alicia Dickenstein, Enrique A. Tobis
TypeArticle in Journal
AbstractIn this paper, we study the basic problem of counting independent sets in a graph and, in particular, the problem of counting antichains in a finite poset, from an algebraic perspective. We show that neither independence polynomials of bipartite Cohen–Macaulay graphs nor Hilbert series of initial ideals of radical zero-dimensional complete intersections ideals, can be evaluated in polynomial time, unless #P = P. Moreover, we present a family of radical zero-dimensional complete intersection ideals JP associated to a finite poset P, for which we describe a universal Gröbner basis. This implies that the bottleneck in computing the dimension of the quotient by JP (that is, the number of zeros of JP) using Gröbner methods lies in the description of the standard monomials.

KeywordsIndependent sets; antichains; posets; Gröbner basis; Hilbert series; complexity
ISSN0218-1967; 1793-6500/e
URL http://www.worldscientific.com/doi/abs/10.1142/S0218196711006819
JournalInt. J. Algebra Comput.
Pages1250014, 15
PublisherWorld Scientific, Singapore
Translation No
Refereed No