Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:Independent sets from an algebraic perspective
Autor:Dickenstein, A.; Tobis, E.A.
Filiación:Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Children's Hospital Boston, 300 Longwood Ave., Boston, MA, United States
Palabras clave:antichains; complexity; Gröbner basis; Hilbert series; Independent sets; posets
Año:2012
Volumen:22
Número:2
DOI: http://dx.doi.org/10.1142/S0218196711006819
Título revista:International Journal of Algebra and Computation
Título revista abreviado:Int. J. Algebra Comput.
ISSN:02181967
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02181967_v22_n2_p_Dickenstein

Referencias:

  • Bayer, D., Stillman, M., Computation of hilbert functions (1992) J. Symb. Comput., 14 (1), pp. 31-50
  • Brown, J.I., Hickman, C.A., Nowakowski, R.J., On the location of roots of independence polynomials (2004) J. Algebr. Combin., 19, pp. 273-282
  • Brown, J., Hoshino, R., Independence polynomials of circulants with an application to music (2009) Discrete Math., 309 (8), pp. 2292-2304
  • Cattani, E., Dickenstein, A., Counting solutions to binomial complete intersections (2007) J. Complexity, 23 (1), pp. 82-107
  • Chandreskaran, V., Chertkov, M., Gamarnik, D., Shash, D., Shin, J., (2009) Counting Independent Sets Using the Bethe Approximation, , http://www-math.mit.edu/jinwoos/submitbp.pdf
  • CoCoA: A System for Doing Computations in Commutative Algebra, , http://cocoa.dima.unige.it, CoCoA Team
  • Cox, D., Little, J., O'Shea, D., (1997) Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics, , Springer
  • Cox, D., Little, J., O'Shea, D., (1998) Using Algebraic Geometry, 185. , 2nd edn., Graduate Texts in Mathematics, Springer, New York
  • Dickenstein, A., Tobis, E.A., Tobis, algebraic methods for counting antichains (2007) Advances in Graph Theory and Applications, , eds. J. Scharcasnki and V. Trevisan (UFRGS, Porto Alegre
  • Eppstein, D., All maximal independent sets and dynamic dominance for sparse graphs (2005) Proc. Sixteenth Annual ACM-SIAM Symp. Discrete Algorithms (SIAM, pp. 451-459
  • Francisco, C.A., Hoefel, A., Tuyl, A.V., Edgeideals: A package for (hyper)graphs (2009) J. Softw. Algebra Geom., 1
  • Grayson, D.R., Stillman, M.E., Macaulay 2, a Software System for Research in Algebraic Geometry, , http://www.math.uiuc.edu/Macaulay2
  • Greuel, G.-M., Pfister, G., Schönemann, H., (2009), http://www.singular.uni-kl.de, Singular 3.1.0 - A computer algebra system for polynomial computations; Hashemi, A., Polynomial complexity for hilbert series of borel type ideals (2007) Albanian J. Math., 1 (3), pp. 145-155
  • Heitzig, J., Reinhold, J., The number of unlabeled orders on fourteen elements (1999) Order, 17, pp. 333-341
  • Herzog, J., Bruns, W., (1993) Cohen-Macaulay Rings, Cambridge Studies in Advanced Mathematics, 39. , Cambridge University Press
  • Herzog, J., Hibi, T., Distributive lattices, bipartite graphs and alexander duality (2005) J. Algebr. Combin., 22 (3), pp. 289-302
  • Kreuzer, M., Robbiano, L., (2005) Computational Commutative Algebra, 2. , Springer-Verlag, Heidelberg
  • Levit, V.E., Mandrescu, E., The independence polynomial of a graph - A survey (2005) Proc. 1st Int. Conf. Algebraic Informatics, pp. 233-254. , Aristotle University, Thessaloniki
  • Lovász, L., Stable sets and polynomials (1994) Discrete Math., 124, pp. 137-153
  • Mora, F., Möller, H., Möller, the computation of the hilbert function (1983) EUROCAL 83, 162, pp. 157-167. , Lecture Notes in Computer Science, Springer-Verlag
  • Provan, J.S., Ball, M.O., Ball, the complexity of counting cuts and of computing the probability that a graph is connected (1983) SIAM J. Comput., 12 (4), pp. 777-788
  • Simis, A., Vasconcelos, W., Villarreal Rodríguez, R.H., Villarreal rodríguez, on the ideal theory of graphs (1994) J. Algebra, 167 (2), pp. 389-416
  • Stanley, R.P., (1996) Combinatorics and Commutative Algebra, 41. , 2nd edn., Progress in Mathematics, Birkhäuser Boston, Boston, MA
  • Villarreal Rodríguez, R.H., Cohen-macaulay graphs (1990) Manuscripta Math., 66 (1), pp. 1432-1785
  • Villarreal Rodríguez, R.H., (2001) Monomial Algebras, Pure and Applied Mathematics (CRC
  • Yedidia, A.B., (2009) Counting Independent Sets and Kernels of Regular Graphs, , http://arxiv.org/pdf/0910.4664v1, preprint

Citas:

---------- APA ----------
Dickenstein, A. & Tobis, E.A. (2012) . Independent sets from an algebraic perspective. International Journal of Algebra and Computation, 22(2).
http://dx.doi.org/10.1142/S0218196711006819
---------- CHICAGO ----------
Dickenstein, A., Tobis, E.A. "Independent sets from an algebraic perspective" . International Journal of Algebra and Computation 22, no. 2 (2012).
http://dx.doi.org/10.1142/S0218196711006819
---------- MLA ----------
Dickenstein, A., Tobis, E.A. "Independent sets from an algebraic perspective" . International Journal of Algebra and Computation, vol. 22, no. 2, 2012.
http://dx.doi.org/10.1142/S0218196711006819
---------- VANCOUVER ----------
Dickenstein, A., Tobis, E.A. Independent sets from an algebraic perspective. Int. J. Algebra Comput. 2012;22(2).
http://dx.doi.org/10.1142/S0218196711006819