Associated primes of monomial ideals and odd holes in graphs
Christopher A. Francisco
, Huy Tài Hà
and Adam Van Tuyl
DOI: 10.1007/s10801-010-0215-y
Abstract
Let G be a finite simple graph with edge ideal I( G). Let I( G) \vee denote the Alexander dual of I( G). We show that a description of all induced cycles of odd length in G is encoded in the associated primes of ( I( G) \vee ) 2. This result forms the basis for a method to detect odd induced cycles of a graph via ideal operations, e.g., intersections, products and colon operations. Moreover, we get a simple algebraic criterion for determining whether a graph is perfect. We also show how to determine the existence of odd holes in a graph from the value of the arithmetic degree of ( I( G) \vee ) 2.
Pages: 287–301
Keywords: keywords edge ideals; odd cycles; perfect graphs; associated primes; arithmetic degree
Full Text: PDF
References
1. Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vušković, K.: Recognizing Berge graphs. Combinatorica 25, 143-186 (2005)
2. Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(2), 51-229 (2006)
3. CoCoATeam: CoCoA: a system for doing Computations in Commutative Algebra. Available at
4. Conforti, M., Cornuéjols, G., Liu, X., Vušković, K., Zambelli, G.: Odd hole recognition in graphs of bounded clique size. SIAM J. Discrete Math. 20, 42-48 (2006)
5. Corso, A., Nagel, U.: Monomial and toric ideals associated to Ferrers graphs. Trans. Am. Math. Soc. 361, 1371-1395 (2009)
6. Dupont, L., Villarreal, R.H.: Vertex covers and irreducible representations of Rees cones. Preprint (2007). arXiv
7. Eisenbud, D., Green, M., Hulek, K., Popescu, S.: Restricting linear syzygies: algebra and geometry. Compos. Math. 141, 1460-1478 (2005)
8. Eisenbud, D., Huneke, C., Vasconcelos, W.: Direct methods for primary decomposition. Invent. Math. 110, 207-235 (1992)
9. Francisco, C.A., Hà, H.T.: Whiskers and sequentially Cohen-Macaulay graphs. J. Comb. Theory Ser. A 115, 304-316 (2008)
10. Francisco, C.A., Hà, H.T., Van Tuyl, A.: Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals. Preprint (2009). arXiv
11. Francisco, C.A., Hoefel, A., Van Tuyl, A.: EdgeIdeals: a package for (hyper)graphs. J. Software Al- gebra Geom. 1, 1-4 (2009)
12. Francisco, C.A., Van Tuyl, A.: Sequentially Cohen-Macaulay edge ideals. Proc. Am. Math. Soc. 135, 2327-2337 (2007)
13. Grayson, D.R., Stillman, M.E.: Macaulay 2, a software system for research in algebraic geometry.
14. Hà, H.T., Morey, S.: Embedded associated primes of powers of square-free monomial ideals. J. Pure Appl. Algebra 214(4), 301-308 (2010)
15. Hà, H.T., Morey, S., Villarreal, R.H.: Cohen-Macaulay admissible clutters. J. Commut. Algebra 1, 463-480 (2009)
16. Hà, H.T., Van Tuyl, A.: Resolutions of square-free monomial ideals via facet ideals: a survey. Contemp. Math. 448, 91-117 (2007)
17. Hà, H.T., Van Tuyl, A.: Splittable ideals and the resolutions of monomial ideals. J. Algebra 309, 405-425 (2007)
18. Hà, H.T., Van Tuyl, A.: Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers. J. Algebr. Comb. 27, 215-245 (2008)
19. Herzog, J., Hibi, T., Trung, N.V.: Symbolic powers of monomial ideals and vertex cover algebras. Adv. Math. 210, 304-322 (2007)
20. Herzog, J., Hibi, T., Zheng, X.: Cohen-Macaulay chordal graphs. J. Comb. Theory Ser. A 113, 911- 916 (2006)
21. Hosten, S., Smith, G.: Monomial ideals. In: Computations in Algebraic Geometry with Macaulay
2. Algorithms and Computations in Mathematics, vol. 8, pp. 73-100. Springer, Berlin (2001)
22. Jacques, S., Katzman, M.: The Betti numbers of forests. Preprint (2005).
23. Miller, E., Sturmfels, B.: Combinatorial Commutative Algebra. GTM, vol.
227. Springer, Berlin (2004)
24. Roth, M., Van Tuyl, A.: On the linear strand of an edge ideal. Commun. Algebra 35, 821-832 (2007)
25. Simis, A., Ulrich, B.: On the ideal of an embedded join. J. Algebra 226, 1-14 (2000)
26. Simis, A., Vasconcelos, W.V., Villarreal, R.H.: On the ideal theory of graphs. J. Algebra 167, 389-416 (1994)
27. Sturmfels, B., Sullivant, S.: Combinatorial secant varieties. Pure Appl. Math. Q. 2, 867-891 (2006)
28. Sturmfels, B., Trung, N.V., Vogel, W.: Bounds on degrees of projective schemes. Math. Ann. 302, 417-432 (1995)
29. Van Tuyl, A., Villarreal, R.: Shellable graphs and sequentially Cohen-Macaulay bipartite graphs.
2. Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(2), 51-229 (2006)
3. CoCoATeam: CoCoA: a system for doing Computations in Commutative Algebra. Available at
4. Conforti, M., Cornuéjols, G., Liu, X., Vušković, K., Zambelli, G.: Odd hole recognition in graphs of bounded clique size. SIAM J. Discrete Math. 20, 42-48 (2006)
5. Corso, A., Nagel, U.: Monomial and toric ideals associated to Ferrers graphs. Trans. Am. Math. Soc. 361, 1371-1395 (2009)
6. Dupont, L., Villarreal, R.H.: Vertex covers and irreducible representations of Rees cones. Preprint (2007). arXiv
7. Eisenbud, D., Green, M., Hulek, K., Popescu, S.: Restricting linear syzygies: algebra and geometry. Compos. Math. 141, 1460-1478 (2005)
8. Eisenbud, D., Huneke, C., Vasconcelos, W.: Direct methods for primary decomposition. Invent. Math. 110, 207-235 (1992)
9. Francisco, C.A., Hà, H.T.: Whiskers and sequentially Cohen-Macaulay graphs. J. Comb. Theory Ser. A 115, 304-316 (2008)
10. Francisco, C.A., Hà, H.T., Van Tuyl, A.: Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals. Preprint (2009). arXiv
11. Francisco, C.A., Hoefel, A., Van Tuyl, A.: EdgeIdeals: a package for (hyper)graphs. J. Software Al- gebra Geom. 1, 1-4 (2009)
12. Francisco, C.A., Van Tuyl, A.: Sequentially Cohen-Macaulay edge ideals. Proc. Am. Math. Soc. 135, 2327-2337 (2007)
13. Grayson, D.R., Stillman, M.E.: Macaulay 2, a software system for research in algebraic geometry.
14. Hà, H.T., Morey, S.: Embedded associated primes of powers of square-free monomial ideals. J. Pure Appl. Algebra 214(4), 301-308 (2010)
15. Hà, H.T., Morey, S., Villarreal, R.H.: Cohen-Macaulay admissible clutters. J. Commut. Algebra 1, 463-480 (2009)
16. Hà, H.T., Van Tuyl, A.: Resolutions of square-free monomial ideals via facet ideals: a survey. Contemp. Math. 448, 91-117 (2007)
17. Hà, H.T., Van Tuyl, A.: Splittable ideals and the resolutions of monomial ideals. J. Algebra 309, 405-425 (2007)
18. Hà, H.T., Van Tuyl, A.: Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers. J. Algebr. Comb. 27, 215-245 (2008)
19. Herzog, J., Hibi, T., Trung, N.V.: Symbolic powers of monomial ideals and vertex cover algebras. Adv. Math. 210, 304-322 (2007)
20. Herzog, J., Hibi, T., Zheng, X.: Cohen-Macaulay chordal graphs. J. Comb. Theory Ser. A 113, 911- 916 (2006)
21. Hosten, S., Smith, G.: Monomial ideals. In: Computations in Algebraic Geometry with Macaulay
2. Algorithms and Computations in Mathematics, vol. 8, pp. 73-100. Springer, Berlin (2001)
22. Jacques, S., Katzman, M.: The Betti numbers of forests. Preprint (2005).
23. Miller, E., Sturmfels, B.: Combinatorial Commutative Algebra. GTM, vol.
227. Springer, Berlin (2004)
24. Roth, M., Van Tuyl, A.: On the linear strand of an edge ideal. Commun. Algebra 35, 821-832 (2007)
25. Simis, A., Ulrich, B.: On the ideal of an embedded join. J. Algebra 226, 1-14 (2000)
26. Simis, A., Vasconcelos, W.V., Villarreal, R.H.: On the ideal theory of graphs. J. Algebra 167, 389-416 (1994)
27. Sturmfels, B., Sullivant, S.: Combinatorial secant varieties. Pure Appl. Math. Q. 2, 867-891 (2006)
28. Sturmfels, B., Trung, N.V., Vogel, W.: Bounds on degrees of projective schemes. Math. Ann. 302, 417-432 (1995)
29. Van Tuyl, A., Villarreal, R.: Shellable graphs and sequentially Cohen-Macaulay bipartite graphs.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition