Independent Sets from an Algebraic Perspective,

A. DICKENSTEIN, E. TOBIS

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION

WORLD SCIENTIFIC PUBL CO PTE LTD

Año: 2012 vol. 22 p. 14 - 29

0218-1967

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 J_P 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 J_P (that is, the number of zeros of J_P) using Gröbner methods lies in the description of the standard monomials.