Cover Product and Betti Polynomial of Graphs

Llamas, Aurora ; Martínez–Bernal, Josá

Canadian mathematical bulletin, Tome 58 (2015) no. 2, pp. 320-333

Résumé

The cover product of disjoint graphs $G$ and $H$ with fixed vertex covers $C\left( G \right)$ and $C\left( H \right)$ , is the graph $G\circledast H$ with vertex set $V\left( G \right)\cup V\left( H \right)$ and edge set $$E\left( G \right)\,\cup \,E\left( H \right)\,\cup \,\left\{ \left\{ i,\,j \right\}\,:\,i\,\in \,C\left( G \right),\,j\,\in \,C\left( H \right) \right\}.$$ We describe the graded Betti numbers of $G\circledast H$ in terms of those of $G$ and $H$ . As applications we obtain: (i) For any positive integer k there exists a connected bipartite graph $G$ such that $\text{reg}\,R/I\left( G \right)\,=\,{{\mu }_{s}}\left( G \right)\,+\,k$ , where, $I\left( G \right)$ denotes the edge ideal of $G$ , $\text{reg}\,\text{R/I}\left( G \right)$ is the Castelnuovo–Mumford regularity of $\text{R/I}\left( G \right)$ and ${{\mu }_{s}}\left( G \right)$ is the induced or strong matching number of $G$ ; (ii)The graded Betti numbers of the complement of a tree depends only upon its number of vertices; (iii)The $h$ -vector of $R/I\left( G\circledast H \right)$ is described in terms of the $h$ -vectors of $\text{R/I}\left( G \right)$ and $R/I\left( H \right)$ . Furthermore, in a different direction, we give a recursive formula for the graded Betti numbers of chordal bipartite graphs.

Détail

DOI : 10.4153/CMB-2015-013-3

Mots-clés : 13D02, 05E45, Castelnuovo–Mumford regularity, chordal bipartite graph, edge ideal, graded Betti number, induced matching number, monomial ideal

Bibliographie

[1] [1] Abbott, J., Bigatti, A. M., and G. Lagoio, CoCoA-5: A system for doing computations in commutative algebra, http://cocoa.dima.unige.it Google Scholar

[2] [2] Bondy, A. and Murty, U.S.R., Graph theory. Graduate Texts in Mathematics, 244, Springer, New York, 2008. Google Scholar

[3] [3] Bruns, W. and Herzog, J., Cohen-Macaulay rings. Cambridge Studies in Advanced Mathematics, 39, Cambridge University Press, Cambridge, 1993. Google Scholar

[4] [4] Corso, A. and Nagel, U., Monomial and toric ideals associated to Ferrers graphs. Trans. Amer. Math. Soc. 361 (2009), no. 3, 1371–1395. Google Scholar | DOI

[5] [5] de Alwis, T., Free minimal resolutions. Comm. Algebra 21 (1993), no. 12, 4575–4585. Google Scholar | DOI

[6] [6] de Alwis, T., Free minimal resolutions and the Betti numbers of the suspension of an n-agon. Int. J. Math. Math. Sci. 23 (2000), no. 3, 211–216. http://dx.doi.Org/10.1155/SO161171200001563 Google Scholar

[7] [7] Dirac, G. A., On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76. Google Scholar | DOI

[8] [8] Dochtermann, A. and Engstrôm, A., Algebraic properties of edge ideals via combinatorial topology. Electron. J. Combin. 16 (2009), no. 2, Research Paper 2. Google Scholar

[9] [9] Ferrarello, D. and Frôberg, R., The Hilbert series of the clique complex. Graphs Combin. 21 (2005), no. 4, 401–405. http://dx.doi.Org/10.1007/s00373-005-0634-z Google Scholar

[10] [10] Francisco, C. A. and A. Van Tuyl, Sequentially Cohen-Macaulay edge ideals. Proc. Amer. Math. Soc. 135 (2007), no. 8, 2327–2337. Google Scholar | DOI

[11] [11] Golumbic, M. Ch. and Lewenstein, M., New results on induced matchings. Discrete Appl. Math. 101 (2000), no. 1, 157–165. Google Scholar | DOI

[12] [12] Fulkerson, D. R. and Gross, O. A., Incidence matrices and interval graphs. Pacific J. Math. 15 (1965), 835–855. Google Scholar | DOI

[13] [13] Hà, H. T and Van Tuyl, A., Splittable ideals and the resolution of monomial ideals. J. Algebra 309 (2007), no. 1, 405–425. http://dx.doi.Org/10.1016/j.jalgebra.2OO6.O8.O22 Google Scholar

[14] [14] Hà, H. T and Van Tuyl, A., Resolutions of square-free monomial ideals via facet ideals: a survey. In: Algebra, geometry and their interactions, Contemp. Math., 448, American Mathematical Society, Providence, RI, 2007, pp. 91–117. Google Scholar

[15] [15] Hayward, R., Hoàng, C., and Maffray, F., Optimizing weakly triangulated graphs. Graphs Combin. 5 (1989), no. 4, 339–349. http://dx.doi.Org/10.1007/BF01788689 Google Scholar

[16] [16] Hochster, M., Cohen-Macaulay rings, combinatorics, and simplicial complexes. In: Ring theory, II, (Proc. Second Cond., Univ. Oklahoma, Norman, Okla., 1975), Lecture Notes in Pure and Appl. Math., 26, Dekker, New York, 1977, pp. 171–223. Google Scholar

[17] [17] Jacques, S., Betti numbers of graph ideals. Ph.D. Thesis, University of Sheffield, 2004. arxiv:math/0410107 Google Scholar

[18] [18] Jacques, S. and Katzman, M., The Betti numbers of forests. arxiv:math/0501226v2 Google Scholar

[19] [19] Katzman, M., Characteristic-Independence of Betti numbers of graph ideals. J. Combin. Theory Ser. A 113 (2006), no. 3, 435–454. http://dx.doi.Org/10.1016/j.jcta.2OO5.04.005 Google Scholar

[20] [20] Kummini, M., Regularity, depth and arithmetical rank of bipartite edge ideals. J. Algebraic Combin. 30 (2009), no. 4, 429–445. Google Scholar | DOI

[21] [21] Martinez-Bernal, J., Renteria, C., and Villarreal, R.H., Combinatorics of symbolic Rees algebras of edge ideals of clutters. Contemp. Math. 555 (2011), 151–164. Google Scholar

[22] [22] Miller, E. and Sturmfels, B., Combinatorial commutative algebra. Graduate Texts in Mathematics, 227, Springer-Verlag, New York, 2005. Google Scholar

[23] [23] Morey, S. and Villarreal, R. H., Edge ideals: Algebraic and combinatorial properties. In: Progress in commutative algebra 1, de Gruyter, Berlin, 85–126. Google Scholar

[24] [24] Mousivand, A., Algebraic properties of product of graphs. Comm. Algebra 40 (2012), no. 11, 4177–4194. Google Scholar | DOI

[25] [25] Peeva, I. and Stillman, M., Open problems on syzygies and Hilbert functions. J. Commut. Algebra 1 (2009), no. 1, 159–195. Google Scholar | DOI

[26] [26] Renteln, P., The Hilbert series of the face ring of a flag complex. Graphs Combin. 18 (2002), no. 3, 605–619. Google Scholar | DOI

[27] [27] Schrijver, A., Combinatorial optimization. Algorithms and Combinatorics, 24, Springer-Verlag, Berlin, 2003. Google Scholar

[28] [28] Spinrad, J. P. and Sritharan, R., Algorithms for weakly triangulated graphs. Discrete Appl. Math. 59 (1995), no. 2, 181–191. http://dx.doi.Org/10.1016/0166–218X(93)E0161-Q Google Scholar

[29] [29] Terai, N., Alexander duality theorem and Stanley-Reisner rings. Free resolutions of coordinate rings of projective varieties and related topics (Japanese) (Kyoto, 1998). Surikaisekikenkyusho Kokyuroku 1078 (1999), 174–184. Google Scholar

[30] [30] Van Tuyl, A., Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity. Arch. Math. 93 (2009), 451–459. http://dx.doi.Org/10.1007/s00013-009-0049-9 Google Scholar

[31] [31] Villarreal, R. H., Cohen-Macaulay graphs. Manuscripta Math. 66 (1990), 277–293. Google Scholar | DOI

[32] [32] Whieldon, G., Jump sequences of edge ideals, arXiv : 1012.0108vl, 2010. Google Scholar

[33] [33] Woodroofe, R., Vertex decomposable graphs and obstructions to shellability. Proc. Amer. Math. Soc. 137 (2009), no. 10, 3235–3246. Google Scholar | DOI

[34] [34] Woodroofe, R., Matchings, coverings, and Castelnuovo-Mumford regularity. J. Commut. Algebra 6 (2014), no. 2, 287–304. Google Scholar | DOI