Binomial edge ideals of cographs


  • Thomas Kahle Fakult¨at f¨ur Mathematik, OvGU Magdeburg, Magdeburg, Germany
  • Jonas Krüsemann Rail Management Consultants GmbH, Hannover, Germany



We determine the Castelnuovo-Mumford regularity of binomial edge ideals of complement-reducible graphs (cographs). For cographs with $n$ vertices the maximum regularity grows as $2n/3$. We also bound the regularity by graph-theoretic invariants and construct a family of counterexamples to a conjecture of Hibi and Matsuda.


Download data is not yet available.


A. Conca and M. Varbaro, Square-free Gröbner degenerations, Invent. Math. 221 (2020), no. 3, 713–730. MR 4132955.

D. G. Corneil, H. Lerchs and L. S. Burlingham, Complement reducible graphs, Discrete Appl. Math. 3 (1981), no. 3, 163–174. MR 0619603.

V. Ene and A. Zarojanu, On the regularity of binomial edge ideals, Math. Nachr. 288 (2015), no. 1, 19–24. MR 3310496.

D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry. Available at

J. Herzog, T. Hibi, F. Hreinsdóttir, T. Kahle and J. Rauh, Binomial edge ideals and conditional independence statements, Adv. in Appl. Math. 45 (2010), no. 3, 317–333. MR 2669070.

J. Herzog, D. Kiani and S. Saeedi Madani, The linear strand of determinantal facet ideals, Michigan Math. J. 66 (2017), no. 1, 107–123. MR 3619738.

T. Hibi and K. Matsuda, Regularity and $h$-polynomials of binomial edge ideals, Acta Math. Vietnam. 47 (2022), no. 1, 369–374. MR 4406578. Originally posted at [math.AC], 2018.

D. T. Hoang and T. Kahle, Hilbert–Poincaré series of parity binomial edge ideals and permanental ideals of complete graphs, Collect. Math. 72 (2021), no. 3, 471–479. MR 4297140.

A. V. Jayanthan, N. Narayanan and B. V. Raghavendra Rao, Regularity of binomial edge ideals of certain block graphs, Proc. Indian Acad. Sci. Math. Sci. 129 (2019), no. 3, Paper No. 36, 10 pp. MR 3941158.

T. Kahle, C. Sarmiento and T. Windisch, Parity binomial edge ideals, J. Algebraic Combin. 44 (2016), no. 1, 99–117. MR 3514772.

D. Kiani and S. Saeedi Madani, The Castelnuovo-Mumford regularity of binomial edge ideals, J. Combin. Theory Ser. A 139 (2016), 80–86. MR 3436053.

A. Kumar and R. Sarkar, Hilbert series of binomial edge ideals, Comm. Algebra 47 (2019), no. 9, 3830–3841. MR 3969484.

K. Matsuda and S. Murai, Regularity bounds for binomial edge ideals, J. Commut. Algebra 5 (2013), no. 1, 141–149. MR 3084125.

M. Ohtani, Graphs and ideals generated by some 2-minors, Comm. Algebra 39 (2011), no. 3, 905–917. MR 2782571.

M. Rouzbahani Malayeri, S. Saeedi Madani and D. Kiani, A proof for a conjecture on the regularity of binomial edge ideals, J. Combin. Theory Ser. A 180 (2021), Paper No. 105432, 9 pp. MR 4213658.

S. Saeedi Madani and D. Kiani, Binomial edge ideals of regularity 3, J. Algebra 515 (2018), 157–172. MR 3859963.