1 Introduction

The binomial edge ideal of a finite simple graph was introduced in [2] and in [10] independently. (Recall that a finite graph G is simple if G possesses no loop and no multiple edge.) Let G be a finite simple graph on the vertex set [n] = {1,2,…, n} and K[x, y] = K[x1,…, xn, y1,…, yn] the polynomial ring in 2n variables over a field K with each \(\deg x_{i} = \deg y_{j} = 1\). The binomial edge ideal JG of G is the binomial ideal of K[x, y] which is generated by those binomials xiyj − xjyi for which {i, j} is an edge of G.

Let, in general, S = K[x1,…, xn] denote the polynomial ring in n variables over a field K with each \(\deg x_{i} = 1\) and I ⊂ S a homogeneous ideal of S with \(\dim S/I = d\). The Hilbert series HS/I(λ) of S/I is of the form HS/I(λ) = (h0 + h1λ + h2λ2 + ⋯ + hsλs)/(1 − λ)d, where each \(h_{i} \in \mathbb Z\) [1, Proposition 4.4.1]. We say that hS/I(λ) = h0 + h1λ + h2λ2 + ⋯ + hsλs with hs≠ 0 is the h-polynomial of S/I. Let reg(S/I) denote the (Castelnuovo–Mumford ) regularity [1, p. 168] of S/I. It is known (e.g., [14, Corollary B.4.1]) that, when S/I is Cohen–Macaulay, one has \(\operatorname {reg}(S/I) = \deg h_{S/I}(\lambda )\). Furthermore, in [3] and [4], for given integers r and s with r, s ≥ 1, a monomial ideal I of S = K[x1,…, xn] with n ≫ 0 for which reg(S/I) = r and \(\deg h_{S/I} (\lambda ) = s\) was constructed.

Let, as before, G be a finite simple graph on the vertex set [n] with \(d = \dim K[\mathbf {x}, \mathbf {y}]/J_{G}\) and \(h_{K[\mathbf {x}, \mathbf {y}]/J_{G}}(\lambda ) = h_{0} + h_{1}\lambda + h_{2}\lambda ^{2} + {\cdots } + h_{s}\lambda ^{s}\) the h-polynomial of K[x, y]/JG.

Now, in the present paper, given arbitrary integers r and s with 2 ≤ r ≤ s, a finite simple graph G on [n] with n ≫ 0 for which reg(K[x, y]/JG) = r and \(\deg h_{K[\bold x, \mathbf {y}]/J_{G}}(\lambda ) = s\) will be constructed.

Theorem 1.1

Given arbitrary integers r and s with 2 ≤ r ≤ s, there exists a finite simple graph G on [n] with n ≫ 0 for which reg(K[x, y]/JG) = r and \(\deg h_{K[\bold x, \mathbf {y}]/J_{G}}(\lambda ) = s\).

2 Proof of Theorem 1.1

Our discussion starts in the computation of the regularity and the h-polynomial of the binomial edge ideal of a path graph.

Example 2.1

Let Pn be the path on the vertex set [n] with {1,2},{2,3},…,{n − 1, n} its edges. Since \(K[\mathbf {x}, \mathbf {y}]/J_{P_{n}}\) is a complete intersection, it follows that the Hilbert series of \(K[\mathbf {x}, \mathbf {y}]/J_{P_{n}}\) is \(H_{K[\mathbf {x}, \mathbf {y}]/J_{P_{n}}} (\lambda ) = (1 + \lambda )^{n - 1}/(1 - \lambda )^{n + 1}\) and that \(\operatorname {reg}(K[\mathbf {x}, \mathbf {y}]/J_{P_{n}})\) \( = \deg h_{K[\mathbf {x}, \mathbf {y}]/J_{P_{n}}}(\lambda ) = n - 1\).

Let G be a finite simple graph on the vertex set [n] and E(G) its edge set. The suspension of G is the finite simple graph \(\widehat {G}\) on the vertex set [n + 1] whose edge set is \(E(\widehat {G}) = E(G) \cup \{ \{i, n + 1\} : i \in [n] \}\). Given a positive integer m ≥ 2, the m-th suspension of G is the finite simple graph \({\widehat {G}}^{ m}\) on [n + m] which is defined inductively by \({\widehat {G}}^{ m} = \widehat {{\widehat {G}}^{ m-1}}\), where \({\widehat {G}}^{ 1} = \widehat {G}\).

Lemma 2.2

Let G be a finite connected simple graph on [n] which is not complete. Suppose that \(\dim K[\mathbf {x}, \mathbf {y}]/J_{G} = n + 1\) and \(\deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}} (\lambda ) \geq 2\). Then

$$ \begin{array}{@{}rcl@{}} \operatorname{reg} \left( K[\mathbf{x}, \mathbf{y}, x_{n+1}, y_{n+1}]/J_{\widehat{G}} \right) = \operatorname{reg}(K[\mathbf{x}, \mathbf{y}]/J_{G}), \\ \deg h_{K[\mathbf{x}, \mathbf{y}, x_{n+1}, y_{n+1}]/J_{\widehat{G}}} (\lambda) = \deg h_{K[\mathbf{x}, \mathbf{y}]/J_{G}} (\lambda) + 1. \end{array} $$

In particular, if \( \operatorname {reg}(K[\mathbf {x}, \mathbf {y}]/J_{G}) \leq \deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}} (\lambda )\), then

$$ \operatorname{reg} \left( K[\mathbf{x}, \mathbf{y}, x_{n+1}, y_{n+1}]/J_{\widehat{G}} \right) < \deg h_{K[\mathbf{x}, \mathbf{y}]/J_{\widehat{G}}} (\lambda). $$

Proof

The suspension \(\widehat {G}\) is the join product [12, p. 3] of G and {n + 1}, and \(\widehat {G}\) is not complete. Hence, by virtue of [11, Theorem 2.1] and [12, Theorem 2.1 (a)], one has

$$ \operatorname{reg} \left( K[\mathbf{x}, \mathbf{y}, x_{n+1}, y_{n+1}]/J_{\widehat{G}} \right) = \max\{ \operatorname{reg}(K[\mathbf{x}, \mathbf{y}]/J_{G}), 2 \} = \operatorname{reg}(K[\mathbf{x}, \mathbf{y}]/J_{G}). $$

Furthermore, [8, Theorem 4.6] says that

$$ \begin{array}{@{}rcl@{}} H_{K[\mathbf{x}, \mathbf{y}, x_{n+1}, y_{n+1}]/J_{\widehat{G}}}(\lambda) &=& H_{K[\mathbf{x}, \mathbf{y}]/J_{G}} (\lambda) + \frac{2\lambda + (n - 1)\lambda^{2}}{(1 - \lambda)^{n + 2}} \\ &=& \frac{h_{K[\mathbf{x}, \mathbf{y}]/J_{G}} (\lambda)}{(1 - \lambda)^{n + 1}} + \frac{2\lambda + (n - 1)\lambda^{2}}{(1 - \lambda)^{n + 2}} \\ &=& \frac{h_{K[\mathbf{x}, \mathbf{y}]/J_{G}} (\lambda) \cdot (1 - \lambda) + 2\lambda + (n - 1)\lambda^{2}}{(1 - \lambda)^{n + 2}}. \end{array} $$

Thus, \(\deg h_{K[\mathbf {x}, \mathbf {y}, x_{n+1}, y_{n+1}]/J_{\widehat {G}}} (\lambda ) = \deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}} (\lambda ) + 1\), as desired. □

We are now in the position to give a proof of Theorem 1.1.

Proof of Theorem 1.1

Each of the following three cases is discussed.

Case 1

Let 2 ≤ r = s. Let G = Pr+ 1. As was shown in Example 2.1, one has

$$ \operatorname{reg}(K[\mathbf{x}, \mathbf{y}]/J_{G}) = \deg h_{K[\mathbf{x}, \mathbf{y}]/J_{G}}(\lambda) = r. $$

Case 2

Let r = 2 and 3 ≤ s. Let G = Ks− 1, s− 1 denote the complete bipartite graph on the vertex set [2s − 2]. By using [13, Theorem 1.1 (c) together with Theorem 5.4 (a)], one has reg(K[x, y]/JG) = 2 and

$$ \begin{array}{@{}rcl@{}} H_{K[\mathbf{x}, \mathbf{y}]/J_{G}}(\lambda) &=& \frac{1 + (2s - 3)\lambda}{(1 - \lambda)^{2s - 1}} + \frac{2}{(1 - \lambda)^{2s - 2}} - \frac{2\{1 + (s - 2)\lambda \}}{(1 - \lambda)^{s}} \\ &=& \frac{1 + (2s - 3)\lambda + 2(1 - \lambda) - 2\{1 + (s - 2)\lambda \}(1 - \lambda)^{s - 1}}{(1 - \lambda)^{2s - 1}}. \end{array} $$

Hence, \(\deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}} (\lambda ) = s\), as required.

Case 3

Let 3 ≤ r < s. Let \(G = \widehat {P_{r + 1}}^{s - r}\) be the (s − r)-th suspension of the path Pr+ 1. Applying Lemma 2.2 repeatedly shows reg(S/JG) = r and

$$ \begin{array}{@{}rcl@{}} & & H_{K[\mathbf{x}, \mathbf{y}]/J_{G}}(\lambda) \\ & & \\ &=& \frac{(1 + \lambda)^{r} (1 - \lambda)^{s - r} + 2\lambda \left\{ {\sum}_{i = 0}^{s - r - 1} (1 - \lambda)^{i} \right\} + \lambda^{2} {\sum}_{i = 0}^{s - r - 1} (s - 1 - i)(1 - \lambda)^{i}}{(1 - \lambda)^{s + 2}} \\ & & \\ &=& \frac{(1 + \lambda)^{r} (1 - \lambda)^{s - r} + 2\lambda \cdot \frac{1 - (1 - \lambda)^{s - r}}{\lambda} + \lambda^{2} \cdot \frac{-1 + (1 - \lambda)^{s - r} + \lambda \{ s - r(1 - \lambda)^{s - r} \}}{\lambda^{2}}}{(1 - \lambda)^{s + 2}} \\ & & \\ &=& \frac{(1 + \lambda)^{r} (1 - \lambda)^{s - r} + 2\left\{1 - (1 - \lambda)^{s - r} \right\} -1 + (1 - \lambda)^{s - r} + \lambda \{s - r(1 - \lambda)^{s - r}\} }{(1 - \lambda)^{s + 2}} \\ & & \\ &=& \frac{(1 + \lambda)^{r} (1 - \lambda)^{s - r} + 1 - (1 - \lambda)^{s - r} + \lambda \{s - r(1 - \lambda)^{s - r}\}}{(1 - \lambda)^{s + 2}} \\ & & \\ &=& \frac{1 + s\lambda + (1 - \lambda)^{s - r} \{(1 + \lambda)^{r} - 1 - r\lambda \}}{(1 - \lambda)^{s + 2}}. \end{array} $$

Hence, \(\deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}} (\lambda ) = s\), as desired.

□

3 Examples

Proposition 3.1

The cycle Cn of length n ≥ 3 satisfies

$$ \operatorname{reg} (K[\mathbf{x}, \mathbf{y}]/J_{C_{n}}) \leq \deg h_{K[\mathbf{x}, \mathbf{y}]/J_{C_{n}}} (\lambda). $$

Proof

Since the length of the longest induced path of Cn is n − 2, it follows from [9, Theorem 1.1] and [7, Theorem 3.2] that \(\operatorname {reg} (K[\mathbf {x}, \mathbf {y}]/J_{C_{n}}) = n - 2\). Furthermore, [15, Theorem 10 (b)] says that

$$ \deg h_{K[\mathbf{x}, \mathbf{y}]/J_{C_{n}}} = \begin{cases} 1 & (n = 3), \\ n - 1 & (n > 3). \end{cases} $$

Hence, the desired inequality follows. □

Let k ≥ 1 be an integer and p1, p2,…, pk a sequence of positive integers with p1 ≥ p2 ≥⋯ ≥ pk ≥ 1 and p1 + p2 + ⋯ + pk = n. Let V1, V2,…, Vk denote a partition of [n] with each |Vi| = pi. In other words, [n] = V1 ⊔ V2 ⊔⋯ ⊔ Vk and Vi ∩ Vj = ∅ if i≠j. Suppose that

$$ V_{i} = \left\{\sum\limits_{j = 1}^{i - 1} p_{j} + 1, \ \sum\limits_{j = 1}^{i - 1} p_{j} + 2, \ \ldots, \sum\limits_{j = 1}^{i - 1} p_{j} + p_{i} - 1, \sum\limits_{j = 1}^{i} p_{j} \right\} $$

for each 1 ≤ i ≤ k. The complete multipartite graph \(K_{p_{1}, \ldots , p_{k}}\) is the finite simple graph on the vertex set [n] with the edge set

$$ E\left( K_{p_{1}, \ldots, p_{k}}\right) = \{ \{k, \ell\} : k \in V_{i}, \ell \in V_{j}, 1 \leq i < j \leq k \}. $$

Proposition 3.2

The complete multipartite graph \(G = K_{p_{1}, \ldots , p_{k}}\) satisfies

$$ \operatorname{reg} (K[\mathbf{x}, \mathbf{y}]/J_{G}) \leq \deg h_{K[\mathbf{x}, \mathbf{y}]/J_{G}} (\lambda). $$

Proof

We claim \(\operatorname {reg} (K[\mathbf {x}, \mathbf {y}]/J_{G}) \leq \deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}} (\lambda )\) by induction on k. If k = 1, then \(G = K_{p_{1}}\) is the complete graph and \(\operatorname {reg} (K[\mathbf {x}, \mathbf {y}]/J_{G}) = \deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}} (\lambda ) = 1\).

Let k > 1. If pk = 1, then \(G = \widehat {G^{\prime }}\), where \(G^{\prime } = K_{p_{1}, \ldots , p_{k - 1}}\). Lemma 2.2 as well as the induction hypothesis then guarantees that \(\operatorname {reg} (K[\mathbf {x}, \mathbf {y}]/J_{G}) \leq \deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}} (\lambda )\). Hence, one can assume that pk > 1. In particular, G is not complete. It then follows from [12, Theorem 2.1 (a)] that reg(K[x, y]/JG) = 2. Furthermore, [8, Corollary 4.14] says that

$$ \deg h_{K[\mathbf{x}, \mathbf{y}]/J_{G}} (\lambda) = \begin{cases} n - p_{k} + 1 & (2p_{1} < n + 1), \\ 2p_{1} - p_{k} & (2p_{1} \geq n + 1). \end{cases} $$

Since k > 1 and pk > 1, one has \(\deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}} (\lambda ) \geq n - p_{k} + 1 \geq p_{1} + 1 \geq 3\). Thus, the desired inequality follows. □

Let t ≥ 3 be an integer and K1, t the complete bipartite graph on {1, v1,…, vt} with the edge set E(K1, t) = {{1, vi} : 1 ≤ i ≤ t}. Let p1, p2,…, pt be a sequence of positive integers and P(i) the path of length pi on the vertex set \(\{w_{i, 1}, w_{i, 2}, \ldots , w_{i, p_{i} + 1} \}\) for each 1 ≤ i ≤ t. Then the t-starlike graph \(T_{p_{1}, p_{2}, \ldots , p_{t}}\) is defined as the finite simple graph obtained by identifying vi with wi,1 for each 1 ≤ i ≤ t. Thus, the vertex set of \(T_{p_{1}, p_{2}, \ldots , p_{t}}\) is

$$ \{1\} \cup \bigcup_{i = 1}^{t} \{w_{i, 1}, w_{i, 2}, \ldots, w_{i, p_{i} + 1} \} $$

and its edge set is

$$ E(T_{p_{1}, p_{2}, \ldots, p_{t}}) = \bigcup_{i = 1}^{t} \left\{ \{ w_{i, j}, w_{i, j + 1} \} \mid 0 \leq j \leq p_{i} \right\}, $$

where wi,0 = 1 for each 1 ≤ i ≤ t.

Proposition 3.3

The t-starlike graph \(G = T_{p_{1}, p_{2}, \ldots , p_{t}}\) satisfies

$$ \operatorname{reg} (K[\mathbf{x}, \mathbf{y}]/J_{G}) < \deg h_{K[\mathbf{x}, \mathbf{y}]/J_{G}} (\lambda). $$

Proof

It follows from [5, Corollary 3.4 (2)] that \(\operatorname {reg}(K[\mathbf {x}, \mathbf {y}]/J_{G}) = 2 + {\sum }_{i = 1}^{t} p_{i}\). Furthermore, [13, Theorem 5.4 (a)] guarantees that

$$ \begin{array}{@{}rcl@{}} H_{K[\mathbf{x}, \mathbf{y}]/J_{K_{1, t}}}(\lambda) &=& \frac{1}{(1 - \lambda)^{2t}} - \frac{1 + (t - 1)\lambda}{(1 - \lambda)^{t + 1}} + \frac{1 + t\lambda}{(1 - \lambda)^{t + 2}} \\ & & \\ &=& \frac{1 - \{ 1 + (t - 1) \lambda \}(1 - \lambda)^{t - 1} + (1 + t\lambda)(1 - \lambda)^{t - 2}}{(1 - \lambda)^{2t}} \\ & & \\ &=& \frac{1 + (1 - \lambda)^{t - 2} \left\{ 2\lambda + (t - 1)\lambda^{2} \right\}}{(1 - \lambda)^{2t}}. \end{array} $$

Hence, by virtue of [8, Corollary 3.3], one has

$$ h_{K[\mathbf{x}, \mathbf{y}]/J_{G}} (\lambda) = \left[1 + (1 - \lambda)^{t - 2} \left\{ 2\lambda + (t - 1)\lambda^{2} \right\} \right] \cdot (1 - \lambda)^{{\sum}_{i = 1}^{t} p_{i}}. $$

Thus

$$ \deg h_{K[\mathbf{x}, \mathbf{y}]/J_{G}} (\lambda) = t + \sum\limits_{i = 1}^{t} p_{i} > 2 + \sum\limits_{i = 1}^{t} p_{i} = \operatorname{reg}(K[\mathbf{x}, \mathbf{y}]/J_{G}), $$

as required. □

Example 3.4

Let m ≥ 0 be an integer and Gm the finite simple graph on the vertex set [m + 9] drawn below

Then \(K[\mathbf {x}, \mathbf {y}]/J_{G_{m}}\) is not unmixed. In fact, for each subset S ⊂ [m + 9], we define

$$ P_{S} = \left( \bigcup_{i \in S} \{ x_{i}, y_{i} \}, J_{\tilde{G}_{1}}, \ldots, J_{\tilde{G}_{c(S)}} \right), $$

where G1,…, Gc(S) are connected components of G[m+ 9]∖S and where \(\tilde {G}_{1}, \ldots , \tilde {G}_{c(S)}\) is the complete graph on the vertex set \(V(G_{1}), \ldots , V\left (G_{c(S)}\right )\), respectively. It then follows from [2, Lemma 3.1 and Corollary 3.9] that P∅ and P{3,8} are minimal primes of \(J_{G_{m}}\) and that heightP∅ = m + 8 < heightP{3,8} = m + 9. Thus, \(K[\mathbf {x}, \mathbf {y}]/J_{G_{m}}\) is not unmixed. In particular, \(K[\mathbf {x}, \mathbf {y}]/J_{G_{m}}\) is not Cohen-Macaulay. However, one has \(\operatorname {reg} (K[\mathbf {x}, \mathbf {y}]/J_{G_{m}}) = \deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G_{m}}} (\lambda )\) = m + 6.

A lot of computational experience encourages the authors to propose the conjecture that, for an arbitrary finite simple graph G, one has \(\operatorname {reg}(K[\mathbf {x}, \mathbf {y}]/J_{G}) \leq \deg h_{K[\mathbf {x}, \mathbf {y}]/J_{G}}(\lambda )\). However, the conjecture turns out to be false. A counterexample is constructed in [6].