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

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

85 citations recorded by the source corpus.

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.

Subfields: Algebra and Number Theory, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/0c71a81cafad154a4e16edd240d63c1c394e905a

Citations in the corpus

• Associated primes of powers of edge ideals (2011, unknown): “The first case is the family of normal ideals (as was pointed out above), which includes, for instance, ideals of vertex covers of perfect graphs [7,8,27].”