ON THE REGULARITY OF BINOMIAL EDGE IDEALS

arXiv:1307.2141v1 [] 8 Jul 2013

VIVIANA ENE, ANDREI ZAROJANU
A BSTRACT. We study the regularity of binomial edge ideals. For a closed graph G we
show that the regularity of the binomial edge ideal JG coincides with the regularity of
inlex (JG ) and can be expressed in terms of the combinatorial data of G. In addition, we
give positive answers to Matsuda-Murai conjecture [8] for some classes of graphs.

I NTRODUCTION
Binomial edge ideals were introduced in [7] and [9]. They are a generalization of the
classical determinantal ideal generated by the 2-minors of a 2 × n–matrix of indeterminates.
Let S = K[x1 , . . . , xn , y1 , . . ., yn ] be the polynomial ring in 2n variables over a field K.
For 1 ≤ i < j ≤ n we set fi j = xi y j − x j yi . Thus, fi j is the 2-minor determined by the
columns i and j in the 2 × n–matrix X with rows x1 , . . . , xn and y1 , . . ., yn . Let G be a
simple graph on [n] with edge set E(G). The binomial edge ideal JG associated with G is
the ideal of S generated by all the binomials fi j with {i, j} ∈ E(G). For example, if G is
the complete graph on the vertex set [n], then JG is equal to the ideal I2 (X ) of the maximal
minors of X .
In the last years, many properties of binomial edge ideals have been studied in relation
to the combinatorial data of the underlying graph and applications to statistics have been
investigated; see [1], [3], [4, Chapter 6], [5], [7], [11], [12], [14], [16].
The Gröbner basis of a binomial edge ideal with respect to the lexicographic order
induced by x1 > · · · > xn > y1 > · · · > yn was computed in [7]. It turned out that this
Gröbner basis is quadratic if and only if the graph G is closed with respect to the given
labeling which means that it satisfies the following condition: whenever {i, j} and {i, k}
are edges of G and either i < j, i < k or i > j, i > k, then { j, k} is also an edge of G.
One calls a graph G closed if it is closed with respect to some labeling of its vertices.
Any closed graph is chordal and claw-free; see [7]. In [3], the authors show that actually
JG has a quadratic Gröbner basis for some monomial order if and only if G is closed.
Combinatorial characterizations of closed graphs are given in [2] and [5].
The regularity of binomial edge ideals has been studied in [8] and [12]. In [8, Theorem
1.1] it was proved that if G is a connected graph, then ℓ ≤ reg(S/JG ) ≤ n − 1 where ℓ
denotes the length of the longest induced path in G. We show in Theorem 2.2 that if, in
The authors were supported by the grant UEFISCDI, PN-II-ID-PCE- 2011-3-1023.
1

addition, G is closed, then reg(S/JG ) = reg(S/ inlex (JG )) = ℓ. In particular, it follows that
the regularity of JG and inlex (JG ) do not depend on the characteristic of the base field.
In [8], the authors conjectured that if G is connected, then reg S/JG = n − 1 if and only
if G is a line graph. It straightforwardly follows from Theorem 2.2 that this conjecture is
true for closed graphs.
In [13] it is conjectured that reg(S/JG ) ≤ r where r is the number of maximal cliques of
G. It is obvious that this conjecture follows from [8, Theorem 1.1] in case that r ≥ n − 1.
Therefore, one should look at the case when r ≤ n − 1. This is the case, for instance, if G
is chordal.
We give a positive answer to Madani-Kiani conjecture [13] for a class of chordal graphs
which includes trees; see Theorem 2.9. In particular, we derive that Matsuda-Murai conjecture [8] holds for trees; see Corollary 2.10. Moreover, this implies, in particular that,
for chordal graphs, Matsuda-Murai conjecture follows from Madani-Kiani conjecture. Indeed, let us assume that the latter conjecture is true and that G is a chordal graph such that
reg(S/JG ) = n − 1. This implies that G has n − 1 cliques, that is, G is a tree with maximal
regularity. By Corollary 2.10 it follows that G must be a line graph.
1. P RELIMINARIES
In this section we review notation and fundamental results on binomial edge ideals that
will be used in the next sections.
1.1. Closed graph and its clique complex. Let G be a simple graph on the vertex set
[n] and S = K[x1 , . . . , xn , y1 , . . ., yn ] the polynomial ring in 2n indeterminates over a field
K endowed with the lexicographic order induced by x1 > · · · > xn > y1 > · · · > yn . Let
JG = ( fi j : {i, j} ∈ E(G)) ⊂ S be the associated binomial edge ideal of G. It is obvious
that, for computing the regularity of S/JG , we may assume without loss of generality
that G has no isolated vertex. According to [7], G is called closed with respect to its
given labeling if its generators form a Gröbner basis with respect to the lexicographic
order induced by the natural ordering of the indeterminates. G is closed if it possesses a
labeling of the vertices with respect to which is closed. In [7] it is shown that any closed
graph is chordal and claw–free. In [5, Theorem 2.2] it is shown that G is closed if and
only if there exists a labeling of G such that all the facets of the clique complex ∆(G) of
G are intervals [a, b] ⊂ [n]. This means, in particular, that if {i, j} ∈ E(G), then for any
i ≤ k < ℓ ≤ j, {k, ℓ} ∈ E(G). Indeed, if F is a facet of ∆(G) which contains {i, j}, then F
contains all the edges {k, ℓ} where i ≤ k < ℓ ≤ j.
Let G be a closed graph. Then inlex (JG ) = (xi y j : {i, j} ∈ E(G)) is the edge ideal of
a bipartite graph on the vertex set {x1 , . . ., xn } ∪ {y1 , . . ., yn }. Inspired by the notation in
[12], we let inlex (G) to be this bipartite graph. Therefore, we have inlex (JG ) = I(inlex (G)).
1.2. Minimal primes of a binomial edge ideal. Let S ⊂ [n] and G1 , . . ., Gc(S ) be the
connected components of the induced graph of G on the vertex set [n] \ S . For each Gi ,
2

let G̃i to be the complete graph on the vertex set of Gi . Then, by [7, Section 3],
PS (G) = ({xi , yi }i∈S , JG̃1 , . . . , JG̃c(S ) )
is a prime ideal for any subset S ⊂ [n], and
JG =

\

PS (G).

S ⊂[n]

Moreover, if G is connected, then the minimal primes of JG are those ideals PS (G) which
correspond to the sets with the cut-point property [7, Corollary 3.9]. We say that S has
the cut-point property or, simply, S is a cut-point set if S = 0/ or S 6= 0/ and c(S \{i}) <
c(S ) for every i ∈ S .
2. R EGULARITY
We recall that, for an arbitrary simple graph H, indmatch(H) is the number of edges
in a largest induced matching of H. By an induced matching we mean an induced subgraph of H which consists of pairwise disjoint edges. Note that indmatch(H) is actually
the monomial grade of the edge ideal I(H) which is the maximum length of a regular
sequence of monomials in I(H).
A graph H is called weakly chordal if every induced cycle in H and H (the complementary graph of H) has length at most 4.
We recall the following theorem in [15].
Theorem 2.1 ([15]). If H is a weakly chordal graph on the vertex set [n], then
reg(K[x1 , . . ., xn ]/I(H)) = indmatch(H).
Theorem 2.2. Let G be a closed graph on the vertex set [n] with the connected components
G1 , . . ., Gr . Then
reg(S/GG ) = reg(S/ in< (JG ))) = ℓ1 + · · · + ℓr ,
where, for 1 ≤ i ≤ r, ℓi is the length of the longest induced path of Gi .
For the proof of this theorem we first need the following results.
Lemma 2.3. Let G be a connected closed graph on [n]. Then the bipartite graph H =
inlex (G) on the vertex set {x1 , . . ., xn } ∪ {y1 , . . . , yn } is weakly chordal.
Proof. It is almost obvious that H has no induced cycle of length ≥ 5. Indeed, this is due
to the fact that H consists of two complete graphs, say Knx on the vertex set {x1 , . . ., xn }
and Kny on the vertex set {y1 , . . . , yn }, together with the edges {xi y j : i ≥ j} ∪ {xi y j : i <
j, {i, j} ∈
/ E(G)}. Hence, if C is an induced cycle of H of length ≥ 5, then C contains at
least three vertices either from Knx , or from Kny , thus it cannot be an induced cycle of H.
Let us now prove that H has no induced cycle of length ≥ 5. Assume that this is not
the case, and choose C with vertices xi1 , y j1 , . . . , xik , y jk , k ≥ 3, an induced cycle of H.
This means that {iℓ , jℓ } and {iℓ+1 , jℓ} are edges of G for 1 ≤ ℓ ≤ k, where we made
3

the convention that ik+1 = i1 . We may assume that i1 < i2 . If there exists ℓ such that iℓ <
jℓ+1 < jℓ , as G is closed, it follows that {iℓ , jℓ+1 } ∈ E(G) which implies that {xiℓ , y jℓ+1 } ∈
E(H), a contradiction, since C is an induced subgraph of H. Therefore, for all ℓ, we must
have either iℓ < iℓ+1 < jℓ < jℓ+1 or iℓ+1 < jℓ+1 ≤ iℓ < jℓ . As i1 < i2 , we may choose t to
be the largest index such that it < it+1 . Thus, we get it < it+1 < jt < jt+1 and it+2 < jt+2 ≤
it+1 < jt+1 , which implies that it+2 < jt+2 ≤ it+1 < jt < jt+1 . Since {it+2 , jt+1 } ∈ E(G)
and G is closed, we obtain {it+2 , jt } ∈ E(G) which leads to {xit+2 , y jt } ∈ E(H), again a
contradiction to the choice of C.

Corollary 2.4. Let G be a closed graph on [n] and H = inlex (G). Then
reg(S/I(H)) = indmatch(H).
Proposition 2.5. Let G be a connected closed graph on [n] and H = inlex (G). Then
indmatch(H) = ℓ, where ℓ is the length of the longest induced path of G.
Proof. First we show that indmatch(H) ≥ ℓ. This follows easily since it is obvious that if
i0 , . . . , iℓ is an induced path in G of length ℓ, then the edges {xi0 , yi1 }, {xi1 , yi2 }, . . ., {xiℓ−1 , yiℓ }
form an induced subgraph of H.
We show now that indmatch(H) ≤ ℓ. Let indmatch(H) = m. Then H has m pairwise
disjoint edges {xi1 , y j1 }, . . . , {xim , y jm } that form an induced subgraph of H. We may assume that i1 < · · · < im . To show the desired inequality we construct a path of length m in
G.
As G is closed, we may assume, as we have seen in Preliminaries, that all the facets of
the clique complex of G are intervals. This implies that, for s = 1, . . ., m, we may choose
the smallest index i′s among the indices t such that {xt , y js } ∈ E(H) and
{xi′1 , y j1 }, . . ., {xt , y js }, {xis+1 , y js+1 }, . . . , {xim , y jm }
is an induced matching of H.
By these arguments, we may assume already from the beginning that the induced subgraph of H with m pairwise distinct edges, {xi1 , y j1 }, . . . , {xim , y jm }, satisfies the following
condition:
(∗)

for all 1 ≤ s ≤ m, if t < s and {t, js} ∈ E(G),

then {xi1 , y j1 }, . . . , {xt , y js }, {xis+1 , y js+1 }, . . ., {xim , y jm } is not an induced matching of H.
Note that we also have jt ≤ it+1 for all 1 ≤ t ≤ m − 1. Indeed, if there exists t such that
jt > it+1 , then it follows that it < it+1 < jt . We obtain {it+1 , jt } ∈ E(G) and {xit+1 , y jt } ∈
E(H), a contradiction to our hypothesis.
In the second part of the proof we show that, under condition (∗) for the induced subgraph {xi1 , y j1 }, . . . , {xim , y jm } of H, we have:
(i) is and is+1 belong to the same clique of G for all 1 ≤ s ≤ m − 1,
(ii) is , is+1 , is+2 do not belong to the same clique for any 1 ≤ s ≤ m − 2.
4

Let us assume that we have already shown (i) and (ii). Then L : i1 , i2 , . . . , im , jm is
an induced path of G. Indeed, by (i), L is a path in G. Next, it is clear that we cannot
have an edge {is , iq } ∈ E(G) with q − s ≥ 2 by (ii). In addition, by (∗), it follows that
{is , jm } ∈
/ E(G) for any 1 ≤ s ≤ m − 1. Therefore, L is an induced path of G.
Let us first prove (ii). Suppose that there are three consecutive vertices is , is+1 , is+2 in
L which belong to the same clique of G. Hence {is , is+2 } ∈ E(G). As is < js ≤ is+1 <
js+1 ≤ is+2 < js+2 , we also have {is , js+1 } ∈ E(G), which is impossible.
Finally, we show (i). Let us assume that there exists s such that is and is+1 do not belong
to the same clique of G, in other words, {is, is+1 } ∈
/ E(G). In particular, we have js < is+1 ,
thus is < js < is+1 . We need to consider the following two cases.
Case (a). { js , is+1 } ∈ E(G). We claim that
{xi1 , y j1 }, . . ., {xis , y js }, {x js , yis+1 }, {xis+1 , y js+1 }, . . ., {xim , y jm }
is an induced subgraph of H with pairwise distinct edges. This will lead to contradiction
since indmatch(H) = m. To prove our claim, we note that {x js , y js+1 } ∈
/ E(H) by (∗)
and {xis , yis+1 } ∈
/ E(H) since {is , is+1 } ∈
/ E(G). Moreover, if {xiq , yis+1 } ∈ E(H) for some
q < s, then, as we have iq < is < js < is+1 , we get {iq , js} ∈ E(G), thus {xiq , y js } ∈ E(H),
contradiction. Similarly, if {x js , y jq } ∈ E(H) for some q ≥ s + 2, as js < is+1 < iq < jq ,
we get {is+1 , jq } ∈ E(G), that is, {xis+1 , y jq } ∈ E(H), contradiction.
Case (b). { js , is+1 } ∈
/ E(G). Let then j = min{t : {t, is+1} ∈ E(G)}. Since G is closed,
we must have j > js > is . Let us consider the following disjoint edges of H :
{xi1 , y j1 }, . . . , {xis , y js }, {x j , yis+1 }, {xis+1 , y js+1 }, . . ., {xim , y jm }.
These edges determine an induced subgraph of H,which leads again to a contradiction to
the fact that indmatch(H) = m. Indeed, since j < is+1 , it follows that { j, js+1 } ∈
/ E(G).
As in the previous case, we get {xiq , yis+1 } ∈
/ E(H) for q < s. Let us assume that {x j , y jq } ∈
E(H) for some q ≥ s + 2. Then { j, jq } ∈ E(G) and since j < is+1 < js+1 < jq , we get
{is+1 , jq } ∈ E(G) or, equivalently, {xis+1 , y jq } ∈ E(H), impossible.

Proof of Theorem 2.2. It is obvious that if Si is the polynomial ring in the indeterminates
N
indexed by the vertex set of Gi for 1 ≤ i ≤ r, then S/JG ∼
= ri=1 (Si /JGi ). Therefore,
reg(S/JG ) = ∑ri=1 reg(Si /JGi ). This equality shows that it is enough to prove our statement
for a connected closed graph G. Therefore, for the remaining part of the proof we take G
to be connected and show that reg(S/JG ) = ℓ, where ℓ is the length of the longest induced
path of G.
The inequality reg(S/JG ) ≥ ℓ is known by [8, Theorem 1.1]. On the other hand, by
using [6, Theorem 3.3.4] and Corollary 2.4, we get
reg(S/JG ) ≤ reg(S/ inlex (JG )) = reg(S/I(H)) = indmatch(H)
where H = inlex(G). But, by Proposition 2.5, indmatch(H) = ℓ, and this ends our proof.

5

Corollary 2.6. Let G be a closed graph. Then the regularity of JG and of inlex (JG ) do not
depend on the characteristic of the base field.
In [8], Matsuda and Murai conjectured that if G is a connected graph on n vertices, then
reg(S/JG ) = n − 1 if and only if G is a line graph. Theorem 2.2 gives a positive answer to
this conjecture for closed graphs.
Corollary 2.7. Let G be a connected closed graph on [n]. Then reg(S/JG ) = n − 1 if and
only if G is a line graph.
In [13], the following conjecture is proposed.
Conjecture 2.8. Let G be a graph. Then reg(S/JG ) ≤ r, where r is the number of maximal
cliques of G.
Note that, for chordal graphs, this conjecture implies Matsuda and Murai’s conjecture,
once we show that the latter is true for trees. Indeed, if G is a connected chordal graph
with reg(S/JG ) = n − 1, then, if Conjecture 2.8 is true, it follows that n − 1 ≤ r, thus G
must be a tree.
In the sequel, we first prove Conjecture 2.8 for the binomial edge ideals associated with
a special class of chordal graphs introduced in [5, Section 1], and, afterwards, we show
that Matsuda and Murai’s conjecture is true for this special class of graphs which includes
trees.
Theorem 2.9. Let G be a chordal graph on [n] with the property that any two distinct
maximal cliques intersect in at most one vertex. Then reg(S/JG ) ≤ r where r is the number
of maximal cliques of G.
Proof. Obviously, by using the argument given in the beginning of the proof of Theorem 2.2, we may assume that G is connected. We make induction on r and closely follow
some arguments given in the proof of [5, Theorem 1.1]. For r = 1, the statement is well
known. Let r > 1. As in the proof of [5, Theorem 1.1], let us consider F1 , . . ., Fr a leaf order on the facets of the clique complex ∆(G) of G. Since Fr is a leaf, there exists a unique
vertex, say i ∈ Fr , such that Fr ∩ Fj = {i} for some j. Let Ft1 , . . . , Ftq be the facets of ∆(G)
which intersect the leaf Fr in the vertex i. We decompose JG as JG = Q1 ∩ Q2 where Q1 is
the intersection of all minimal primes PS (G) of JG with i 6∈ S , and Q2 is the intersection
of all minimal primes PS (G) with i ∈ S . This decomposition yields the following exact
sequence of S-modules:
(1)

0 → S/JG → S/Q1 ⊕ S/Q2 → S/(Q1 + Q2 ) → 0.

In the proof of [5, Theorem 1.1], it was shown that Q1 = JG′ where G′ inherits the properties of G and has less than r cliques. Hence, by the inductive hypothesis, reg(S/JG′ ) < r.
In the same proof it was shown that Q2 = (xi , yi ) + JG′′ where G′′ is a chordal graph on
n − 1 vertices with q + 1 ≥ 2 components satisfying the conditions of the theorem and
6

with at most r cliques. Therefore, we get reg(S/Q2 ) ≤ r and, consequently, reg(S/Q1 ⊕
S/Q2 ) ≤ r. Finally, as it was observed in [5, Theorem 1.1], Q1 + Q2 = (xi , yi ) + JG′ , hence
S/Q1 + Q2 ∼
= Si /JH for a graph H on the vertex set [n] \ {i} which has the same properties
as G and a number of cliques < r. (Here Si is the polynomial ring in the variables indexed
by [n] \ {i}.) Consequently, by induction, we have reg(S/Q1 + Q2 ) < r.
By applying [10, Corollay 18.7] to the sequence (1), we get reg(S/JG ) ≤ r.

By using the notation and the arguments in the proof of the above theorem we also get
the following statement.
Corollary 2.10. Let G be be a connected chordal graph on [n] with the property that any
two distinct maximal cliques intersect in at most one vertex. If reg(S/JG ) = n − 1, then G
is a line graph.
Proof. By the above theorem, we have reg(S/JG ) ≤ r. Hence G has n − 1 cliques, which
implies that G is a tree. By using the sequence (1) and [10, Corollay 18.7], it follows that
at least one of the following inequalities must hold:
(i) reg(S/Q1) ≥ n − 1,
(ii) reg(S/Q2) ≥ n − 1,
(iii) reg(S/Q1 + Q2 ) ≥ n − 2.
The first inequality cannot hold since the graph G′ has a smaller number of cliques than G.
The second one is also impossible since it would imply that reg(S/Q2) = reg(Si /JG′′ ) ≥
n−1, and G′′ is a graph on n−1 vertices. Therefore, we must have (iii). Since reg(S/Q1 +
Q2 ) = reg(Si /JH ) where H is obtained form G′ by replacing the clique on the vertex set
Fr ∪(

q
S

j=1

Ft j ) by the clique on the vertex set Fr ∪(

q
S

j=1

Ft j )\{i} (see the proof of [5, Theorem

1.1]), by induction on n, it follows that H must be a line graph. This implies that the clique
on Fr ∪(

q
S

j=1

Ft j ) \ {i} has 2 vertices. In particular, it follows that q = 1 and G is a line graph


as well.

R EFERENCES
[1] N. Ay, J. Rauh, Robustness and conditional independence ideals, (2011) arXiv:1110.1338
[2] D. A. Cox, A. Erskine, On closed graphs, arXiv:1306.5149.
[3] M. Crupi, G. Rinaldo, Binomial edge ideals with quadratic Gröbner bases, Electron. J. Combin., 18
(2011), no. 1, # P211.
[4] V. Ene, J. Herzog, Gröbner bases in Commutative Algebra, Graduate Studies in Mathematics 130,
American Mathematical Society, 2011.
[5] V. Ene, J. Herzog, T. Hibi, Cohen-Macaulay binomial edge ideals, Nagoya Math. J. 204 (2011), 57–68.
[6] J. Herzog, T. Hibi, Monomial Ideals, Graduate Texts in Mathematics 260, Springer, 2010.
[7] J. Herzog, T. Hibi, F. Hreinsdotir, T. Kahle, J. Rauh, Binomial edge ideals and conditional independence
statements, Adv. Appl. Math. 45 (2010), 317–333.
[8] K. Matsuda, S. Murai, Regularity bounds for binomial edge ideals, J. Commut. Algebra 5 (2013),
141–149.
7

[9] M. Ohtani, Graphs and ideals generated by some 2-minors, Commun. Algebra 39 (2011), no. 3, 905–
917.
[10] I. Peeva, Graded syzygies, Algebra and Applications 14, Springer, 2011
[11] A. Rauf, G. Rinaldo, Construction of Cohen-Macaulay binomial edge ideals, arXiv:1205.0475
[12] S. Saeedi Madani, D. Kiani, Binomial edge ideals of graphs, Electron. J. Combin, 19 (2012), no. 2, #
P44.
[13] S. Saeedi Madani, D. Kiani, On the binomial edge ideal of a pair of graphs, Electron. J. Combin, 20
(2013), no. 1, # P48.
[14] P. Schenzel, S. Zafar, Algebraic properties of the binomial edge ideal of a complete bipartite graph,
to appear in An. St. Univ. Ovidius Constanta, Ser. Mat.
[15] R. Woodroofe, Matching, coverings, and Castelnuovo-Mumford regularity, Preprint, (2011),
arXiv:1009.2756v2
[16] S. Zafar, On approximately Cohen-Macaulay binomial edge ideal, Bull. Math. Soc. Sci. Math.
Roumanie, Tome 55(103) (2012) No. 4, 429–442.
V IVIANA E NE , FACULTY OF M ATHEMATICS AND C OMPUTER S CIENCE , OVIDIUS U NIVERSITY, B D .
M AMAIA 124, 900527 C ONSTANTA , ROMANIA
S IMION S TOILOW I NSTITUTE OF M ATHEMATICS OF ROMANIAN ACADEMY, R ESEARCH GROUP OF
THE PROJECT ID-PCE-2011-1023, P.O.B OX 1-764, B UCHAREST 014700, ROMANIA
E-mail address: vivian@univ-ovidius.ro
A NDREI Z AROJANU , S IMION S TOILOW I NSTITUTE OF M ATHEMATICS OF ROMANIAN ACADEMY,
R ESEARCH GROUP OF THE PROJECT ID-PCE-2011-1023, P.O.B OX 1-764, B UCHAREST 014700, RO MANIA

E-mail address: andrei zarojanu@yahoo.com

8

