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

Details:

   
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
LanguageEnglish
JournalInt. J. Algebra Comput.
Volume22
Number2
Pages1250014, 15
PublisherWorld Scientific, Singapore
Year2012
Edition0
Translation No
Refereed No
Webmaster