arXiv:1209.4972v2 [] 27 Sep 2012

COHEN-MACAULAY BINOMIAL EDGE IDEALS OF
SMALL DEVIATION
GIANCARLO RINALDO
Abstract. We classify all binomial edge ideals that are complete intersection and Cohen-Macaulay almost complete intersection. We also
describe an algorithm and provide an implementation to compute primary decomposition of binomial edge ideals.

Introduction
In 2010, binomial edge ideals were introduced in [4] and appeared independently also in [6]. Let S = K[x1 , . . . , xn , y1 , . . . , yn ] be the polynomial
ring in 2n variables with coefficients in a field K. Let G be a graph on
vertex set [n]. For each edge {i, j} of G with i < j, we associate a binomial
fij = xi yj − xj yi . The ideal JG of S generated by fij = xi yj − xj yi such
that i < j , is called the binomial edge ideal of G. Any ideal generated by
a set of 2-minors of a 2 × n-matrix of indeterminates may be viewed as the
binomial edge ideal of a graph.
Algebraic properties of binomial edge ideals in terms of properties of
the underlying graph were studied in [4], [2], [5] and [7]. In [5] and [7] the
authors considered the Cohen-Macaulay property of these graphs. However,
the classification of Cohen-Macaulay binomial edge ideals in terms of the
underlying graphs is still widely open and, as in the case of monomial edge
ideals introduced in [9], it seems rather hopeless to give a full classification.
In this paper we consider Cohen-Macaulay and unmixed binomial edge
ideals JG with small deviation, namely the difference between the minimum
number of the generators and the height of JG is less than or equal to 2.
Section 1 contains some preliminaries and notions that we use in the
paper. In the beginning of Section 2 we give a complete classification of the
complete intersection binomial edge ideals (Theorem 2.2), that is the case
of deviation 0. This results is a consequence of Corollary 1.2 of [5]. We also
observe that in general the almost complete intersection, namely deviation
1, binomial edge ideals are not unmixed. A nice example is the claw graph
(see Example 2.3). In Theorem 2.8 we give a complete classification of
Date: January 9, 2018.
2000 Mathematics Subject Classification. Primary 13F55, Secondary 13H10.
Key words and phrases. binomial ideal, unmixed, Cohen–Macaulay.
1

Cohen-Macaulay binomial edge ideals that are almost complete intersection
and we show that this set coincides with the set of unmixed binomial edge
ideals that are almost complete intersection.
In Section 3 we describe an algorithm to compute the primary decomposition of JG and provide an implementation in CoCoA (see [1]) that is
freely downloadable (see [8]). Thanks to this we computed Examples 3.2
and 3.3 that are unmixed binomial edge ideals of deviation 2 that are not
Cohen-Macaulay.
1. Preliminaries
In this section we recall some concepts and notations on graphs and on
simplicial complexes that we will use in the article.
Let G be a simple graph with vertex set V (G) and the edge set E(G).
A subset C of V (G) is called a clique of G if for all i and j belonging to C
with i 6= j one has {i, j} ∈ E(G). A vertex of a graph is called cutpoint if
the removal of the vertex increases the number of connected components.
A vertex v is a cut point of a graph G if and only if there exist u, w ∈ V (G)
such that v is in every path connecting u and w (see Theorem 3.1 of [3]).
A subgraph H of G spans G if V (H) = V (G). In a connected graph G
a chord of a tree T that spans G is an edge of G not in T . The number
of chords of any spanning tree of a connected graph G, namely m(G), is
called the cycle rank of G and is m(G) = |E(G)| − |V (G)| + 1 (see Corollary
4.5(a) of [3]). If G has c components than m(G) = |E(G)| − |V (G)| + c (see
Corollary 4.5(b) of [3]).
Let v 6∈ V (G). The cone of v on G, namely cone(v, G), is the graph with
vertices V (G) ∪ {v} and edges E(G) ∪ {{u, v} : u ∈ V (G)}.
Let G1 and G2 be graphs. We set G = G1 ∪ G2 (resp. G = G1 ⊔ G2
where ⊔ is disjoint union) where G is the graph with V (G) = V (G1 )∪V (G2 )
(resp. V (G) = V (G1 ) ⊔ V (G2 )) and E(G) = E(G1 ) ∪ E(G2 ) (resp. E(G) =
E(G1 ) ⊔ E(G2 )).
Set V = {x1 , . . . , xn }. A simplicial complex ∆ on the vertex set V is a
collection of subsets of V such that
(i) {xi } ∈ ∆ for all xi ∈ V ;
(ii) F ∈ ∆ and G ⊆ F imply G ∈ ∆.
An element F ∈ ∆ is called a face of ∆. A maximal face of ∆ with respect
to inclusion is called a facet of ∆. A vertex i of ∆ is called a free vertex of
∆ if i belongs to exactly one facet.
If ∆ is a simplicial complex with facets F1 , . . . , Fq , we call {F1 , . . . , Fq }
the facet set of ∆ and we denote it by F(∆).
The clique complex ∆(G) of G is the simplicial complex whose faces are
the cliques of G. Hence a vertex v of a graph G is called free vertex if it
belongs to only one clique of ∆(G).
2

We need notations and results from [4] (section 3) that we recall for the
sake of completeness.
Let T ⊆ [n], and let T = [n] \ T . Let G1 , . . . , Gc(T ) be the connected
components of the induced subgraph on T , namely GT . For each Gi , denote
ei the complete graph on the vertex set V (Gi ). We set
by G
[
(1.1)
PT (G) = ( {xi , yi }, JGe1 , . . . , JGe ),
c(T )

i∈T

T
PT (G) is a prime ideal. Then JG = T ⊂[n] PT (G). If there is no confusion
possible, we write simply PT instead of PT (G). Moreover, height PT =
n + |T |− c(T ) (see [4, Lemma 3.1]). We denote by M(G) the set of minimal
prime ideals of JG .
If each i ∈ T is a cut point of the graph GT ∪{i} , then we say that T has
cutpoint property for G. We denote by C(G) the set of all T ⊂ V (G) such
that T has cutpoint property for G.
Lemma 1.1. [4] PT (G) ∈ M(G) if and only if T ∈ C(G).
Lemma 1.2. [7] Let G be a connected graph. Then JG is unmixed if and
only if for all T ∈ C(G) we have c(T ) = |T | + 1.
2. Complete intersection and almost complete intersection

Let S be a standard graded polynomial ring over a field K. For a homogeneous ideal J ⊆ S, J is called a complete intersection ideal (resp. an
almost complete intersection ideal) if J is minimally generated by height J
(resp. height J + 1) elements. A homogeneous ideal has deviation dev(J) if
it is minimally generated by height I + dev(J) elements. Throughout this
section let S = K[{xi , yi } : i ∈ V (G)], JG be the binomial edge ideal of a
graph G and µ(JG ) the minimal number of generators of JG .
A nice combinatorial interpretation of dev(JG ) is given by the following
Remark 2.1. Suppose that height JG = height P∅ . Then height JG = n − c
where c are the connected components of G. Therefore
dev(JG ) = µ(JG ) − n + c = m(G).
Theorem 2.2. Let G be a graph. Then JG is complete intersection if and
only if each component of G is a path graph.
S
Proof. Let G = ci=1 Gi where Gi are the connected components of G. Let
ni = |V (Gi )| for i = 1, . . . , c. Since Gi is connected it has at least ni − 1
edges, namely the number of edges of a tree. Hence
µ(JG ) ≥

c
X

(ni − 1) = n − c.

i=1

3

Since JG is a complete intersection then it is unmixed, hence height JG =
height P∅ . By Remark 2.1 and since complete intersection implies dev(JG ) =
0 we obtain that µ(JG ) = n − c. Therefore every connected component Gi
is a tree. Now the proof is a consequence of Corollary 1.2 of [5].

In general almost complete intersection binomial edge ideals are not unmixed as the following example shows
Example 2.3. Let G be the graph on 4 vertices and edges
{{1, 2}, {1, 3}, {1, 4}},
namely the claw graph. We observe that
JG = P∅ ∩ P{1}
where height P∅ = 3 and height P{1} = 2.
Remark 2.4. If JG is an unmixed almost complete intersection binomial
edge ideal with c components we have that G has c − 1 components that are
path graphs and 1 that contains only one cycle, namely a unicyclic graph.
The proof is similar to the proof of Theorem 2.2.
Thanks to Remark 2.4 we assume from now on that G is a connected
unicyclic graph.
Proposition 2.5. Let G3 be the set of graphs such that for all G ∈ G3 we
have
V (G) = {u1 , . . . , ur , v1 , . . . , vs , w1 , . . . , wt }
with r ≥ 1, s ≥ 1, t ≥ 1 and edge set
E(G) ={{ui , ui+1 } : i = 1, . . . , r − 1} ∪ {vi , vi+1 } : i = 1, . . . , s − 1}∪
∪ {wi , wi+1 } : i = 1, . . . , t − 1} ∪ {{u1 , v1 }, {u1 , w1 }, {v1 , w1 }}.
Then S/JG is Cohen-Macaulay for all G ∈ G3 .
Proof. If r = s = t = 1 then G is a complete graph. Hence it is CohenMacaulay. Since u1 , v1 and w1 are free vertices in ∆(G), by Theorem 2.7
of [7] the assertion follows easily.

Lemma 2.6. Let G be the graph with vertex set V (G) = {1, . . . , 6} and
edge set E(G) = {{1, 2}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}, {5, 6}}. Then
S/JG is Cohen-Macaulay.
Proof. Let H1 be the graph with one vertex, V (H1 ) = {1}, H2 the path
graph with edges {3, 4} and {4, 5} and let G1 = cone(2, H1 ⊔ H2 ). By
Theorem 3.8 of [7] G1 is Cohen-Macaulay. Now let G2 be the complete
graph on the vertices V (G2 ) = {5, 6}. Then 5 is a free vertex in ∆(G1 ) and
∆(G2 ). By Theorem 2.7 of [7] the assertion follows.

4

Proposition 2.7. Let G4 be the set of graphs such that for all G ∈ G4 we
have
V (G) = {u1 , u2 , u3 , . . . , ur , v1 , v2 , v3 , . . . , vs }
with r ≥ 3 and s ≥ 3 and edge set
E(G) ={{ui , ui+1 } : i = 1, . . . , r − 1} ∪ {{vi , vi+1 } : i = 1, . . . , s − 1}∪
∪ {{u1 , v1 }, {u2 , v2 }}.
Then S/JG is Cohen-Macaulay for all G ∈ G4 .
Proof. Let s = r = 3. We observe that
C(G) = {∅, {u2 }, {v2 }, {u2 , v1 }, {u1 , v2 }, {u2 , v2 }}
and JG is unmixed with dim S/JG = 7 with S = K[{xi , yi } : i ∈ V (G)] .
We need to show that depth S/JG ≥ 7. Let
JH = P∅ ∩ P{u2 } ∩ P{v2 } ∩ P{u2 ,v1 } ∩ P{u2 ,v2 }
and
JH ′ = P∅ ∩ P{u2 } ∩ P{v2 } ∩ P{u1 ,v2 } ∩ P{u2 ,v2 }
be binomial edge ideals on S. The graphs H and H ′ are both isomorphic to
the graph described in Lemma 2.6. Hence they are Cohen-Macaulay with
dimension equal to 7. Let
JH ′′ = JH + JH ′ ⊂ S.
We observe that H ′′ = G1 ∪ G2 ∪ G3 where G1 is the complete graph on the
vertex set {u1 , u2 , v1 , v2 } and G2 (resp. G3 ) is the complete graph on the
vertex set {u2 , u3 } (resp. {v2 , v3 }). By Theorem 2.7 of [7], applied twice
(or by Theorem 1.1 of [5]) S/JH ′′ is Cohen-Macaulay with dimension equal
to 7. Thanks to depth Lemma applied to the following exact sequence
0 −→ S/JG −→ S/JH ⊕ S/JH ′ −→ S/JH ′′ −→ 0
we obtain that depth S/JG is greater than or equal to 7. Hence S/JG is
Cohen-Macaulay, too. The assertion follows by Theorem 2.7 of [7] observing
that u3 and v3 are free vertices in ∆(G).

Theorem 2.8. Let G be a graph and JG is an almost complete intersection
binomial edge ideal. The following conditions are equivalent:
(1) G is in G3 ∪ G4 defined as in Propositions 2.5 and 2.7;
(2) S/JG is CM;
(3) S/JG is unmixed.
Proof. 1) ⇒ 2). It follows by Propositions 2.5 and 2.7.
2) ⇒ 3). Always true.
5

3) ⇒ 1). Suppose that JG is unmixed. By Lemma 1.2 if G is unicyclic
then
!
r
[
Pi
(2.1)
G = Cl ∪
i=1

with 0 ≤ r ≤ l, where Cl is a cycle of length l and for all 1 ≤ i ≤ r,
Pi is a path graph, |V (Pi ) ∩ V (Cl )| = 1 and |V (Pi ) ∩ V (Pj )| = 0 for all
j 6= i. Suppose that G is not in G3 ∪ G4 . Then it is an element of one of
the following sets:
G3′ = {G satisfies (2.1) with l = 3} \ G3 ;
G4′ = {G satisfies (2.1) with l = 4} \ G4 ;
′ = {G satisfies (2.1) with l ≥ 5}.
G>
G does not belong to G3′ since it is the empty set. Let G ∈ G4′ . We have
that there are two vertices v and v ′ in C4 that are not adjacent and have
the same degree, that is either 2 or 3. We observe that T = {v, v ′ } has
the cutpoint property. If the degree is 2 then c(T ) = |T |, if the degree is
3 then c(T ) = |T | + 2. In both cases JG is not unmixed by Lemma 1.2.
Contradiction.
′ and let V (C ) = {i , i , . . . , i } such that {i , i
Let G ∈ G>
1 2
j j+1 } is an edge
l
l
of G with j = 1, . . . , l − 1 and {i1 , il } is an edge of G, too. Since G is
unicyclic then {i1 , i3 } has the cutpoint property. In fact GV \{i1 ,i3 } has at
least two connected components one containing the vertex i2 and another
containing the vertices {i4 , . . . , il }. Since JG is unmixed these components
are exactly 3. We may assume without loss of generality that i1 has degree
3 and i3 has degree 2.
By the same argument also {i2 , i4 } has the cutpoint property and either
i2 or i4 has degree 3. Suppose i4 has degree 3. Then {i1 , i4 } has the cutpoint
property and GV \{i1 ,i4 } has 4 connected components. Contradiction. Hence
i2 must have degree 3. Also {i3 , il } has the cutpoint property and since i3
has degree 2 then il has degree 3. Since {i2 , il } has the cutpoint property
and GV \{i1 ,i3 } has 4 connected components we obtain a contradiction.

3. An algorithm to compute primary decomposition
In this section we describe Algorithm 3.1 that summarizes the results of
Lemma 1.1 and Proposition 2.1 of [7] and provide an implementation in
CoCoA (see [1]) that is freely downloadable (see [8]). This tool help the
research of unmixed binomial edge ideals of deviation greater than or equal
to 2.
Algorithm 3.1 (Computation of C(G)).
Input: A simple connected graph G with V (G) = [n].
Output: The set C(G).
6

1. S := {1, . . . , n} \ {free vertices of ∆(G)}
2. C(G) = {∅}
3. For each T ⊂ S and 1 ≤ |T | ≤ n − 2 with T = {v1 , . . . , vr } do
3.1 If c(T ) > 1 then
i := 1
3.1.1 While c(T \ {vi }) < c(T ) and i ≤ r do
i := i + 1
3.1.2 If i > r then
C(G) := C(G) ∪ {T }
4. Return C(G)
We give a description of the Algorithm 3.1.
• Line 1. By Proposition 2.1 of [7] we can avoid all the free vertices
of ∆(G) in the computation of C(G).
• Line 2. The empty set is always in C(G) by Lemma 1.1.
• Line 3. T can be any subset of S by Lemma 1.1. Nevertheless
Since T has the cutpoint property, c(T ) ≥ 2 (see line 3.1). Therefore the maximum cardinality of T is n − 2 where the 2 connected
components are isolated vertices (if such T exists).
• Line 3.1. We observe that if c(T ) = 1 then c(T \ {vi }) = c(T ) for
all vi ∈ T . Hence we discard such T .
• Line 3.1.1-3.1.2. We check if exists a vi ∈ T that does not satisfy the
condition c(T \ {vi }) < c(T ). If such vi exists interrupt the current
computation otherwise add the new set to C(G) (line 3.1.2).
Thanks to Algorithm 3.1 we found some unmixed binomial edge ideals of
deviation 2 that are not Cohen-Macaulay. We provide two examples. The
first one is interesting since it is a bipartite graph. The second one since it
has induced 5-cycle subgraphs.

3
•
1•

• 4•
2
•
5

3
•
•
6

•7

1•

•
2

7

8
•

•
7

•
9

•4
•
5

Figure 1.

6
•

Example 3.2. Let JG the binomial edge ideal associated to the graph with
7 vertices in figure 1. Then
C(G) = {∅, {2}, {6}, {2, 6}, {3, 5}, {2, 4, 6}}
and is unmixed with dim S/JG = 8. Using CoCoA (see [1]) the depth =
S/JG = 7.
Example 3.3. Let JG the binomial edge ideal associated to the graph with
9 vertices in figure 1. Then
C(G) ={∅, {2}, {6}, {7}, {2, 6}, {2, 7}, {3, 5}, {3, 7}, {5, 6}, {6, 7},
{2, 3, 7}, {2, 4, 6}, {2, 4, 7}, {2, 5, 6}, {2, 6, 7}, {3, 5, 6}, {3, 5, 7},
{2, 4, 6, 7}}
and is unmixed with dim S/JG = 10. Using CoCoA (see [1]) the depth =
S/JG = 9.
References
[1] CoCoATeam, CoCoA: a system for doing Computations in Commutative Algebra,
Available at http://cocoa.dima.unige.it
[2] M. Crupi, G. Rinaldo, Binomial edge ideals with quadratic Gröbner bases, The Electronic Journal of Combinatorics, ISSN 1077-8926, 18, 2011, pp. 1–13.
[3] F. Harary, Graph theory, Addison-Wesley series in Mathematics, 1972.
[4] J. Herzog, T. Hibi, F. Hreinsdottir, T. Kahle, J. Rauh, Binomial edge ideals and
conditional independence statements, Advances in Applied Mathematics, 45 (2010)
317–333.
[5] V. Ene, J. Herzog, T. Hibi, Cohen-Macaulay binomial edge ideals, Nagoya Math. J.
Volume 204 (2011), 57–68.
[6] M. Ohtani, Graphs and ideals generated by some 2-minors, Comm. Algebra 39 (2011),
905–917.
[7] A. Rauf, G. Rinaldo Construction of Cohen-Macaulay binomial edge ideals, Accepted
in Comm. Algebra.
[8] G. Rinaldo, An algorithm to compute primary decomposition of binomial edge ideals,
available at http://ww2.unime.it/algebra/rinaldo/binedg.
[9] R.H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66 (1990) 277–293.
(Giancarlo Rinaldo) Dipartimento di Matematica, Universita’ di Messina, Viale
Ferdinando Stagno d’Alcontres, 31 98166 Messina, Italy.
E-mail address: giancarlo.rinaldo@tiscali.it

8

