Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals

DOI10.1016/J.JALGEBRA.2010.10.025MaRDI QIDQ716459zbMATH OpenOpenAlexFDO

Authors Christopher A. Francisco, Adam Van Tuyl, Huy Tài Hà

Publication date 22 September 2011

Published in Journal of Algebra (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberedge idealhypergraphsmonomial idealsperfect graphsassociated primesAlexander dualitypowers of idealscover idealsaturated chain propertystability and persistence of associated primes

Mathematics Subject Classification ID

Combinatorial aspects of commutative algebra (05E40) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Algebraic combinatorics (05E99) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Perfect graphs (05C17) Theory of modules and ideals in commutative rings (13C99)

Abstract: There is a natural one-to-one correspondence between squarefree monomial ideals and finite simple hypergraphs via the cover ideal construction. Let H be a finite simple hypergraph, and let J = J(H) be its cover ideal in a polynomial ring R. We give an explicit description of all associated primes of R/J^s, for any power J^s of J, in terms of the coloring properties of hypergraphs arising from H. We also give an algebraic method for determining the chromatic number of H, proving that it is equivalent to a monomial ideal membership problem involving powers of J. Our work yields two new purely algebraic characterizations of perfect graphs, independent of the Strong Perfect Graph Theorem; the first characterization is in terms of the sets Ass(R/J^s), while the second characterization is in terms of the saturated chain condition for associated primes.

Recommendations

• Powers of Square-Free Monomial Ideals and Combinatorics
• Associated primes of monomial ideals and odd holes in graphs
• Asymptotic growth of associated primes of certain graph ideals
• In the shadows of a hypergraph: looking for associated primes of powers of square-free monomial ideals
• The coloring ideal and coloring complex of a graph

Cites work

• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A conjecture on critical graphs and connections to the persistence of associated primes
• Associated primes of monomial ideals and odd holes in graphs
• Asymptotic Stability of Ass(M/I n M)
• Cohen-Macaulay graphs
• Combinatorial secant varieties
• EdgeIdeals: a package for (hyper)graphs
• Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers
• On associated primes of initial ideals
• On the ideal of an embedded join.
• Rees algebras and polyhedral cones of ideals of vertex covers of perfect graphs
• Stability of associated primes of monomial ideals
• Symbolic powers of monomial ideals and vertex cover algebras
• The associated primes of initial ideals of lattice ideals
• The chain property for the associated primes of \(\mathcal A\)-graded ideals.
• The strong perfect graph theorem

Cited in

(48)

• The strong persistence property and symbolic strong persistence property
• Expansion and contraction functors on matriods
• Associated primes of monomial ideals and odd holes in graphs
• Equality of ordinary and symbolic powers of Stanley-Reisner ideals
• A conjecture on critical graphs and connections to the persistence of associated primes
• The uniform face ideals of a simplicial complex
• Associated primes of \(h\)-wheels
• On the stable set of associated prime ideals of a monomial ideal
• Normality and associated primes of closed neighborhood ideals and dominating ideals
• Stanley-Reisner rings
• On the resurgence and asymptotic resurgence of homogeneous ideals
• On the associated primes and the depth of the second power of squarefree monomial ideals
• Persistence and stability properties of powers of ideals
• Monomial invariants applied to graph coloring
• The stable set of associated prime ideals of a polymatroidal ideal
• The coloring ideal and coloring complex of a graph
• Discrete polymatroids satisfying a stronger symmetric exchange property
• Depth of powers of generalized Hibi ideals
• On the Alexander dual of the path ideals of rooted and unrooted trees
• Associated primes of powers of edge ideals
• Generalized cover ideals and the persistence property
• On the stable set of associated prime ideals of monomial ideals and square-free monomial ideals
• Depth and regularity modulo a principal ideal
• In the shadows of a hypergraph: looking for associated primes of powers of square-free monomial ideals
• On the strong persistence property and normality of cover ideals of theta graphs
• On the embedded associated primes of monomial ideals
• Path ideals of weighted graphs
• Homotopy and Hom construction in the category of finite hypergraphs
• Associated primes of powers of cover ideals under graph operations
• Associated primes of powers of edge ideals and ear decompositions of graphs
• Dominating ideals and closed neighborhood ideals of graphs
• Symbolic powers of cover ideal of very well-covered and bipartite graphs
• Asymptotic growth of associated primes of certain graph ideals
• Combinatorial characterizations of the saturation and the associated primes of the fourth power of edge ideals
• Regular sequences on squares of monomial ideals
• Monomial ideals whose depth function has any given number of strict local maxima
• Squarefree monomial ideals that fail the persistence property and non-increasing depth
• Classes of normally and nearly normally torsion-free monomial ideals
• A NEW PROOF OF THE PERSISTENCE PROPERTY FOR IDEALS IN DEDEKIND RINGS AND PR¨UFER DOMAINS
• On powers of some classes of monomial ideals
• Stabilization of associated prime ideals of monomial ideals -- bounding the copersistence index
• Superficial ideals for monomial ideals
• A note on the Alexander dual of path ideals of rooted trees
• Persistence property for some classes of monomial ideals of a polynomial ring
• Strong persistence and associated primes of powers of monomial ideals
• Expansions of monomial ideals and multigraded modules
• Saturation and associated primes of powers of edge ideals
• Expansion of a simplicial complex

Describes a project that uses

Uses Software

• EdgeIdeals
• Macaulay2
• CoCoA

This page was built for publication: Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals

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