Details:
Title  Independent sets from an algebraic perspective.  Author(s)  Alicia Dickenstein, Enrique A. Tobis  Type  Article in Journal  Abstract  In 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 zerodimensional complete intersections ideals, can be evaluated in polynomial time, unless #P = P. Moreover, we present a family of radical zerodimensional 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.
 Keywords  Independent sets; antichains; posets; Gröbner basis; Hilbert series; complexity  ISSN  02181967; 17936500/e 
URL 
http://www.worldscientific.com/doi/abs/10.1142/S0218196711006819 
Language  English  Journal  Int. J. Algebra Comput.  Volume  22  Number  2  Pages  1250014, 15  Publisher  World Scientific, Singapore  Year  2012  Edition  0  Translation 
No  Refereed 
No 
