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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Dickenstein, A., Tobis, E.A.
Formato: JOUR
Materias:
antichains
complexity
Gröbner basis
Hilbert series
Independent sets
posets
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_02181967_v22_n2_p_Dickenstein
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_02181967_v22_n2_p_Dickenstein
record_format dspace
spelling todo:paper_02181967_v22_n2_p_Dickenstein2023-10-03T15:10:47Z Independent sets from an algebraic perspective Dickenstein, A. Tobis, E.A. antichains complexity Gröbner basis Hilbert series Independent sets posets 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. Fil:Dickenstein, A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Tobis, E.A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_02181967_v22_n2_p_Dickenstein
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic antichains
complexity
Gröbner basis
Hilbert series
Independent sets
posets
spellingShingle antichains
complexity
Gröbner basis
Hilbert series
Independent sets
posets
Dickenstein, A.
Tobis, E.A.
Independent sets from an algebraic perspective
topic_facet antichains
complexity
Gröbner basis
Hilbert series
Independent sets
posets
description 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.
format JOUR
author Dickenstein, A.
Tobis, E.A.
author_facet Dickenstein, A.
Tobis, E.A.
author_sort Dickenstein, A.
title Independent sets from an algebraic perspective
title_short Independent sets from an algebraic perspective
title_full Independent sets from an algebraic perspective
title_fullStr Independent sets from an algebraic perspective
title_full_unstemmed Independent sets from an algebraic perspective
title_sort independent sets from an algebraic perspective
url http://hdl.handle.net/20.500.12110/paper_02181967_v22_n2_p_Dickenstein
work_keys_str_mv AT dickensteina independentsetsfromanalgebraicperspective
AT tobisea independentsetsfromanalgebraicperspective
_version_ 1807322103149494272

Ejemplares similares