Independent sets from an algebraic perspective

DOI10.1142/S0218196711006819MaRDI QIDQ5389114zbMATH OpenOpenAlexFDO

Authors Alicia Dickenstein, Enrique A. Tobis

Publication date 24 April 2012

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.3508

zbMATH Keywords

antichainscomplexityGröbner basisHilbert seriesindependent setsposets

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorics of partially ordered sets (06A07) Algebraic aspects of posets (06A11) Computational aspects and applications of commutative rings (13P99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

Recommendations

• Solving the \(k\)-independent sets problem of graphs by Gröbner bases
• The monomial ideal of independent sets associated to a graph
• Computing dimension and independent sets for polynomial ideals
• Counting independent sets in graphs of hyperplane arrangements
• A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks

Cites work

• Computation of Hilbert functions
• Counting solutions to binomial complete intersections
• Distributive lattices, bipartite graphs and Alexander duality
• scientific article; zbMATH DE number 2206382 (Why is no real title available?)
• Independence polynomials of circulants with an application to music
• On the ideal theory of graphs
• On the location of roots of independence polynomials
• Stable sets and polynomials
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The number of unlabeled orders on fourteen elements

Cited in

(3)

• Independent sets and second category
• Enumeration and classification of self-orthogonal partial Latin rectangles by using the polynomial method
• Robust toric ideals

Describes a project that uses

Uses Software

• Macaulay2
• CoCoA
• SINGULAR
• EdgeIdeals

This page was built for publication: Independent sets from an algebraic perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5389114)