# 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
CoCoA; Macaulay2
Full Text:
##### References:
  CoCoATeam, CoCoA: A system for doing Computations in Commutative Algebra, available at http://cocoa.dima.unige.it.  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  Ene, V., Herzog, J. and Hibi, T., Cohen-Macaulay binomial edge ideals, Nagoya Math. J.45 (2011) 57-68. · Zbl 1236.13011  Ene, V., Zarojanu, A., On the regularity of binomial edge ideals, Math. Nachr.45 (2015) 19-24. · Zbl 1310.13021  D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.  Herzog, J. and Hibi, T., Monomial Ideals, , Vol. 260 (Springer, London, 2010). · Zbl 1206.13001  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  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  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  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  Kiani, D. and Madani, S. Saeedi, The Castelnuovo-Mumford regularity of binomial edge ideals, Combin. Theory Ser. A139 (2016) 80-86. · Zbl 1328.05087  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.  Matsuda, K., Murai, S., Regularity bounds for binomial edge ideals, Commun. Algebra5 (2013) 141-149. · Zbl 1272.13018  Ohtani, M., Graphs and ideals generated by some $$2$$-minors, Commun. Algebra39 (2011) 905-917. · Zbl 1225.13028  Rauf, A. and Rinaldo, G., Construction of Cohen-Macaulay binomial edge ideals, Commun. Algebra42.1 (2014) 238-252. · Zbl 1293.13007  Rinaldo, G., Cohen-Macaulay binomial edge ideals of small deviation, Bull. Math. Soc. Sci. Math. Roumanie56(104)(4) (2013) 497-503. · Zbl 1299.13026  Rinaldo, G., Cohen-Macaulay binomial edge ideals of cactus graphs, J. Algebra Appl.18(4) (2019) 1-18. · Zbl 1419.13042  Madani, S. Saeedi and Kiani, D., Binomial edge ideals of graphs, Electron. J. Combin.19 (2012) Paper #P44. · Zbl 1403.13028  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  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.