Independent Sets from an Algebraic Perspective

Details Independent Sets from an Algebraic Perspective Independent Sets from an Algebraic Perspective

2010-03-18

arxiv.org/abs/1003.3508v2

Mathematics

Commutative Algebra

Final version

Scientific paper

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 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\"obner 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\"obner methods lies in the description of the standard monomials.

Affiliated with

Also associated with

No associations

Rating

Independent Sets from an Algebraic Perspective does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Independent Sets from an Algebraic Perspective, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Independent Sets from an Algebraic Perspective will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-700101