Regularity of edge ideal of a graph
arXiv:1207.6249v1 [] 26 Jul 2012

Marcel Morales1, Ali Akbar Yazdan Pour1,2, Rashid Zaare-Nahandi2
1
2

Université de Grenoble I, Institut Fourier, Laboratoire de Mathématiques, France

Institute for Advanced Studies in Basic Sciences, P. O. Box 45195-1159, Zanjan, Iran

Abstract
In this paper, we introduce some reduction processes on graphs
which preserve the regularity of related edge ideals. As a consequence,
an alternative proof for the theorem of R. Fröberg on linearity of
resolution of edge ideal of graphs is given.

1

Introduction and Preliminaries

Throughout this paper, we assume that G is a simple finite graph on vertex
set [n] = {1, . . . , n}. A graph G is called chordal, if every induced cyclic
subgraph of G has length 3. A vertex v of a graph G is simplicial, if the
neighborhood of v in G is a complete subgraph. Let S = K[x1 , . . . , xn ] be
the polynomial ring over a field K with standard grading. The edge ideal of
G is defined by
I(G) = (xi xj :

{i, j} is an edge in G) ⊂ S.

Let I 6= 0 be a homogeneous ideal of S and N be the set of non-negative
integers. For every i ∈ N, one defines:
tSi (I) = max{j :

S
βi,j
(I) 6= 0}

S
where βi,j
(I) is the i, j-th graded Betti number of I as an S-module. The
Castelnuovo–Mumford regularity of I is given by:

reg (I) = sup{tSi (I) − i :

i ∈ Z}.

We say that the ideal I has a d-linear resolution, if I is generated by homogeS
neous polynomials of degree d and βi,j
(I) = 0, for all j 6= i + d and i ≥ 0. For
1

an ideal which has a d-linear resolution, the Castelnuovo–Mumford regularity
would be d.
Recently, several mathematicians have studied the regularity of edge ideals of graphs. Kummini in [7] has computed the Castelnuovo–Mumford
regularity of Cohen–Macaulay bipartite graphs and Van Tuyl in [14] has
generalized it for sequentially Cohen–Macaulay bipartite graphs. In [9] the
regularity was computed for very well-covered graphs, in [10], some bounds
were obtained for the regularity of edge ideals of vertex decomposable and
shellable graphs and in [15], the Castelnuovo–Mumford regularity was calculated for edge ideals of several other classes of graphs. Also [12] has studied
the topology of the lcm-lattice of edge ideals and derived upper bounds on
the Castelnuovo–Mumford regularity of the ideals.
The Alexander dual of a square-free monomial ideals, plays an essential
role in combinatorics and commutative algebra. For a square-free monomial ideal I = (M1 , . . . , Mq ) ⊂ S = K[x1 , . . . , xn ], the Alexander dual of I,
denoted by I ∨ , is defined to be:
I ∨ = PM 1 ∩ · · · ∩ PM q
where, PMi is prime ideal generated by {xj : xj |Mi }.
We begin with a well-known result of Eagon and Reiner and its generalization by Terai concerning the relation of the regularity of a square-free
monomial ideal and the Cohen-Macaulayness of its Alexander dual. For a
complete discussion of this fact, one can refer to [13].
Theorem 1.1 (Eagon-Reiner theorem [2, Theorem 3]). Let I be a square-free
monomial ideal in S = K[x1 , . . . , xn ]. The ideal I has a q-linear resolution
if and only if S/I ∨ is Cohen-Macaulay of dimension n − q.
Theorem 1.2 ([13, Theorem 2.1]). Let I be a square-free monomial ideal in
S = K[x1 , . . . , xn ] with dim S/I ≤ n − 2. Then,
S
S
−
depth
= reg (I) − indeg (I).
I∨
I∨
Here, indeg (I) indicates the initial degree of I. That is, the minimal degree
of a minimal generator of I.
dim

The following lemma was proved in [11].
Lemma 1.3. Let I, I1 and T be ideals in a commutative Noetherian local
ring (R, m) such that, I = I1 + T and
r := depth

R
R
≤ depth .
I1 ∩ T
T
2

Then, for all i < r − 1 one has:
 
 
R ∼ i R
i
Hm
.
= Hm
I1
I
Remark 1.4. Let I, J be square-free monomial ideals generated by elements
of degree d ≥ 2 in S = K[x1 , . . . , xn ]. By Theorem 1.2, we have
reg (I) = n − depth

S
,
I∨

reg (J) = n − depth

S
.
J∨

Therefore, reg (I) = reg (J) if and only if depth S/I ∨ = depth S/J ∨ .
For a graph G, let Ḡ denotes the complement of graph G. That is,
V (Ḡ) = V (G) and

E(Ḡ) = {i, j} : {i, j} ∈
/ E(G) .

Frequently in this paper, we take a graph G and we let I = I(Ḡ) be the edge
ideal of graph Ḡ. The following proposition was proved in [6, Proposition
4.1.1].
Proposition 1.5. If H is an induced subgraph of G on a subset of the vertices
of G, then:


S
S
I(Ḡ)
βi,j
I(H̄) ≤ βi,j

for all i, j.

Corollary 1.6. Let G be a graph and H an induced subgraph of G. If I(H̄)
does not have linear resolution, then the ideal I(Ḡ) does not have linear
resolution.

2

Reduction processes on graphs

In this section we introduce some reduction processes on vertices and edges
of a graph which preserve the regularity of the edge ideal of the complement
of the graph.
In the following, for convenience we use this notation:
x = x1 , . . . , xn ,

z = z1 , . . . , zr ,

Also for a subset F ⊂ [n], we set xF =

Q

i∈F

3

y = y1 , . . . , ym .

xi and PF = (xi :

i ∈ F ).

Lemma 2.1. Let S = K[x, y] be the polynomial ring and I be an ideal in
K[y]. Then,
S
S
depth
= depth
.
(x1 · · · xn ) IS
IS
Lemma 2.2. Let I 6= 0 be square-free monomial ideal in K[x, z] and J be
the ideal
J = I + (xi yj : 1 ≤ i ≤ n, 1 ≤ j ≤ m) ⊂ S := K[x, y, z].
Then, we have the followings:

(i) J ∨ = I ∨ ∩ x[n] , y[m] .

(ii) If zi zj ∈
/ I for all 1 ≤ i < j ≤ r, then reg (I) = reg (J).

Proof. (i) This is an easy computation.
(ii) By Remark 1.4, it is enough to show that, depth S/I ∨ = depth S/J ∨ .
We know that I ∨ is intersection of prime ideals PF , such that:
|F | = 2,

G(PF ) ⊂ {x, z} and

xF ∈ I.

Since zi zj ∈
/ I, for all 1 ≤ i < j ≤ r, it follows that P * {z}, for all
P ∈ Ass (I). Hence x[n] ∈ P , for all P ∈ Ass (I). This means that, x[n] ∈ I ∨ .
Now, by part (i) of this theorem, we have:

J ∨ = I ∨ ∩ x[n] , y[m]
 

(1)
= x[n] + y[m] I ∨ .

 

Clearly, x[n] ∩ y[m] I ∨ = x[n] y[m] . Hence by Lemma 1.3, we have:
!
 
S
S
∼

,
for all i < (m + n + r) − 2.
(2)
Hmi
= Hmi
J∨
y[m] I ∨

Since,

S
S
= (m + n + r) − 2 = dim ∨ ,
∨
J
I
from (2) and Lemma 2.2 we conclude that, depth S/I ∨ = depth S/J ∨ .
dim

Theorem 2.3. Let G1 and G2 be graphs on two vertex sets V1 and V2 respectively, such that V1 ∩ V2 = {z} and {zi , zj } ∈ E(G1 ) ∩ E(G2 ), for all
1 ≤ i < j ≤ r. Let
I1 = I(Ḡ1 ) ⊂ K[x, z],
I2 = I(Ḡ2 ) ⊂ K[y, z],

I = I G1 ∪ G2 ⊂ S = K[x, y, z].

be corresponding non-zero circuit ideals. Then,
4

(i) depth IS∨ = min{depth IS∨ , depth IS∨ }.
1

2

(ii) reg (I) = max{reg (I1 ), reg (I2 )}.
(iii) The ideal I has a 2-linear resolution if and only if both of I1 and I2
have a 2-linear resolution.
x1
..
.
xn

z1
..
.
zr

G1

y1
..
.
ym
G2

Proof. (i) We know that:
I = I1 + I2 + (xi yj :

1 ≤ i ≤ n,

1 ≤ j ≤ m) .

Let,
J1 = I1 + (xi yj :

1 ≤ i ≤ n,

1 ≤ j ≤ m) ,

J2 = I2 + (xi yj :

1 ≤ i ≤ n,

1 ≤ j ≤ m) .

Then, I ∨ = J1∨ ∩ J2∨ and by Lemma 2.2(ii), we have:

J1∨ + J2∨ = x[n] , y[m] .

From Mayer-Vietoris long exact sequence ([4, Proposition 5.1.8.]), we have
the long exact sequence:
!
 
 
 
S
S
S
S
i−1
i
i
i
 → Hm
· · · → Hm
⊕ Hm
→
→ Hm
∨
∨
I
J1
J2∨
x[n] , y[m]
!
S
 → ··· .
→ Hmi
x[n] , y[m]

Hence, for all i < (m + n + r) − 2, we have:
 
 
 
S
S ∼ i S
i
i
Hm
⊕ Hm
.
= Hm
J1∨
J2∨
I∨
5

This implies that,
depth

S
S
S
= min{depth ∨ , depth ∨ }.
∨
I
J1
J2

(3)

By Lemma 2.2(ii) and Remark 1.4, we have:
depth

S
S
=
depth
,
Ii∨
Ji∨

for i = 1, 2.

Hence, (i) follows from (3) and the above equality.
(ii) This is an easy consequence of (i) and Remark 1.4.
(iii) This is a direct consequence of (ii).
Lemma 2.4. Let G be a graph on vertex set [n] such that, {1, 2} ∈ E(G)
and

{1, i}, {2, i} * E(G),
for all i > 2.
(4)

Let I = I(Ḡ) ⊂ S = K[x1 , . . . , xn ] be the circuit ideal of G. Then,
(i) depth I ∨ +(xS 1 ,x2 ) ≥ depth IS∨ − 1.
(ii) depth I ∨ ∩(xS1 ,x2 ) ≥ depth IS∨ .

Proof. Let t := depth S/I ∨ ≤ dim S/I ∨ = n − 2.
(i) One can easily check that, condition (4) is equivalent to say that:
for all r > 2, there exists F ∈ E(Ḡ) such that, PF ⊂ (x1 , x2 , xr ).
Therefore,
I∨ =

\

F ∈E(Ḡ)





PF = 

\

PF  ∩ ((x1 , x2 , x3 ) ∩ · · · ∩ (x1 , x2 , xn ))

=

\

PF  ∩ (x1 , x2 , x3 · · · xn )

F ∈E(Ḡ)



F ∈E(Ḡ)



= I ∨ ∩ (x1 , x2 , x3 · · · xn ).

Clearly, x3 · · · xn ∈ I ∨ . Thus, from Mayer–Vietoris long exact sequence,






· · · → Hmi−1 IS∨ ⊕ Hmi−1 (x1 ,x2 ,xS 3 ···xn ) → Hmi−1 I ∨ +(xS 1 ,x2 ) → Hmi IS∨ → · · · .

we have:

Hmi−1



S
I ∨ + (x1 , x2 )



= 0,
6

for all i < t ≤ n − 2.

(5)

This proves (i).
(ii) From Mayer–Vietoris long exact sequence




i−1
i
S
S
· · · → Hm
→ Hm I ∨ ∩(x1 ,x2 ) → Hmi
I ∨ +(x1 ,x2 )
and (5), we have:

i
Hm

S
I ∨ ∩ (x1 , x2 )



= 0,

S
I∨



⊕

Hmi



S
(x1 ,x2 )



→ ··· .

for all i < t ≤ n − 2,

which completes the proof of (ii).
Theorem
2.5. Let G be a graph on vertex set [n] such that, {1, 2} ∈ E(G)

and {1, i}, {2, i} * E(G), for all i > 2. Let,

G1 = (G \ {1, 2}) ∪ {0, 1}, {0, 2}
be a graph on {0} ∪ [n] and I = I(Ḡ), J = I(Ḡ1 ) be circuit ideals in S =
K[x0 , x1 , . . . , xn ]. Then,
reg (I) = reg (J).

Proof. By Remark 1.4, it is enough to show that, depth S/I ∨ = depth S/J ∨ .
Let G1 = G \ {1, 2} and I1 = I(Ḡ1 ). Clearly, I1∨ = (x1 , x2 ) ∩ I ∨ and
!
n
\
J∨ =
(x0 , xi ) ∩ I1∨
i=3

= (x0 , x3 · · · xn ) ∩ I1∨ .

Moreover, our assumption implies that for all i > 2, there exists F ∈ E(Ḡ)
such that, PF ⊂ (x1 , x2 , xi ). Therefore,
I1∨ + (x0 , x3 · · · xn ) = (x0 , x3 · · · xn , I1∨)
= (x0 ) +

"

x3 · · · xn , (x1 , x2 ) ∩

\

F ∈Ḡ

PF

!#!

= (x0 ) +

(x1 , x2 , x3 ) ∩ · · · ∩ (x1 , x2 , xn ) ∩

= (x0 ) +

\

\

F ∈Ḡ

F ∈Ḡ

PF

!

7

= (x0 , I ∨).

PF

!!
(6)

Now, consider Mayer-Vietoris long exact sequence




 
S
S
S
i−1
i−1
i−1
⊕ Hm
· · · → Hm
→ Hm
→
I1∨
(x0 , x3 · · · xn )
(x0 , I ∨)
 


 
S
S
S
i
i
i
→ Hm
⊕ Hm
→ ··· .
(7)
→ Hm
J∨
I1∨
(x0 , x3 · · · xn )
Let t := depth IS∨ ≤ dim IS∨ = (n + 1) − 2. Consider two cases:
Case 1. t = (n + 1) − 2.
In this case, using Lemma 2.4(ii), we have:
(n + 1) − 2 = dim

S
S
S
S
= depth ∨ ≤ depth ∨ ≤ dim ∨ = (n + 1) − 2.
∨
I
I
I1
I1

This means that, depth S/I1∨ = (n + 1) − 2. Hence, by (7), we have:


 
S
S
i−1
i
∼
Hm
,
for all i < (n + 1) − 2
H
=
m
(x0 , I ∨ )
J∨
which implies that depth JS∨ = (n + 1) − 2 = t.
Case 2. t < (n + 1) − 2.
Since depth S/I1∨ ≥ t, by Lemma 2.4(ii) and the exact sequence (7), Hmi
0, for all i < t and we get the exact sequence

 

S
S
t
t−1
−→ Hm
.
0 −→ Hm
∨
(x0 , I )
J∨

This implies that, Hmt JS∨ 6= 0. Therefore, depth S/J ∨ = t.

S
J∨



=

Let G be a graph without any cycle of length 3 and G1 a subdivision
of G, that is, G1 is obtained by adding
some vertices

 on edges of G; then
Theorem 2.5 implies that reg I(Ḡ) = reg I(Ḡ1 ) . As an application of
the last reduction process, we state the following.
Corollary 2.6. Let C be a cycle of length n > 3 and I = I(C̄) ⊂ S =
K[x1 , . . . , xn ] be the circuit ideal of C. Then,
(i) reg (I) = 3; in particular I does not have linear resolution.
(ii) If G is not chordal graph, then the ideal I(Ḡ) does not have linear
resolution.
8


Proof. (i) Let E(C) = {1, 2}, {2, 3}, . . . , {n − 1, n}, {n, 1} . We use induction on n. For n = 4 an easy computation shows that, the minimal free
resolution of I(C̄) is:
0 → S(−4) → S 2 (−2) → I,
which is not linear. Assume that n > 4 and the theorem holds for cycles of
length n − 1. For a cycle C of length n, let C ′ be the graph (C \ 1) ∪ {1, 3}.
Then C ′ is a cycle of length n − 1 and by induction hypothesis, reg I(C̄ ′ ) = 3.
Using Theorem 2.5, we have reg I(C̄) = reg I(C̄ ′ ) = 3.
(ii) If G is not chordal, then G contains an induced cycle Cn with n > 3.
Now, from (i) and Corollary 1.6 we conclude that the ideal I(Ḡ) does not
have linear resolution.
Now, we state another reduction which is removing a simplicial vertex in
a graph.
Theorem 2.7. Let G be a graph on [n] and v be a simplicial vertex of G. Let
G1 = G \ v and I = I(Ḡ), J = I(Ḡ1 ) be the corresponding non-zero circuit
ideals in S = K[x1 , . . . , xn ]. Then,
reg (I) = reg (J).
Proof. By Remark 1.4, it is enough to show that, depth S/I ∨ = depth S/J ∨ .
Without loss of generality, we may assume that, N(v) = {1, . . . , v − 1} and
J ⊂ K[x1 , . . . , x̂v , . . . , xn ]. Therefore, we have:
I = J + (xv xi :

v < i ≤ n).

Moreover, since v is a simplicial vertex, we conclude that, xv+1 · · · xn ∈ J ∨ .
Hence we have:
!
n
\
I∨ = J∨ ∩
(xv , xi )
i=v+1

∨

= J ∩ (xv , xv+1 · · · xn )

= ((xv ) ∩ J ∨ ) + (xv+1 · · · xn ).
Clearly, ((xv ) ∩ J ∨ ) ∩ (xv+1 · · · xn ) = (xv · · · xn ). Hence by Lemma 1.3,
 


S ∼ i
S
i
Hm
,
for all i < n − 2.
= Hm
I∨
(xv ) ∩ J ∨
Since dim S/I ∨ = n−2, the above isomorphism and Lemma 2.1 implies that,
depth S/I ∨ = depth S/J ∨ .
9

Remark. Let G be a non-complete graph, v be a simplicial vertex of G
and G1 = G \ v. If G1 is a complete graph, then the ideal I = I(Ḡ) =
(xv xi : {v, i} ∈ E(Ḡ)) is a non-zero ideal and
Y
I ∨ = (xv ,
xi ).
{v,i}∈E(Ḡ)

In particular, I ∨ is Cohen-Macaulay and the ideal I has a 2-linear resolution
(Theorem 1.1).
If G1 is not a complete graph, then Theorem 2.7 implies that reg I(Ḡ) =
reg I(Ḡ1 ).
The following nice characterization of chordal graphs and Theorem 2.7,
enable us to prove that the ideal I(Ḡ) has a linear resolution, whenever G is
a chordal graph.
Theorem 2.8 ([8], essentially [1]). A graph G is chordal if and only if every
induced subgraph of G has a simplicial vertex.
Corollary 2.9. If G is a non-complete chordal graph, then the ideal I = I(Ḡ)
has a 2-linear resolution over any filed K.
Proof. Let G be a non-complete chordal graph. By Theorem 2.8, G has
simplicial vertex v. If G1 = G \ v, then G1 is again chordal graph. Now,
the induction and Theorem 2.7 together with the remark after Theorem 2.7,
yield the conclusion.
By Corollaries 2.6(ii) and 2.9 we have the following result which was first
proved by Fröberg in [3].
Corollary 2.10. A graph G is chordal if and only if I(Ḡ) has a linear resolution.
The class of chordal graphs are contained in the class of decomposable graphs
(c.f. [4, Lemma 9.2.1]). Using our reduction processes, we can find the regularity of decomposable graphs in terms of its indecomposable components.
Definition 2.11 (Decomposable Graph). Let G be a graph on vertex set
[n]. We say that G is decomposable, if there exists proper subsets P and Q
of [n] with P ∪ Q = [n] such that,
(a) {i, j} ∈ E(G), for all i, j ∈ P ∩ Q, i 6= j.
10

(b) {i, j} ∈
/ E(G), for all i ∈ P \ Q and j ∈ Q \ P .
Remark 2.12 (Regularity of Decomposable Graphs). Let G be a decomposable graph and P, Q be proper subsets of V (G) = [n] which satisfies in the
mentioned conditions.
• If both of GP and GQ are complete graphs, then:
I(Ḡ) = (xi yj :

i ∈ P \ Q,

j ∈ Q \ P ).

Hence,


I(Ḡ)∨ = 

Y

i∈P \Q

xi ,

Y

i∈Q\P



yi 

which is Cohen-Macaulay of dimension n − 2. Thus, reg I(Ḡ) = 2, by
Theorem 1.1.
• If GP is complete graph but GQ is not complete graph, then all v ∈ P \Q

are simplicial vertex. Hence by Theorem 2.7, reg I(Ḡ) = reg I G \ v .

If |P | = 1, we conclude that reg I(Ḡ) = reg I(ḠQ ). Otherwise, the
graph G′ = G\v is again decomposable with the components P ′ = P \v
and Q. Note that, G′P ′ is again a complete graph. Going on this
argument, we conclude that, reg I(Ḡ) = reg I(ḠQ ).

• If non of GP and GQ are complete graphs, then Theorem 2.3 implies
that, reg I(Ḡ) = max{reg I(ḠP ), reg I(ḠQ )}.
Remark 2.13. Let G be a (indecomposable) graph. After our reduction
processes (Theorems 2.5 and 2.7), finally we get a graph G′ with reg I(Ḡ) =
reg I(Ḡ′ ) and G′ has neither a simplicial vertex nor a subdivision. If at least
one of the connected components of G′ has cycle of length greater that 3,
then I(Ḡ) does not have a 2-linear resolution (Corollary 2.6(ii)).
But, sometimes we are not able to do more reduction on a graph. For
example, if G is the Peterson graph or the following Hamiltonian graph, then
we cannot apply our reduction process to further simplify G.

11

bc

bc

bc
bc
bc
bc
bc

bc

bc

bc

bc
bc
bc
bc

bc
bc

bc
bc

Peterson Graph

bc

bc

Hamiltonian Graph

References
[1] G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg
25(1961), 71–76.
[2] J. A. Eagon and V. Reiner, Resolutions of Stanley-Reisner rings and
Alexander duality, J. Pure and Applied Algebra 130 (1998), 265-275.
[3] R. Fröberg, On Stanley-Reisner rings, in: Topics in Algebra, Banach
Center Publications, 26 (2) (1990) 57–70.
[4] J. Herzog and T. Hibi, Monomial Ideals, in: GTM 260, Springer, London, (2010).
[5] J. Herzog, T. Hibi, X. Zheng, Dirac’s theorem on chordal graphs and
Alexander duality, European Journal of Combinatorics 25 (2004) 949960.
[6] S. Jacques, Betti numbers of graph ideals, PhD Thesis, University of
Sheffield, (2004). arXiv:math/0410107v1.
[7] M. Kummini, Regularity, depth and arithmetic rank of bipartite edge
ideals, J. Algebraic Combin. 30 (2009) 429-445.
[8] C.B. Lekkerkerker and J.C. Boland, Representation of finite graphs by
a set of intervals on the real line, Fund. Math. 51 (1962), 45-64.
[9] M. Mahmoudi, A. Mousivand, M. Crupi, G. Rinaldo, N. Terai,
S. Yassemi, Vertex decomposability and regularity of very wellcovered graphs, J. Pure Appl. Algebra 215 (2011) 2473–2480
arXiv:1006.1087v1

12

[10] S. Moradi, D. Kiani, Bounds for the regularity of edge ideal of vertex
decomposable and shellable graphs, Bull. Iranian Math. Soc. 36 (2) (2012)
267-277.
[11] M. Morales, A. Nasrollah Nejad, A. A. Yazdan Pour and R. ZaareNahandi, Monomial ideals with 3-linear resolutions, preprint (2011),
arXiv:1207.1790v1
[12] E. Nevo, Regularity via topology of the lcm-lattice for C4 -free graphs, J.
Combin. Theory Ser. A 118 (2) (2011) 491-501.
[13] N. Terai, Generalization of Eagon-Reiner theorem and h-vectors of
graded rings, preprint (2000).
[14] A. Van Tuyl, Sequentially Cohen–Macaulay bipartite graphs: vertex decomposability and regularity, Arch. Math. 93 (2009) 451-459.
[15] R. Woodroofe, Matchings, coverings, and Castelnuovo–Mumford regularity, Preprint. arXiv:1009.2756v2.
E-mail: morales@ujf-grenoble.fr
E-mail: yazdan@iasbs.ac.ir
E-mail: rashidzn@iasbs.ac.ir

13

