Independent sets from an algebraic perspective
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 CohenMacaulay graphs nor Hilbert series of initial ide...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_02181967_v22_n2_p_Dickenstein |
| Aporte de: |
| Sumario: | 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 CohenMacaulay 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. © 2012 World Scientific Publishing Company. |
|---|