A proof for a conjecture on the regularity of binomial edge ideals (Q2229199)

Let \(\mathbb K\) be a field and let \(G\) be a finite simple graph on the vertex set \(\{1,\dots,n\}\) and the edge set \(E(G)\). The associated binomial edge ideal is the ideal \(J_G=(x_i y_j-x_j y_i \mid \{i,j\} \in E(G))\) of the polynomial ring \(R=\mathbb K [x_1, \dots, x_n, y_1, \dots, y_n]\). In [\textit{S. Saeedi Madani} and \textit{D. Kiani}, Electron. J. Comb. 20, No. 1, Research Paper P48, 13 p. (2013; Zbl 1278.13007); J. Comb. Theory, Ser. A 139, 80--86 (2016; Zbl 1328.05087)] the second and the third author of the present paper conjectured that the Castelnuovo-Mumford regularity of \(R/J_G\) is bounded above by the number of maximal cliques, \(c(G)\), of \(G\). In this paper this conjecture is settled in full generality; in fact, a better bound is proved. A set \(\mathcal{H} \subseteq E(G)\) is said to be a clique disjoint edge set in \(G\) if there are no two elements of \(\mathcal{H}\) belonging to the same clique of \(G\). The maximum cardinality of a clique disjoint edge set in \(G\) is denoted by \(\eta(G)\). In this paper it is proved that the Castelnuovo-Mumford regularity of \(R/J_G\) is bounded above by \(\eta(G)\) and this settles the conjecture above because \(\eta(G) \leq c(G)\). Moreover, the authors show a family of graphs \(G_n\) for which \(\lim_{n \rightarrow \infty} (c(G_n)-\eta(G_n)) = \infty\).