×

zbMATH — the first resource for mathematics

Krull dimension and regularity of binomial edge ideals of block graphs. (English) Zbl 1444.13029
Let \(K\) be a field, \(S=K[x_i,y_j]_{1\leq i,j\leq n}\) and \(G\) be a simple undirected graph with vertex set \([n]\). The ideal \(J_G\) of \(S\) generated by all \(x_iy_j-x_jy_i\) such that \(i< j\) and \(\{i,j\}\) is an edge of \(G\) is called the binomial edge ideal of \(G\). Also a block graph means a graph, in which, all blocks are cliques. In this paper, the authors present linear time algorithms for computing the Krull dimension and the Castelnuovo-Mumford regularity of \(S/J_G\), when \(G\) is a block graph. They also give a lower bound on the regularity of binomial edge ideals of block graphs.
For finding the Krull dimension of \(S/J_G\), they use a result of the paper [J. Herzog et al., Adv. Appl. Math. 45, No. 3, 317–333 (2010; Zbl 1196.13018)] which characterizes minimal prime ideals of \(J_G\). Here the authors present an algorithm to find a minimal prime ideal of \(J_G\) with the minimum possible height with just one traverse of \(G\).
To study the regularity of \(S/J_G\), the authors introduce flower graphs. They call a graph a flower graph, when it is obtained by unifying a vertex \(v\) of some disjoint copies of a triangle and some disjoint copies of \(K_{1,3}\), where \(v\) must have degree 1 in each copy of \(K_{1,3}\) and the total number of copies of the triangle and \(K_{1,3}\) must be at least 3. They find extremal Betti numbers of \(S/J_G\) and state a formula for the regularity of \(S/J_G\) when \(G\) is a flower graph. Also if \(G\) is a block graph which is flower-free, that is, \(G\) has no induced subgraph which is a flower graph, a formula for the regularity of \(S/J_G\) is presented. Moreover, they use the results on flower graphs to state a lower bound on the regularity of \(S/J_G\) for general block graphs. Finally, they present and prove the correctness of an algorithm which computes the regularity of \(S/J_G\), by successively deleting certain flower graphs from \(G\) and summing up the regularities of the remained connected components which are flower-free graphs.

MSC:
13F65 Commutative rings defined by binomial ideals, toric rings, etc.
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
13P99 Computational aspects and applications of commutative rings
13D02 Syzygies, resolutions, complexes and commutative rings
Software:
CoCoA; Macaulay2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] CoCoATeam, CoCoA: A system for doing Computations in Commutative Algebra, available at http://cocoa.dima.unige.it.
[2] Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C., Introduction to Algorithms, 2nd edn. (MIT Press and McGraw-Hill, 2001). · Zbl 1047.68161
[3] Ene, V., Herzog, J. and Hibi, T., Cohen-Macaulay binomial edge ideals, Nagoya Math. J.45 (2011) 57-68. · Zbl 1236.13011
[4] Ene, V., Zarojanu, A., On the regularity of binomial edge ideals, Math. Nachr.45 (2015) 19-24. · Zbl 1310.13021
[5] D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
[6] Herzog, J. and Hibi, T., Monomial Ideals, , Vol. 260 (Springer, London, 2010). · Zbl 1206.13001
[7] Herzog, J., Hibi, T., Hreinsdottir, F., Kahle, T. and Rauh, J., Binomial edge ideals and conditional independence statements, Adv. Appl. Math.45 (2010) 317-333. · Zbl 1196.13018
[8] Herzog, J. and Rinaldo, G., On the extremal Betti numbers of binomial edge ideals of block graphs, Electron. J. Combin.25(1) (2018) 1-10. · Zbl 1395.13010
[9] Jayanthan, A. V., Narayanan, N. and Rao, B. V. Raghavendra, Regularity of binomial edge ideals of certain block graphs, in Proc. Indian Acad. Sci. Math. Sci.129 (2019) 36. · Zbl 1415.13010
[10] Jayanthan, A. V., Narayanan, N. and Rao, B. V. Raghavendra, An upper bound for the regularity of binomial edge ideals of trees, J. Algebra Appl. (2018), in press. · Zbl 07098694
[11] Kiani, D. and Madani, S. Saeedi, The Castelnuovo-Mumford regularity of binomial edge ideals, Combin. Theory Ser. A139 (2016) 80-86. · Zbl 1328.05087
[12] C. Mascia and G. Rinaldo, A linear time algorithm to compute the Krull dimension of binomial edge ideal of trees (2018) http://www.giancarlorinaldo.it/krulldimtrees.
[13] Matsuda, K., Murai, S., Regularity bounds for binomial edge ideals, Commun. Algebra5 (2013) 141-149. · Zbl 1272.13018
[14] Ohtani, M., Graphs and ideals generated by some \(2\)-minors, Commun. Algebra39 (2011) 905-917. · Zbl 1225.13028
[15] Rauf, A. and Rinaldo, G., Construction of Cohen-Macaulay binomial edge ideals, Commun. Algebra42.1 (2014) 238-252. · Zbl 1293.13007
[16] Rinaldo, G., Cohen-Macaulay binomial edge ideals of small deviation, Bull. Math. Soc. Sci. Math. Roumanie56(104)(4) (2013) 497-503. · Zbl 1299.13026
[17] Rinaldo, G., Cohen-Macaulay binomial edge ideals of cactus graphs, J. Algebra Appl.18(4) (2019) 1-18. · Zbl 1419.13042
[18] Madani, S. Saeedi and Kiani, D., Binomial edge ideals of graphs, Electron. J. Combin.19 (2012) Paper #P44. · Zbl 1403.13028
[19] Madani, S. Saeedi and Kiani, D., On the binomial edge ideal of a pair of graphs, Electron. J. Combin.20(1) (2013) Paper # P48. · Zbl 1278.13007
[20] Madani, S. Saeedi and Kiani, D., Binomial edge ideals of regularity 3, J. Algebra515 (2018) 157-172. · Zbl 1403.13028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.