{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T22:22:30Z","timestamp":1648851750022},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p> 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\u2013Macaulay 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<jats:sub>P<\/jats:sub> associated to a finite poset P, for which we describe a universal Gr\u00f6bner basis. This implies that the bottleneck in computing the dimension of the quotient by J<jats:sub>P<\/jats:sub> (that is, the number of zeros of J<jats:sub>P<\/jats:sub>) using Gr\u00f6bner methods lies in the description of the standard monomials. <\/jats:p>","DOI":"10.1142\/s0218196711006819","type":"journal-article","created":{"date-parts":[[2011,8,29]],"date-time":"2011-08-29T05:26:06Z","timestamp":1314595566000},"page":"1250014","source":"Crossref","is-referenced-by-count":3,"title":["INDEPENDENT SETS FROM AN ALGEBRAIC PERSPECTIVE"],"prefix":"10.1142","volume":"22","author":[{"given":"ALICIA","family":"DICKENSTEIN","sequence":"first","affiliation":[{"name":"Departamento de Matem\u00e1tica, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ENRIQUE A.","family":"TOBIS","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1tica, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0747-7171(92)90024-X"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1023\/B:JACO.0000030703.39946.70"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.05.003"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.04.004"},{"key":"rf7","series-title":"Undergraduate Texts in Mathematics","volume-title":"Ideals, Varieties, and Algorithms","author":"Cox D.","year":"1997"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6911-1"},{"key":"rf9","volume-title":"Advances in Graph Theory and Applications","author":"Dickenstein A.","year":"2007"},{"key":"rf11","volume":"1","author":"Francisco C. A.","journal-title":"J. Softw. Algebra Geom."},{"key":"rf14","first-page":"145","volume":"1","author":"Hashemi A.","journal-title":"Albanian J. Math."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006431609027"},{"key":"rf16","series-title":"Cambridge Studies in Advanced Mathematics","volume-title":"Cohen\u2013Macaulay Rings","volume":"39","author":"Herzog J.","year":"1993"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-005-4528-1"},{"key":"rf18","volume-title":"Computational Commutative Algebra 2","author":"Kreuzer M.","year":"2005"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)00057-X"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.1994.1192"},{"key":"rf24","series-title":"Progress in Mathematics","volume-title":"Combinatorics and Commutative Algebra","volume":"41","author":"Stanley R. P.","year":"1996"},{"key":"rf25","first-page":"1432","volume":"66","author":"Rodr\u00edguez R. H. Villarreal","journal-title":"Manuscripta Math."},{"key":"rf26","series-title":"Pure and Applied Mathematics","volume-title":"Monomial Algebras","author":"Rodr\u00edguez R. H. Villarreal","year":"2001"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196711006819","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T08:40:52Z","timestamp":1565167252000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196711006819"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":19,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2012,3]]}},"alternative-id":["10.1142\/S0218196711006819"],"URL":"https:\/\/doi.org\/10.1142\/s0218196711006819","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}