REGULARITY OF EDGE IDEALS AND THEIR POWERS

arXiv:1712.00887v2 [] 11 Mar 2018

ARINDAM BANERJEE, SELVI BEYARSLAN, AND HUY TÀI HÀ
Abstract. We survey recent studies on the Castelnuovo-Mumford regularity of edge ideals
of graphs and their powers. Our focus is on bounds and exact values of reg I(G) and the
asymptotic linear function reg I(G)q , for q ≥ 1, in terms of combinatorial data of the given
graph G.

1. Introduction
Monomial ideals are classical objects that live at the crossroad of three areas in mathematics: algebra, combinatorics and topology. Investigating monomial ideals has led to many
important results in these areas. The new construction of edge ideals of (hyper)graphs has
again resurrected much interest in and regenerated a large amount of work on this class of
ideals (cf. [28, 51, 61] and references therein). In this paper, we survey recent works on the
Castelnuovo-Mumford regularity of edge ideals of graphs and their powers.
Castelnuovo-Mumford regularity is an important algebraic invariant which, roughly speaking, measures the complexity of ideals and modules. Restricting to the class of edge ideals
of graphs, our focus is on studies that relate this algebraic invariant to the combinatorial
data of given graphs. Our interest in powers of edge ideals is driven by the well-celebrated
result of Cutkosky, Herzog and Trung [15], and independently, Kodiyalam [42], that for any
homogeneous ideal I in a standard graded k-algebra R, the regularity of I q is asymptotically a linear function in q; that is, there exist constants a and b such that for all q  0,
reg I q = aq + b. Generally, the problem of finding the exact linear form aq + b and the
smallest value q0 such that reg I q = aq + b for all q ≥ q0 has proved to be very difficult. We,
thus, focus our attention also on the problem of understanding the linear form aq + b and
the value q0 for edge ideals via combinatorial data of given graphs.
The on-going research program in which algebraic invariants and properties of edge ideals
and their powers are investigated through combinatorial structures of corresponding graphs
has produced many exciting results and, at the same time, opened many further interesting
questions and conjectures. It is our hope to collect these works together in a systematic
way to give a better overall picture of the problems and the current state of the art of this
research area. For this purpose, we shall state theorems and present sketches of the proofs;
instead of giving full detailed arguments, our aim is to exhibit general ideas behind these
results, the similarities and differences when developing from one theorem to the next.
This paper can be viewed as a complement to the survey done in [27]. While in [27] the
focus was on the regularity of squarefree monomial ideals in general, our attention in this
paper is restricted mostly to edge ideals of graphs, but we enlarge our scope by discussing
1

also the regularity of powers of edge ideals. The later is an important area of study itself,
with a deep motivation from geometry, and has seen a surge of interest in the last few years.
The paper is outlined as follows. In Section 2, we collect notations and terminology used
in the paper. In Section 3, we present necessary tools which were used in works in this area.
Particularly, we shall give Hochster’s and Takayama’s formulas, which relate the graded
Betti numbers of a monomial ideal to the reduced homology groups of certain simplicial
complexes. We shall also describe inductive techniques that have been the backbones of
most of the studies being surveyed. In Section 4, we survey results on the regularity of edge
ideals of graphs. This section is divided into two subsections; the first one focusses on bounds
on the regularity in terms of combinatorial data of the graph, and the second one exhausts
cases where the regularity of an edge ideal can be computed explicitly. Section 5 discusses
the regularity of powers of edge ideals. This section again is divided into two subsections,
which in turn examine bounds for the asymptotic linear function of the regularity of powers
of edge ideals and cases when this asymptotic linear function can be explicitly described.
In Section 6, we recall a number of results extending the study of edge ideals of graphs to
hypergraphs. Since, our focus in this paper is on mostly edge ideals of graphs, our results
in Section 6 will be representative rather than exhaustive. We end the paper with Section
7, in which we state a number of open problems and questions which we would like to see
answered. We hope that these problems and questions would stimulate further studies in
this research area.
Acknowledgement. The authors would like to thank the organizers of SARC (Southern
Regional Algebra Conference) 2017 for their encouragement, which led us to writing this
survey. The last named author is partially supported by the Simons Foundation (grant
#279786) and Louisiana Board of Regent (grant #LEQSF(2017-19)-ENH-TR-25).
2. Preliminaries
In this section we recall preliminary notations and terminology of combinatorics and algebra that will be used throughout this survey. In Subsection 2.1 we give various definitions on
graphs, hypergraphs, and simplicial complexes. In Subsection 2.2 we recall basic homological algebra terminology. Finally, in the last subsection we define various algebraic objects
associated to (hyper)graphs and simplicial complexes.
2.1. Combinatorial preliminaries. For any finite simple graph G, with set of vertices
V (G) and set of edges E(G), we define some graph-theoretic notions as follows.
For any A ⊆ V (G), the induced subgraph on A is the graph whose set of vertices is A
and whose edges are exactly the edges of G that join two elements of A. In the following
example (Figure 1) H 0 is an induced subgraph of H, while H 00 is not an induced subgraph
of H as it misses the edge yw of H.
For any vertex x in a graph G the degree of x, denoted by d(x) is the number of vertices
connected to x. For any vertex x in a graph G the neighborhood of x, denoted by NG [x]
is the set consisting of x and all its neighbors. For the graph H 00 above, d(x) = 2 and
2

y

z

H: x

w

t
y

s

z

H 0: x

y

z

H 00 : x

w

w

s

s

Figure 1. Induced subgraphs
NG [x] = {x, y, w}. For any graph G and any vertex x, by G \ x we denote the induced
subgraph on V (G) \ {x}.
For any graph G, the complement graph, denoted by Gc , is the graph whose vertices are
the vertices of G and whose edges are the non-edges of G, i.e., for a, b ∈ V (G), ab is an edge
in Gc if and only if ab is not an edge in G. For the graph H in Figure 1, the following is H c .
y

z

H c: x

w

t

s

Figure 2. Complement graph
A cycle of length n in a graph G is a closed walk along its edges, x1 x2 , x2 x3 , . . . , xn−1 xn , xn x1 ,
such that xi 6= xj for i 6= j. We denote the cycle on n vertices by Cn . A chord in the cycle
Cn is an edge xi xj where xj 6= xi−1 , xi+1 . A graph is said to be chordal if for any cycle of
length greater than or equal to 4 there is a chord. A graph is said to be co-chordal if the
complement of G is chordal. The graph H in Figure 2 is chordal and H c is co-chordal.
A forest is a graph without any cycles. A tree is a connected forest.
A complete graph (or clique) on n vertices is a graph where for any two vertices there is
an edge joining them. It is denoted by Kn .
3

A bipartite graph is a graph whose vertices can be split into two groups such that there
is no edge between vertices of same group; only edges are between vertices coming from
different groups. It is easy to see that a graph is bipartite if and only if it is without any
cycle of odd length. We use Km,n to denote the complete bipartite graph with m vertices on
one side, and n on the other. We observe that H 00 in Figure 1 has no cycle, so it is a tree.
As a consequence it is also a bipartite graph with bipartition {x, z, s} and {y, w}.
Let G be a graph. We say two disjoint edges uv and xy form a gap in G if G does not have
an edge with one endpoint in {u, v} and the other in {x, y}. A graph without an induced
gap is called gap-free. Equivalently, G is gap-free if and only if Gc contains no induced C4 .
The graph H in Figure 1 is gap-free. In the following graph {x, y} and {z, w} form a gap.
y

z

G: x

w

s
Figure 3. A graph which is not gap-free
A matching in a graph is a set of pairwise disjoint edges. A matching is called an induced
matching if the induced subgraph on the vertices of the edges forming the matching has no
other edge. We observe that {x, y} and {z, w} forms an induced matching for graph G in
Figure 3.
Any graph isomorphic to K1,3 is called a claw. Any graph isomorphic to K1,n is called an
n-claw. If n > 1, the vertex with degree n is called the root in K1,n . A graph without an
induced claw is called claw-free. A graph without an induced n-claw is called n-claw-free.
y

x

w

t
Figure 4. A 3-claw (or simply, a claw)
A graph is called a diamond if it is isomorphic to the graph with vertex set {a, b, c, d} and
edge set {ab, bc, ac, ad, cd}. A graph without an induced diamond is called diamond-free.
4

A graph is said to be planar if as a 1-dimensional topological space it can be embedded
in the complex plane, i.e., if it can be drawn in the plane in such a way that no pair of edges
cross. The following graph in Figure 5 is a diamond. We observe that it is also planar.
y

z

x

t
Figure 5. A diamond
Any graph isomorphic to the graph with set of vertices {w1 , w2 , w3 , w4 , w5 } and set of edges
{w1 w3 , w2 w3 , w3 w4 , w3 w5 , w4 w5 } is called a cricket. A graph without an induced cricket is
called cricket-free. It is easy to see that a claw-free graph is also cricket-free.

y
w
x
t
z
Figure 6. A cricket
An edge in a graph is called a whisker if one of its vertices has degree one. A graph is
called an anticycle if its complement is a cycle.
x1

x4

x7

x5

x2

x3

x8

x9

x6

Figure 7. A hypergraph
A hypergraph is the natural higher degree analogue of graphs, in the sense that we allow
an edge to be a collection of any number of vertices. Formally speaking, a hypergraph
5

H = (V (H), E(H)) consists of the vertices V (H) = {x1 , . . . , xn } and the edges E(H), where
E(H) is a collection of nonempty subsets of the vertices. With this notation, a graph G is a
hypergraph whose edges are subsets of cardinality 2. By abusing notation, we often identify
an edge {xi1 , . . . , xir } ∈ E(H) with the monomial xi1 . . . xir . Figure 7 depicts a hypergraph
with edges {x1 x2 x3 x4 , x3 x4 x5 , x5 x6 x7 , x7 x8 , x9 }. In this example, the vertex x9 can also be
viewed as an isolated vertex.
A clutter is a hypergraph none of whose edges contains any other edge as a subset. The
hypergraph in Figure 7 is a clutter.
A simplicial complex with vertices {x1 , . . . , xn } is subset of the power set of {x1 , . . . , xn }
which is closed under the subset operation. The sets that constitute a simplicial complex are
called its faces. Maximal faces under inclusion are called facets. Figure 8 gives a simpicial
complex with facets {a, b, f }, {c, d, e}, {f, e},{b, c}.
e

f

a

d

b

c

Figure 8. A simplicial complex
An independent set in a graph G is a set of vertices no two of which forms an edge. The
independence complex of a graph G, denoted by ∆(G), is the simplicial complex whose faces
are independent sets in G.
a

e

c

d

b

f

Figure 9. A simple graph whose independence complex is in Figure 8
Let ∆ be a simplicial complex, and let σ ∈ ∆. The deletion of σ in ∆, denoted by del∆ (σ),
is the simplicial complex obtained by removing σ and all faces containing σ from ∆. The
link of σ in ∆, denoted by link∆ (σ), is the simplicial complex whose faces are
{F ∈ ∆ | F ∩ σ = ∅, σ ∪ F ∈ ∆}.
A simplicial complex ∆ is recursively defined to be vertex decomposable if either:
6

(i) ∆ is a simplex; or
(ii) there is a vertex v in ∆ such that both link∆ (v) and del∆ (v) are vertex decomposable,
and all facets of del∆ (v) are facets of ∆.
A vertex satisfying condition (2) is called a shedding vertex, and the recursive choice of
shedding vertices is called a shedding order of ∆.
Recall that a simplicial complex ∆ is said to be shellable if there exists a linear
order of
Sk−1  T
its facets F1 , F2 , . . . , Ft such that for all k = 2, . . . , t, the subcomplex
Fk is pure
i=1 Fi
and of dimension (dim Fk − 1). Here F represents the simplex over the vertices of F . It is a
celebrated fact that pure shellable complexes give rise to Cohen-Macaulay Stanley-Reisner
rings. Recall also that a ring or module is sequentially Cohen-Macaulay if it has a filtration
in which the factors are Cohen-Macaulay and their dimensions are increasing. This property
corresponds to (nonpure) shellability in general. Vertex decomposability can be thought
of as a combinatorial criterion for shellability and sequentially Cohen-Macaulayness. In
particular, for a simplicial complex ∆,
∆ vertex decomposable ⇒ ∆ shellable ⇒ ∆ sequentially Cohen-Macaulay.
2.2. Algebraic preliminaries. Let S = K[x1 , . . . , xn ] be a polynomial ring over a field K.
Let M be a finitely generated Zn -graded S-module. It is known that M can be successively
approximated by free modules. Formally speaking, there exists an exact sequence of minimal
possible length, called a minimal free resolution of M :
dp

d

d

d

2
1
0
0 −→ Fp −→ Fp−1 · · · −→
F1 −→
F0 −→
M −→ 0

L

(∗)

βi,σ

Here, Fi = σ∈Zn S(−σ) , where S(−σ) denotes the free module obtained by shifting the
degrees in S by σ. The numbers βi,σ ’s are positive integers and are called the multigraded
Betti numbers of M . We often identify σ with the monomial whose exponent vector is σ.
For example, over K[x, y], we may write βi,x2 y (M ) instead of βi,(2,1) (M ).
P
For every j ∈ Z, βi,j =
{σ | |σ|=j} βi,σ is called the (i, j)-th standard graded Betti
number of M . Three very important homological invariants that are related to these numbers
are the Castelnuovo-Mumford regularity, or simply regularity, the depth and the projective
dimension, denoted by reg(M ), depth(M ) and pd(M ) respectively:
reg M = max{|σ| − i | βi,σ 6= 0}
depth M = inf{i | Exti (K, M ) 6= 0}
pd M = max{i | there is a σ, βi,σ 6= 0}.
If S is viewed as a standard graded K-algebra and M is a graded S-module, then the
graded Betti numbers of M are also given by βi,j (M ) = dimk Tori (M, K)j , and so we have
reg M = max{j − i | Tori (M, K)j 6= 0}
pd M = max{i | Tori (M, K) 6= 0}
depth M = n − pd M.
In practice, we often work with short exact sequences, so it is worthwhile to mention
that the regularity can also be defined via the vanishings of local cohomology modules with
7

respect to the “irrelevant maximal ideal” m = (x1 . . . , xn ). Particularly, for i ≥ 0, define
(
i
i
max{j | Hm
(M )j 6= 0} if Hm
(M ) 6= 0
ai (M ) :=
−∞
otherwise.
Then, the regularity of M is also given by
reg M = max{ai (M ) + i}.
i

Example 2.1. Let M = Q[x1 , . . . , x5 ]/(x1 x2 , x2 x3 , x3 x4 , x4 x5 , x5 x1 ). Then the minimal free
resolution of M is:
d3
d2
d1
d0
0 −→ F3 −→
F2 −→
F1 −→
F0 −→
M −→ 0
Here:
β0,σ = 1 if σ = 1, and β0,σ = 0 otherwise
β1,σ = 1 if σ = x1 x2 , x2 x3 , x3 x4 , x4 x5 , x5 x1 , and β1,σ = 0 otherwise
β2,σ = 1 if σ = x1 x2 x3 , x2 x3 x4 , x1 x2 x5 , x1 x4 x5 , x3 x4 x5 , and β2,σ = 0 otherwise
β3,σ = 1 if σ = x1 x2 x3 x4 x5 , and β3,σ = 0 otherwise
An ideal I in S is said to be unmixed if all its associated primes are minimal of same height.
We say I (or equivalently S/I) is Cohen-Macaulay if the Krull dimension and depth are
equal. Cohen-Macaulay ideals are always unmixed and known to have many nice geometric
properties. It can be checked that the module M in Example 2.1 is Cohen-Macaulay.
2.3. Algebraic objects with underlying combinatorial structures. For any (hyper)graph
H over the vertex set V (H) = {x1 , . . . , xn }, its edge ideal is defined as follows:
Y
I(H) = ( x e ∈ E(H)) ⊆ S = K[x1 , . . . , xn ].
x∈e

Example 2.2. The edge ideal of the hypergraph, say H, in Figure 7, is
I(H) = (x1 x2 x3 x4 , x3 x4 x5 , x5 x6 x7 , x7 x8 , x9 ).
For any simplicial complex ∆ over the vertex set V = {x1 , . . . , xn }, its Stanley-Reisner
ideal is defined as follows:
Y
I∆ = ( x e is a minimal non-face of ∆) ⊆ S.
x∈e

Example 2.3. The Stanley-Reisner ideal of the simplicial complex in Figure 8 is
I∆ = (ac, ad, ae, bd, be, cf, df ).
As we have seen before, (hyper)graphs are related to simplicial complexes via the notion
of independence complex. The algebraic view of this relation exposes the following equality.
Lemma 2.4. Let G be a simple (hyper)graph and let ∆(G) be its independence complex.
Then
I(G) = I∆(G) .
8

Example 2.5. The edge ideal of the graph G in Figure 9 is the same as the the StanleyReisner ideal of the simplicial complex ∆ in Figure 8. Note that ∆ = ∆(G).
I(G) = (ae, ad, bd, be, bf, ec, ef )
For any simple graph G with V (G) = {x1 , . . . , xn }, we define the t-path ideal as:
It (G) = (xi1 · · · xit | ik 6= il for k 6= l, xik xik+1 an edge of G).
Example 2.6. The 3-path ideal of the five cycle C5 : x1 x2 x3 x4 x5 is
I3 (C5 ) = (x1 x2 x3 , x2 x3 x4 , x3 x4 x5 , x4 x5 x1 , x5 x1 x2 ).
Finally, as a matter of convention, for any (hyper)graph G, by reg G we mean reg I(G).
3. Formulas and inductive approaches
Computing non-vanishings of local cohomology modules or Betti numbers of an ideal
can be quite complicated. As a result, inductive techniques that relate regularity of edge
ideals with simplicial complexes and smaller ideals are employed as a common tool in the
literature. In this context, induced structures such as induced subcomplexes and induced
subgraphs have proven to be significant objects to investigate regularity of an edge ideal and
its powers.
In this section, we focus on the methods that enable us to bound and compute regularity
of an edge ideal and its powers. We start the section by recalling two important formulas.
Then we address a few inductive bounds that are widely used in the literature.
3.1. Hochster’s and Takayama’s Formulas. Hochster’s formula has been a significant
tool in the study of squarefree monomial ideals due to its power to relate the multigraded
Betti numbers of a simplicial complex ∆ to the non-vanishings of the reduced simplicial
homology groups of ∆ and its induced subcomplexes.
Theorem 3.1 (Hochster’s Formula [35]). Let ∆ be a simplicial complex on the vertex set V
and let I(∆) be its Stanley-Reisner ideal. Then
βi,j (I(∆)) =

X


e j−i−2 (∆W ; K)
dimk H

W ⊆V, |W |=j

where ∆W is the restriction of ∆ to the vertex set W.
For an arbitrary monomial ideal, Hochster’s formula can not be employed. Takayama’s
formula given in [58] can perform a similar task as Hochster’s formula for this class of ideals.
Let I ⊆ S = K[x1 , . . . , xn ] be a monomial ideal. Takayama’s formula provides a combinatorial description for the non-vanishings of Zn -graded component Hmi (S/I)a for a ∈ Zn , and
this description is given in terms of certain simplicial complexes ∆a (I) related to I. Note
that S/I is an Nn -graded algebra, and so Hmi (S/I) is a Zn -graded module over S/I.
The simplicial complex ∆a (I) is called the degree complex of I. The construction of ∆a (I)
was first given in [58] and then simplified in [48]. We recall the construction from [48].
9

For a = (a1 , . . . , an ) ∈ Zn , set xa = xa11 · · · xann and Ga := {j ∈ {1, . . . , n} | aj < 0}. For
every subset F ⊆ {1, . . . , n}, let SF = S[x−1
j | j ∈ F ]. Define
∆a (I) = {F \ Ga | Ga ⊆ F, xa ∈
/ ISF }.
Theorem 3.2 (Takayama’s Formula [58]). Let√I ⊆ S be a monomial ideal, and let ∆(I)
denote the simplicial complex corresponding to I. Then
(

e i−|Ga |−1 (∆a (I), K
dimk H
i
dimk Hm (S/I)a =
0

if Ga ∈ ∆(I),
otherwise.

The formula stated in [48] and here is different than the original formula introduced in
[58]. The original formula has additional conditions on a for Hmi (S/I)a = 0. It follows from
the proof in [58] that those conditions can be omitted.
Due to the equality between edge ideals of graphs and Stanley-Reisner ideals of their
independence complexes, we can employ Hochster’s and Takayama’s formulas in the study
of regularity of edge ideals.
In order to deal with arbitrary monomial ideals, polarization is proved to be a powerful
process to obtain a squarefree monomial ideal from a given monomial ideal. For details of
polarization we refer the reader to [32].
Definition 3.3. Let M = xa11 . . . xann be a monomial in S = K[x1 , . . . , xn ]. Then we define
the squarefree monomial P (M ) (polarization of M ) as
P (M ) = x11 . . . x1a1 x21 . . . x2a2 . . . xn1 . . . xnan
in the polynomial ring R = K[xij | 1 ≤ i ≤ n, 1 ≤ j ≤ ai ]. If I = (M1 , . . . , Mq ) is an ideal in
S, then the polarization of I, denoted by I pol , is defined as I pol = (P (M1 ), . . . , P (Mq )).
The regularity is preserved under polarization.
Corollary 3.4. [32, Corollary 1.6.3.d] Let I ⊂ S be a monomial ideal and I pol ⊂ R be its
polarization. Then reg(S/I) = reg(R/I pol ).
3.2. Inductive techniques. We start the section with an easy yet essential consequence
of Hochster’s formula that links the regularity of a graph with regularity of its induced
subgraphs.
Lemma 3.5. Let G be a simple graph. Then reg H ≤ reg G for any induced subgraph H of
G.
For any homogeneous ideal I ⊆ S and any homogeneous element m of degree d, the
following short exact sequences are used as standard tools in commutative algebra and also
proved to be very useful in computing regularity of edge ideals and their powers.

0 −→

R
R
·m R
(−d) −→
−→
−→ 0
I:m
I
I + (m)
10

(3.1)

Let I and J be ideals in S. Another useful exact sequence is:
0 −→

R R
R
R
→ ⊕ −→
−→ 0
I ∩J
I
J
I +J

(3.2)

We can see how regularity changes in a short exact sequence by taking the associated long
exact sequence of local cohomology modules. Particularly, we have the following inductive
bound (the second statement is the content of [17, Lemma 2.10 ]).
Lemma 3.6. Let I ⊆ S be a monomial ideal, and let m be a monomial of degree d. Then
reg I ≤ max{reg(I : m) + d, reg(I, m)}.
Furthermore, if x is a variable appearing in I, then
reg I ∈ {reg(I : x) + 1, reg(I, x)}.
In the statement of Lemma 3.6, the expression x is a variable appearing in I means some
of the minimal generators of I is divisible by x. Note that if x is a variable not appearing
in I, then reg(I, x) = reg I. In case of edge ideals, if x is an isolated vertex in G, we can
drop the vertex x when computing regularity. Thus reg(I(G) : x) = reg I(G \ NG [x]) and
reg(I(G), x) = reg(I(G \ x)) for any vertex x in G. Then Lemma 3.6 can be restated in terms
of edge ideals.
Lemma 3.7. Let x be a vertex in G. Then
reg G ∈ {reg(G \ NG [x]) + 1, reg(G \ x)}.
Kalai and Meshulam [39] proved the following result for squarefree monomial ideals and
Herzog [31] generalized it to any monomial ideal.
Theorem 3.8. Let I1 , . . . , Is be squarefree monomial ideals in S. Then
s
s
 X
 X
reg S/Ii
reg S
Ii ≤
i=1

i=1

In the case of edge ideals, we have the following bound.
Corollary
3.9. Let G be a simple graph. If G1 , . . . , Gs are subgraphs of G such that E(G) =
Ss
i=1 E(Gi ) then
s

 X
reg S/I(G) ≤
reg S/I(Gi )
i=1

If G is the disjoint union of graphs G1 , . . . , Gs then the above equality is achieved by using
Künneth formula in algebraic topology.
Corollary 3.10. Let G be a simple graph. If G can be written as a disjoint union of graphs
G1 , . . . , Gs then
s

 X
reg S/I(G) =
reg S/I(Gi )
i=1

11

In the study of powers of edge ideals, Banerjee developed the notion of even-connection
and gave an important inductive inequality in [5].
Theorem 3.11. For any simple graph G and any s ≥ 1, let the set of minimal monomial
generators of I(G)s be {m1 , . . . , mk }. Then
reg I(G)s+1 ≤ max{reg(I(G)s+1 : ml ) + 2s, 1 ≤ l ≤ k, reg I(G)s }.
In particular, if for all s ≥ 1 and for all minimal monomial generators m of I(G)s ,
reg (I(G)s+1 : m) ≤ 2 and reg I(G) ≤ 4, then reg I(G)s+1 = 2s + 2 for all s ≥ 1; as a
consequence I(G)s+1 has a linear minimal free resolution.
Working with the above inequality requires a good understanding of the ideal (I(G)s+1 :
m) and its generators when m is a minimal monomial generator of I(G)s . The even-connection
definition is key to attain this goal. We recall the definition of even-connectedness and its
important properties from [5].
Definition 3.12. Let G = (V, E) be a graph. Two vertices u and v (u may be the same
as v) are said to be even-connected with respect to an s-fold product e1 · · · es where ei ’s are
edges of G, not necessarily distinct, if there is a path p0 p1 · · · p2k+1 , k ≥ 1 in G such that:
(1)
(2)
(3)
(4)

p0 = u, p2k+1 = v.
For all 0 ≤ l ≤ k − 1, p2l+1 p2l+2 = ei for some i.
For all i, | {l ≥ 0 | p2l+1 p2l+2 = ei } | ≤ | {j | ej = ei } |.
For all 0 ≤ r ≤ 2k, pr pr+1 is an edge in G.

Fortunately, it turns out that (I(G)s+1 : m) is generated by monomials in degree 2.
Theorem 3.13. [5, Theorem 6.1 and Theorem 6.7] Let G be a graph with edge ideal I = I(G),
and let s ≥ 1 be an integer. Let m be a minimal generator of I s . Then (I s+1 : m) is minimally
generated by monomials of degree 2, and uv (u and v may be the same) is a minimal generator
of (I s+1 : m) if and only if either {u, v} ∈ E(G) or u and v are even-connected with respect
to m.
After polarization, the ideal (I(G)s+1 : m) can be viewed as the edge ideal of a graph
that is obtained from G by adding even-connected edges with respect to m. Some of the
combinatorial properties of this ideal in relation to G are studied in [37].
4. Regularity of edge ideals
Computing and/or bounding the regularity of edge ideals is the foundation in the study of
regularity of powers of edge ideals. In this section, we identify the combinatorial structures
that are related to regularity of edge ideals. First, we collect the general upper and lower
bounds given for the regularity of edge ideals, then we present the list of known classes of
graphs where the regularity is computed explicitly.
Note that regularity of an edge ideal is bounded below by 2, which is the generating degree
of an edge ideal. Thus, identifying combinatorial structures of a graph with regularity 2
12

can be considered as the base case of results in this section. The following combinatorial
characterization of such graphs is nowadays often referred to as Fröberg’s characterization.
It was, in fact, given first in topological language by Wegner [63] and later, independently,
by Lyubeznik [45] and Fröberg [25] in monomial ideals language.
Theorem 4.1 ([25, Theorem 1]). Let G be a simple graph. Then reg I(G) = 2 if and only
if G is a co-chordal graph.
4.1. Lower and upper bounds. One of the graph-theoretical invariants that can be related
to the regularity is the induced matching number. The first result revealing this relation is
due to Katzman and it provides a general lower bound on the regularity of edge ideals.
Theorem 4.2 ([41, Lemma 2.2]). Let G be a simple graph and ν(G) be the maximum size
of an induced matching in G. Then
reg I(G) ≥ ν(G) + 1.
Sketch of proof. Let {e1 , . . . , er } be an induced matching of maximal size in G. Suppose
H is the induced subgraph of G with E(H) = {e1 , . . . , er }. Note that all the edges in H are
disjoint. Thus reg(H) = r + 1. By Lemma 3.5, reg(G) ≥ ν(G) + 1.

Another graph-theoretical invariant of interest is the matching number and this invariant
actually emerges as a general upper bound for any graph.
Theorem 4.3 ([29, Theorem 6.7], [64, Theorem 11]). Let G be a simple graph. Let β(G) be
the minimum size of a maximal matching in G. Then
reg I(G) ≤ β(G) + 1.
Example 4.4. Let G be the graph given in Figure 10. It is clear that ν(G) = β(G) = 3.
Then reg G = 4 by Theorem 4.2 and Theorem 4.3. In general, if G is a simple graph with
disjoint edges, then the above bounds coincide and become an equality.

Figure 10. A graph with disjoint edges
Comparing the existing lower and upper bounds yields to interesting classifications, particularly when these bounds coincide. For example, Cameron and Walker [16, Theorem 1]
gave the first classification of graphs G with ν(G) = β(G). Then Hibi et al [34] modified
their result slightly and gave a full generalization with some corrections.
Example 4.5. Let G be the graph given in Figure 11. One can easily verify that β(G) = 2.
However reg G = 2 by Fröberg’s characterization. In general, we can find examples of graphs
where β(G) + 1 can be arbitrarily large compared to reg G.
13

Figure 11. A co-chordal graph
The above upper bound is strengthened by making use of co-chordal subgraph covers
of a graph and this bound is proved by Woodroofe. Recall that a graph is co-chordal if
its complement is chordal and co-chord(G), the co-chordal number of G, denotes the least
number of co-chordal subgraphs of G whose union is G. The graph in Figure 11 is an example
of a co-chordal graph.
Let {e1 , . . . , er } be a maximal matching of minimal size in G. For each i, let Gi be the
subgraph of G with edges ei ∪ { edges in G adjacent to ei }. Note that G1 , . . . , Gr forms a
co-chordal subgraph cover of G, thus co-chord(G) ≤ β(G) and the bound in Theorem 4.6
improves the bound in Theorem 4.3.
Theorem 4.6 ([64, Lemma 1]). Let G be a simple graph. Then
reg I(G) ≤ co-chord(G) + 1.
Sketch of proof. Let co-chord(G) = r and let G1 , . . . , Gr be a co-chordal cover of G. It
follows from Fröberg’s characterization of regularity 2 graphs, Theorem 4.1, that reg(Gi ) = 2
for each i ∈ {1, . . . , r}. Then the result follows immediately from Corollary 3.9.

Gap-free graphs have also been of interest in the investigation of regularity. These graphs
arise naturally since their induced matching number is 1 which is the smallest possible
number it could be. However, computing or bounding the regularity of this class of graphs
is not so easy. Furthermore, there are very few examples on how large the regularity of such
edge ideals can be, see [53] by Nevo and Peeva for an example of a gap-free graph G in
12 variables with reg G = 4. Putting an additional condition on the gap-freeness of G may
result with an upper bound and it is indeed achieved in [52] .
Theorem 4.7 ([52, Theorem 1.2], [17, Proposition 19]). If G is gap-free and claw-free, then
reg I(G) ≤ 3.
Sketch of proof. Let x be a vertex in G with the maximum possible degree. By Lemma
3.7, we have reg(G) ≤ max{reg(G \ NG [x]) + 1, reg(G \ x)}. Note that induced subgraphs
G \ NG [x] and G \ x of G are both gap-free and claw-free. It follows from the induction on
the number of vertices that reg(G \ x) ≤ 3. Thus it suffices to show that reg(G \ NG [x]) ≤ 2.
By Fröberg’s characterization, it is enough to prove that (G \ NG [x])c is chordal and it is
proved by contradiction:
(1) Suppose (G \ NG [x])c has an induced cycle on w1 , w2 , . . . , wn (in order) of length at
least 4.
(2) Any vertex of G is distance 2 from x in G by [17, Proposition 3.3], then {x, y} and
{y, w1 } are edges in G for some vertex y.
14

(3) Note that either {y, w2 } or {y, wn } must be an edge in G. Otherwise edges {w2 , wn }
and {x, y} form a gap in G.
(4) Without loss of generality, suppose {y, w2 } is an edge. Then the induced subgraph
on {x, y, w1 , w2 } is a claw in G, a contradiction.

Example 4.8. There are examples of gap-free and claw-free graphs where both values in
Theorem 4.7 can be attained for regularity. For example, if Gc is a tree then reg G = 2 and
if Gc is Cn for n ≥ 5 then reg G = 3.
This result is generalized to n-claw free and gap-free graphs by Banerjee in [5]. The proof
of the general case follows similarly and uses induction on n.
Theorem 4.9 ([5, Theorem 3.5]). If G is gap-free and n-claw-free, then reg I(G) ≤ n.
Another special class of graphs are planar graphs. This class of graphs emerges frequently
in applications since they can be drawn in the plane without edges crossing. It is given in
[64] that even though regularity of a planar graph may be arbitrarily large, regularity of its
complement can be bounded above by 4.
Theorem 4.10 ([64, Theorem 3.4]). If G is a planar graph, then reg I(Gc ) ≤ 4.
4.2. Exact values. Computing the regularity for special classes of graphs has been an
attractive research topic in the recent years. To that extend characterizing edge ideals with
certain regularity has been of interest as well. However, very little is known in the latter
case.
A combinatorial characterization of edge ideals with regularity 3 is still not known. However, a partial result for bipartite graphs is achieved by Fernández-Ramos and Gimenez in
[23]. Recall that a graph G is bipartite if the vertices V can be partitioned into disjoint
subsets V = X ∪ Y such that {x, y} is an edge in G only if x ∈ X and y ∈ Y or vice versa.
The bipartite complement of a bipartite graph G, denoted by Gbc , is the bipartite graph over
the same partition of vertices and {x, y} ∈ Gbc if and only if {x, y} ∈
/ G for x ∈ X, y ∈ Y.
Theorem 4.11 ([23, Theorem 3.1]). Let G be a connected bipartite graph. Then reg I(G) = 3
if and only if Gc has no induced cycles of length ≥ 4 and Gbc has no induced cycles of length
≥ 6.
In most of the known cases, it turns out that regularity can be expressed in terms of the
induced matching number. We first recall the results when the regularity is one more than
the induced matching number.
Theorem 4.12. Let G be a simple graph and ν(G) be the induced matching number of G.
Then
reg I(G) = ν(G) + 1
in the following cases:
15

(a)
(b)
(c)
(d)
(e)
(f )
(g)
(h)

G is a chordal graph (see [29]);
G is a weakly chordal graph (see [64]);
G is sequentially Cohen-Macaulay bipartite graph (see [62]);
G is unmixed bipartite graph (see [43]);
G is very well-covered graph (see [46]);
G is vertex decomposable graph and has no closed circuit of length 5 (see [40]);
G is a (C4 , C5 )-free vertex decomposable graph (see [7]);
G is a unicyclic graph with cycle Cn when
(i) n ≡ 0, 1 (mod 3) (see [2, 10, 36]) or
(ii) ν(G \ Γ(G)) < ν(G) where Γ(G) is the collection of all neighbors of the roots in
the rooted trees attached to Cn (see [2]).
x

w

y

t

z

Figure 12. A vertex decomposable and a (weakly) chordal graph
Remark 4.13. Chordal graphs are vertex decomposable and vertex decomposable graphs are
sequentially Cohen-Macaulay (see [26, 65]). Sequentially Cohen-Macaulay bipartite graphs
are vertex decomposable (see [62]). Also if G is a very well-covered graph then G is unmixed
and if G is chordal, then it is weakly chordal. Thus, (b) implies (a), and (e) implies (d).
Note that bipartite graphs have no odd cycles. Hence, (f ) implies (c).
Example 4.14. Let G be the graph given in Figure 13. Then Γ(G) = {x6 , x7 , x8 } and
ν(G \ Γ(G)) = 2 < ν(G) = 3. Furthermore, this graph does not belong to any of the classes
described in (a)—(g).
x5

x6

x7

x4

x1

x2

x8

x9

x10

x3

Figure 13. A graph satisfying (h) (ii) in Theorem 4.12
16

It is of interest to find different expressions for the regularity of edge ideals. The next
result collects all known cases in which the regularity has a different expression than the
above classes and it is still in terms of induced matching.
Theorem 4.15. Let G be a simple graph and ν(G) be the induced matching number of G.
Then
reg I(G) = ν(G) + 2
in the following cases:
(a) G is an n-cycle Cn when n ≡ 2 (mod 3) (see [10, 36]);
(b) G is a unicyclic graph with cycle Cn when n ≡ 2 (mod 3) and ν(G \ Γ(G)) = ν(G)
where Γ(G) is the collection of all neighbors of the roots in the rooted trees attached
to Cn (see [2]).
5. Regularity of powers of edge ideals
The regularity of powers of an edge ideal is considerably harder to compute than that
of the edge ideal itself. However, in many cases, known bounds and exact formulas for
the regularity of I(G) inspire new bounds and exact formulas for the regularity of I(G)q , for
q ≥ 1. This section is divided into two parts, where in the first subsection we list a number of
lower and upper bounds, and in the second subsection we give the exact values of reg I(G)q ,
for q ≥ 1, for special classes of graphs.
5.1. Lower and upper bounds. Just like with studies on the regularity of edge ideals,
the induced matching number of a graph is ultimately connected to the regularity of powers
of its edge ideal. The following general lower bound generalizes that of Theorem 4.2 for an
edge ideal to its powers.
Theorem 5.1 ([10, Theorem 4.5]). Let G be any graph and let I = I(G) be its edge ideal.
Then for all q ≥ 1, we have
reg I q ≥ 2q + ν(G) − 1.
Sketch of proof. The proof is based on the following observations:
(1) If H is an induced subgraph of G then for any i, j ∈ Z, we have
βi,j (I(H)q ) ≤ βi,j (I(G)q ).

(5.1)

In particular, this gives reg I(H)q ≤ reg I(G)q .
(2) If H is the induced subgraph of G consisting of a maximal induced matching of ν(G)
edges then for any q ≥ 1, we have
reg I(H)q = 2q + ν(G) − 1.

(5.2)

To establish the first observation, recall that the upper-Koszul simplicial complex K α (I)
associated to a monomial ideal I ⊆ S = K[x1 , . . . , xn ] at degree α ∈ Zn consists of faces
n
o
xα
W ⊆ {1, . . . , n} Q
∈I ,
w∈W w
17

and a variation of Hochster’s formula (Theorem 3.1) gives
e i−1 (K α (I); K) for all i ≥ 0.
βi,α (I) = dimk H
The inequality (5.1) then follows by noting that for α ∈ Zn with supp(α) ⊆ VH , K α (I(H)q ) =
K α (I(G)q ).
The second observation is proved by induction, noting that in this case I(H) is a complete
intersection.


Figure 14. A uniyclic graph
Example 5.2. Though there are many classes of graphs for which the lower bound given in
Theorem 5.1 is attained, there are also classes of graphs where the asymptotic linear function
reg I(G)q is strictly bigger than 2q + ν(G) − 1 for all q  0. Let G be the graph depicted in
Figure 14. Then it is easy to see that ν(G) = 2, whereas reg I(G)q = 2q + 2 for q ≥ 1.
A similar general upper bound generalizing that of Theorem 4.6 is, unfortunately, not
available. It is established, by Jayanthan, Narayanan and Selvaraja [37], only for a special
class of graphs — bipartite graphs.
Theorem 5.3 ([37, Theorem 1.1]). Let G be a bipartite graph and let I = I(G) be its edge
ideal. Then for all q ≥ 1, we have
reg I q ≤ 2q + co-chord(G) − 1.
Sketch of proof. The statement is proved by induction utilizing Theorem 3.11. The crucial
step in the proof is to show that for any q ≥ 1 and any collection of edges e1 , . . . , eq of G
(not necessarily distinct), we have
reg(I q+1 : e1 . . . eq ) ≤ co-chord(G) + 1.

(5.3)

Observe that when G is a bipartite graph, by [1, Lemma 3.7],
I q+1 : e1 . . . eq = (((I 2 : e1 )2 : . . . )2 : eq ),
and so (5.3) itself can be obtained by induction. To this end, let G0 be the graph associated
to the polarization of I 2 : e for an edge e in G (which is generated in degree 2 by Theorem
3.13). The proof is completed by establishing the following facts:
(1) reg I(G0 ) ≤ co-chord(G0 ) + 1. This inequality was proved to hold for any graph in
[64].
(2) co-chord(G0 ) ≤ co-chord(G). This is combinatorial statement, which can be shown
by analyzing how G0 is constructed from G.
18


Remark 5.4. Let G be a 4-cycle. We can easily verify that ν(G) = 1 and co-chord(G) = 1.
Since the lower bound in Theorem 5.1 coincides with the upper bound in Theorem 5.3, we
have reg I(G)q = 2q = 2q + ν(G) − 1 = 2q + co-chord(G) − 1 for all q ≥ 1. Classes of graphs
for which the two upper and lower bounds agree were discussed in [37, Corollary 5.1].
On the other hand, the upper bound given in Theorem 5.3 can be strict. For example,
if G is C8 , then ν(G) = 2 and co-chord(G) = 3. By [10, Theorem 5.2], it is known that
reg I(G)q = 2q + 1 < 2q + co-chord(G) − 1 for all q ≥ 1.
For a special class of graphs — gap-free graphs — there is another upper bound that was
proved by Banerjee [5].
Theorem 5.5 ([5, Theorem 6.19]). Let G be a gap-free graph and let I = I(G) be its edge
ideal. Then for all q ≥ 2, we have
reg I q ≤ 2q + reg I − 1.
Remark 5.6. The bound in Theorem 5.5 is slightly weaker than the conjectural bound of
Conjecture 7.11.
5.2. Exact values. In most of the known cases where the asymptotic linear function reg I(G)q
can be computed explicitly, the lower bound in Theorem 5.1 turns out to give the exact formula. In this subsection, we describe those instances.
In [33, Theorem 3.2], the authors showed that I(G) has a linear resolution if and only
if I(G)q has a linear resolution for all q ≥ 1. Combination of their result with Fröberg’s
characterization yields to the exact value of regularity of powers of co-chordal graphs.
Theorem 5.7. Let G be a co-chordal graph and I = I(G) be its edge ideal. Then for all
q ≥ 1, we have
reg I q = 2q.
As often the case when dealing with graphs, one of the first classes to consider is that of
trees and forests.
Theorem 5.8 ([10, Theorem 4.7]). Let G be a forest and let I = I(G) be its edge ideal.
Then for all q ≥ 1, we have
reg I q = 2q + ν(G) − 1.
Sketch of proof. Thanks to the general lower bound in Theorem 5.1, it remains to establish
the upper bound
reg I q ≤ 2q + ν(G) − 1.
In fact, a more general inequality can be proved for induced subgraphs of G. Let H and K
be induced subgraphs of K such that
EH ∪ EK = EG and EH ∩ EK = ∅.
Then the required upper bound follows from the following inequality (by setting H to be the
empty graph):
reg(I(H) + I(K)q ) ≤ 2q + ν(G) − 1.
19

(5.4)

The inequality (5.4) is proved by induction on q + |VK |, making use of the short exact
sequence arising by taking quotient and colon with respect to a leaf xy in K. Note that, by
[50, Lemma 2.10], we have
(I(H) + I(K)q ) : xy = (I(H) : xy) + (I(K)q : xy) = (I(H) : xy) + I(K)q−1 .

The next natural class of graphs to consider is that of cycles and graphs containing exactly
one cycle (i.e., unicyclic graphs).
Theorem 5.9 ([10, Theorem 5.2]). Let Cn denote the n-cycle and let I = I(Cn ) be its edge
ideal. Let ν = b n3 c be the induced matching number of Cn . Then

ν + 1 if n ≡ 0, 1 (mod 3)
reg I =
ν + 2 if n ≡ 2
(mod 3)
and for any q ≥ 2, we have
reg I q = 2q + ν − 1.
Sketch of proof. The first statement was already proved in [36]. To prove the second
statement, again thanks to the general lower bound of Theorem 5.1, it remains to establish
the upper bound
reg I q ≤ 2q + ν − 1.

(5.5)

The inductive method of Theorem 3.11 once again is invoked, and it reduces the problem
to showing that for any collection of edges e1 , . . . , eq of G (not necessarily distinct), we have
reg(I q+1 : e1 . . . eq ) ≤ ν + 1.
To this end, let J be the polarization of I q+1 : e1 . . . eq . It can be seen that
J = I(H) + (xi1 yi1 , . . . , xit yit ),
where H is a graph over the vertices {x1 , . . . , xn } and x2i1 , . . . , x2it are the non-squarefree
generators of I q+1 : e1 . . . eq . By using standard short exact sequences, it can be shown that
reg(J) = reg I(H).
Observe further that H contains Cn as a subgraph, so H has a Hamiltonian cycle. Thus,
the required upper bound now follows from a more general upper bound for the regularity of
a graph admitting either a Hamiltonian path or a Hamiltonian cycle (which is the content
of [10, Theorems 3.1 and 3.2]).

The following theorem was proved in the special case of whiskered cycles by Moghimian,
Seyed Fakhari, and Yassemi [49], and then in more generality for unicyclic graphs by Alilooee,
Beyarslan and Selvaraja [2].
Theorem 5.10 ([2, Theorem 1.2], [49, Proposition 1.1]). Let G be a unicyclic graph and let
I = I(G) be its edge ideal. Then for all q ≥ 1, we have
reg I q = 2q + reg I − 2.
20

Sketch of proof. The proof is based on establishing the conjectural bound of Conjecture
7.11.(2)
reg(I q ) ≤ 2q + reg I − 2.

(5.6)

The inequality (5.6) is proved by using induction on q. It also requires a good understanding of reg(I(Cn )q , f1 , . . . , fk ) where Cn is the cycle in G and f1 , . . . , fk are the edges of G
that are not in Cn . By making use of the general lower bound of Theorem 5.1 and the first
main result of [2], namely,

ν(G) + 2 if n ≡ 2(mod 3) and ν(G \ Γ(G)) = ν(G)
reg I =
ν(G) + 1 otherwise,
equality is achieved for the latter case. (Here, Γ(G) is a well described subset of the vertices
in G.) The proof is completed by showing reg(I(G\Γ(G))q ) = 2q +ν(G) and using inequality
(5.1).

Example 5.11. Let G be the graph depicted in Figure 15. Macaulay 2 computations show
that
reg I(G) = 5, reg I(G)2 = 6, reg I(G)3 = 8, reg I(G)4 = 10, reg I(G)5 = 12.
Thus, the formula given in Theorem 5.10 does not necessarily hold for a graph containing
more than 1 cycle.

Figure 15. A bicyclic graph
A particular interesting class of graph is those for which ν(G) = 1. It is expected that for
such a graph G, powers of its edge ideal should asymptotically have linear resolutions. This
is examined in the next two theorems under various additional conditions.
Theorem 5.12 ([5, Theorem 1.2]). Let G be a gap-free and cricket-free graph, and let
I = I(G) be its edge ideal. Then for all q ≥ 2, we have
reg I q = 2q;
i.e., I q has a linear resolution.
Sketch of proof. Since I q is generated in degree 2q, it remains to show that for q ≥ 2,
reg I q ≤ 2q. By induction, making use of the inductive techniques of Theorem 3.11 (and [5,
Theorem 3.4] which proves that reg I ≤ 3), it suffices to show that for any collection of edges
e1 , . . . , eq in G, reg(I q+1 : e1 . . . eq ) ≤ 2. Let J be the polarization of I q+1 : e1 . . . eq and let
H be the simple graph associated to J. The statement is reduced to showing that reg J = 2,
or equivalently (by Theorem 4.1), that H c is a chordal graph. That is, H does not have any
induced anticycle of length at least 4.
21

By contradiction, suppose that H has an anticycle w1 , . . . , ws of length at least 4. Since
an induced anticycle of length 4 gives a gap, we may assume further that s ≥ 5. Suppose
also that e1 = xy. The proof follows from the following observations:
(1) There must be an edge between {x, y} and {w1 , w3 }; otherwise xy and w1 w3 form a
gap in G.
(2) Suppose that xw1 ∈ EG . Then neither of w2 nor wn can coincide with x.
(3) Neither of w2 nor wn can coincide with y; otherwise the other vertex (among {w2 , wn })
and w1 would be even-connected implying that w1 w2 or w1 wn is an edge in H.
(4) Either w2 or wn must be connected to x; otherwise, xy and w2 wn form a gap in G.
(5) Suppose that xw2 ∈ EG . Now, by the same line of arguments applying to {w3 , wn },
we deduce that either w3 or wn must be a neighbor of x.
(6) Suppose that xw3 ∈ EG . We arrive at a contradiction that {w1 , w3 , x, y, w2 } forms a
cricket in G.

Theorem 5.13 ([21, Theorem 4.9]). Let G be a gap-free and diamond-free graph, and let
I = I(G) be its edge ideal. Then for all q ≥ 2, we have
reg I q = 2q;
i.e., I q has a linear resolution.
Sketch of proof. The proof of this theorem is based on a good understanding of the
combinatorial structures of gap-free and diamond-free graphs. Let ω(G) denote the largest
size of a complete subgraph in G (the clique number of G). If ω(G) < 3 then G is cricketfree, and the assertion follows from Theorem 5.12. If ω(G) ≥ 4, then it is shown that the
complement of G is chordal, and the conclusion follows from Theorem 4.1.
Consider the case where ω(G) = 3. It is shown that if, in addition, G is also C5 -free then
the complement of G is either chordal or C6 , and the assertion again follows from known
results. The essential part of the proof is then to examine the structures of G when G is
gap-free, diamond-free and contains a C5 . This is where novel and interesting combinatorics
happen. It is shown that, in this case, G can be obtained from a list of ten specific graphs
via a so-called process of multiplying vertices. The proof is completed with a careful analysis
of each of these ten graphs to show that reg(I(G)q+1 : e1 . . . eq ) ≤ 2 and to employ Banerjee’s
result, Theorem 3.11.

Another large class of graphs for which the regularity of powers of their edge ideals can be
computed explicitly is that of very well-covered graphs. The following theorem was proved
by Norouzi, Seyed Fakhari, and Yassemi [54] for very well-covered graphs with an additional
condition, and then by Jayanthan and Selvaraja [38] in full generality for any very wellcovered graph.
Theorem 5.14 ([38, Theorem 5.3], [54, Theorem 3.6]). Let G be a very well-covered graph
and let I = I(G) be its edge ideal. Then for all q ≥ 1, we have
reg I q = 2q + ν(G) − 1.
22

Sketch of proof. The proof also uses inductive techniques given by Theorem 3.11 and goes
along the same line as that of previous theorems in this section. The heart of the arguments
is to verify that for any collection of edges e1 , . . . , eq in G, we have
reg(I q+1 : e1 . . . eq ) ≤ ν(G) + 1.
If J = (I q+1 : e1 . . . eq ) is squarefree then this is achieved by letting H be the graph
associated to J and establishing the following facts:
(1) H is also very well-covered;
(2) ν(H) ≤ ν(G);
(3) reg I(H) = ν(H) + 1 and reg I(G) = ν(G) + 1 (this is the content of [46, Theorem
4.12]).
The arguments are much more involved for the case where J is not squarefree. Let H be
the graph corresponding to the polarization of J. The proof is completed by an ingenious
induction on the number of vertices added to G in order to obtain H.

6. Higher Dimension
In this section we discuss the regularity of squarefree monomial ideals generated in degree
more than two. The goal, as in the case of the edge ideals, is to find bounds and/or formulas
for regularity of the ideal in terms of “its combinatorics”. As mentioned in the preliminaries,
one can view these ideals both as Stanley-Reisner ideals or edge ideals of hypergraphs.
If interpreted as Stanley-Reisner ideals, via Hochster’s formula one can potentially get all
Betti numbers of a given ideal in terms of the combinatorics of the underlying complex. The
hypergraph case, however, is far less understood compared to either the edge ideal case or
the Stanley-Reisner ideal interpretation. However, in the last decade, some results have been
proven in that direction. In some cases, general squarefree monomial ideals can be viewed
as path ideals of simple graphs, and there has been some progress for those cases in the last
few years.
Since the main topic of this survey is the edge ideals, we are not trying to be comprehensive
in this section. Our aim is to give the reader an idea of possible approaches to generalize
the results on edge ideals to higher dimensions. We split the section into three subsections;
devoted to Stanley-Reisner ideals, edge ideals of hypergraphs and path ideals respectively.
6.1. Stanley-Reisner Ideals. As mentioned earlier, any squarefree monomial ideal can be
viewed as the Stanley-Reisner ideal of some simplicial complex. This combinatorial interpretation is by far the most studied one among monomial ideals generated in higher degrees.
The first result we mention is a famous theorem by Eagon and Reiner which establishes the
relation between minimal regularity and maximal depth as well as relation between regularity
of a Stanley-Reisner ideal and the structure of a special kind of dual complex, namely, the
Alexander dual. In a sense it is similar to Fröberg’s result; this gives a classification of linear
resolution. The Alexander dual of a simplicial complex ∆ is the simplicial complex whose
faces are the complements of the nonfaces of ∆. If I is a Stanley-Reisner ideal then by I ∨
we denote the Stanley-Reisner ideal of the Alexander dual of the simplicial complex of I.
23

Theorem 6.1 ([18, Theorem 3]). Let I be a Stanley-Reisner ideal in S = K[x1 , . . . , xn ].
Then I has q-linear resolution if and only if depth of S/I ∨ has depth n − q. In particular, I
has linear resolution if and only if the Alexander dual of ∆(I) is Cohen-Macaulay.
The next result bounds regularity with another important algebraic invariant, the arithmetic degree. For a squarefree monomial ideal I, its arithmetic degree, denoted by adeg(I),
is given by number of facets in the corresponding simplicial complex.
Theorem 6.2 ([24, Theorem 3.8]). Suppose I is a Stanley-Reisner ideal with codimension
≥ 2. Then, reg I ≤ adeg(I).
6.2. Hypergraphs. Any squarefree monomial ideal is the edge ideal of a hypergraph. The
corresponding simplicial complex is the independence complex of this hypergraph and computing that is an NP-hard problem in general.
The problem of finding bounds for the regularity of graphs can be extended to hypergraphs. In [13] the authors provided a sufficient condition for a hypergraph to have regularity
≤ 3. For every vertex x of a hypergraph H, let H : x denote the simple hypergraph of all
minimal subsets A ⊂ V \ {x} such that A or A ∪ {x} is an edge of H.
Theorem 6.3 ([13, Theorem 6.4]). Let H be a simple hypergraph such that H : x is a graph
whose complement is chordal for all vertices of H. Then, reg H ≤ 3.
Any hypergraph whose all edges have same cardinality is called uniform. A d-uniform
hypergraph (i.e., a uniform hypergraph whose all edges are represented by monomials of
degree d) is called properly-connected if for any two edges E, E 0 sharing at least one vertex,
the length of the shortest path between E and E 0 is d − |E ∩ E 0 |. If the length of the shortest
path between two edges is ≥ t then they are called t-disjoint (for relevant definitions see
[29]).
Example 6.4. Consider the 4-uniform hypergraph H with edge set:
{x1 x2 x3 x4 , x1 x2 x3 x7 , x1 x2 x6 x7 , x1 x5 x6 x7 , x1 x5 x6 x8 }
There is a proper irredundant chain of length 4 from the edge E = x1 x2 x3 x4 to E0 =
x1 x5 x6 x8 . Furthermore, there is no shorter such chain. But these edges have a nonempty
intersection. So H is not properly-connected since the distance between them is 4 which is
not same as 4 − |E ∩ E0 | = 3. This hypergraph is not properly-connected. On the other
hand every finite simple graph is properly connected.
A d-uniform properly connected hypergraph H is called triangulated if for any subset A
of vertices the induced subgraph H 0 on A has a vertex x such that the induced subgraph on
its neighborhood N (x) ∪ {x} is complete. For a more formal definition and relevant notions
see [29].
Example 6.5. Simple graphs that are triangulated are precisely the chordal graphs due to
Theorem 5.2 of [29].
The following result by Hà and Van-Tuyl gives a lower bound for regularity of properly
connected hypergraphs and the bound becomes an equality if the hypergraph is triangulated.
24

Theorem 6.6 ([29, Theorem 6.5 and 6.8]). Let H be a properly-connected hypergraph. Suppose d is the common cardinality of the edges in H. Let c be the maximal number of pairwise
d + 1 disjoint edges in H. Then, reg H ≥ (d − 1)c + 1, and the equality occurs if H is
triangulated.
A 2-collage for a hypergraph is a subset C of the edges with the property that for every
edge E of the hypergraph, we can delete a vertex v of E so that E \ {v} is contained in
some edge of C. For uniform hypergraphs, the condition for a collection C of the edges to
be a 2-collage is equivalent to requiring that for any edge E not in C, there exists F ∈ C
such that the symmetric difference of E and F consists of exactly two vertices. When H
is a graph, it is straightforward to see that for any minimal 2-collage, there is a maximal
matching of the same or lesser cardinality.
The following theorem gives a formula for regularity of uniform hypergraphs in terms of
its collages.
Theorem 6.7 ([30, Theorem 1.1]). Let H be a simple d-uniform hypergraph and let c be
the minimum size of a 2 collage in H. Then, reg I(H) ≤ (d − 1)c + 1.
The next theorem is a generalization of the previous that work for all simple hypergraph.
Theorem 6.8 ([30, TheoremP1.2]). Let H be a simple hypergraph and let {m1 , ...., mc } be a
2-collage. Then, reg I(H) ≤ ci=1 |mi | − c + 1.
The next theorem gives a formula for regularity of edge ideals of clutters, which are
hypergraphs where no edge contains any other edge as a subset. A monomial ideal I has
linear quotients if the monomials that generate I can be ordered g1 , . . . , gq such that for all
1 ≤ i ≤ q − 1, ((g1 , . . . , gi ) : gi+1 ) is generated by linear forms. For further details see [51].
Theorem 6.9 ([51, Corollary 3.35]). Let H be a clutter such that I(H) has linear quotients.
Then, reg I(H) = max{|E| : E ∈ E(H)}.
Taylor resolutions, introduced in [59], are free resolutions of monomial ideals constructed
in a natural way that makes computations easy to deal with. These are in general not
minimal. The following theorem gives a formula for regularity when Taylor resolutions are
minimal. A hypergraph H is called saturated when the Taylor resolution of I(H) is minimal.
For further details see [44].
Theorem 6.10 ([44, Proposition 4.1]). For a saturated hypergraph H, we have reg I(H =
|X| − |L| + 1. Here L is the minimal monomial generating set of I(H) and X is the number
of variables that divide some minimal monomial generator.
6.3. Path Ideal. Path ideals of finite simple graphs are interesting generalizations of edge
ideals, see Section 2.2 to recall the definition of path ideals. For gap-free graphs their
regularity too tend to behave nicely.
Theorem 6.11 ([11, Theorem 1.1]). Let G be a gap-free and claw-free graph. Then for all
t ≤ 6, It has linear resolution. If further G is induced whiskered-K4 free then for all t, It
has linear resolution.
25

Let Ln denote a line of length n. The regularity of path ideals of lines have been computed
by Alilooee and Faridi in the next theorem.
Theorem 6.12 ([3, Theorem 3.2]). Let n, t, p and d be integers such that n ≥ 2, 2 ≤ t ≤
n, n = (t + 1)p + d, where p ≥ 0, 0 ≤ d ≤ t. Then, reg It (Ln ) is p(t − 1) + 1 for d < t and
(p + 1)(t − 1) + 1 for d = t.
We end this section by a result regarding a somewhat different kind of path ideals. A
tree is a graph in which there exists a unique path between every pair of distinct vertices; a
rooted tree is a tree together with a fixed vertex called the root. In particular, in a rooted
tree there exists a unique path from the root to any given vertices. We can also view a rooted
tree as a directed graph by assigning to each edge the direction that goes “away” from the
root. Let Γ be a rooted tree and It (Γ) be the squarefree monomial ideal generated by all
“directed paths” of length t − 1 in the above sense. The following theorem gives regularity
of such ideals.
In this theorem, we define lt (Γ) to be the number of leaves in Γ whose level is at least
t − 1 and pt (Γ) to be the maximal number of pairwise disjoint paths of length t in Γ (i.e.,
pt (Γ) = max{|D| | D is a set of disjoint paths of length t in Γ}).
Theorem 6.13 ([9, Theorem 3.4]). Let Γ be a rooted tree on n vertices. Then, reg It (Γ) ≤
(t − 1)[lt (Γ) + pt (Γ)] + 1.
7. Open problems and questions
We end the paper by listing a number of open problems and questions in the research
area which we hope to be solved.
Our first problem is inspired by Theorems 4.1 and 4.11. Since graphs with regularity 2
are classified. The next class of graph to examine is that of regularity 3.
Problem 7.1. Characterize graphs G for which reg I(G) = 3.
In various results, for example Theorems 4.7 and 6.3, “local” condition on the regularity
of G : x for all vertices x lead to a “global” statement on the regularity of G. We ask if
similar local conditions on G : x, for all vertices x, would also lead to a statement on the
asymptotic linear function reg I(G)q .
Question 7.2. Let G be a simple graph and let I = I(G) be its edge ideal. Suppose that
for any vertex x in G, we have reg(I : x) ≤ r. Does this imply that for any q ≥ 1,
reg I q ≤ 2q + r − 1?
As noted in Lemma 3.7, for any vertex x, the regularity of I(G) is always equal to either
the regularity of I(G) : x or the regularity of (I(G), x). It would be interesting to know for
which vertex x the equality happens one way or another.
Problem 7.3. Let G be a graph and let I = I(G) be its edge ideal. Find conditions on a
vertex x of G such that
(1) reg I = reg(I, x).
26

(2) reg I = reg(I : x).
The regularity of I(G) has been computed for several special classes of graphs (see Theorem 4.12). A particular class of graphs which is of interest is that of vertex decomposable
graphs. For a vertex decomposable graph G, the statement of Lemma 3.7 can be made
slightly more precise (see [30]), namely, there exists a vertex x such that
reg G = max{reg(G \ NG [x]) + 1, reg(G \ x)}.
For such a graph G, it is also known that the independent complex ∆(G) is shellable and
the quotient ring S/I(G) is sequentially Cohen-Macaulay.
Problem 7.4. Let G be a vertex decomposable graph. Compute reg I(G) via combinatorial
invariant of G.
As noted throughout Sections 4 and 5, the induced matching number of a graph G is
closely related to the regularity of I(G). In fact, ν(G) + 1 gives a lower bound for reg I(G)
and, more generally, 2q +ν(G)−1 gives a lower bound for reg I(G)q for any q ≥ 1. Moreover,
for many special classes of graphs the equality has been shown to hold. Thus, it is desirable
to characterize all graphs for which the equality is attained.
Problem 7.5. Characterize graphs G for which the edge ideals I = I(G) satisfy
(1) reg I = ν(G) + 1.
(2) reg I q = 2q + ν(G) − 1 ∀ q  0.
When ν(G) = 1, the answer to Problem 7.5.(2) is predicted in the following open problem.
Problem 7.6 (Francisco-Hà-Van Tuyl and Nevo-Peeva). Suppose that ν(G) = 1, i.e., Gc
has no induced 4-cycle and let I = I(G).
(1) Prove (or disprove) that reg I q = 2q for all q  0.
(2) Prove (or disprove) that reg I q+1 = reg I q + 2 for all q ≥ reg(I) − 1.
Note that examples exist in which ν(G) = 1 and reg I q 6= 2q for small values of q (cf.
[53]), so in Problem 7.6 it is necessary to consider q  0. A satisfactory solution to Problem
7.1 would be a good starting point to tackle Problem 7.6, since regularity 3 is the first open
case of the problem. In fact, in this case, reg I(G)q is expected to be linear starting at q = 2.
Problem 7.7 (Nevo-Peeva). Suppose that ν(G) = 1 and reg I(G) = 3. Then is it true that
for all q ≥ 2,
reg I(G)q = 2q?
In many known cases where the asymptotic linear function reg I(G)q can be computed, it
happens to be reg I(G)q = 2q + ν(G) − 1. We would like to see if this is the case when the
equality is already known to hold for small values of q. If this is indeed the case then how
far one must go before concluding that the equality holds for all q ≥ 1?
Problem 7.8. Let G be a graph. Find a number N such that if reg I(G)q = 2q + ν(G) − 1
for all 1 ≤ q ≤ N then, for all q ≥ 1, we have
reg I(G)q = 2q + ν(G) − 1.
27

(Computational experiments seem to suggest that N can be taken to be 2.)
A particularly related question is whether for special classes of graphs satisfying reg I(G) =
ν(G) + 1 one would have reg I(G)q = 2q + ν(G) − 1 for all q ≥ 1 (or for all q  0). Inspired
by Theorem 4.12, we raise the following question.
Question 7.9. Let G be a graph and let I = I(G) be its edge ideal. Suppose that G is of
one of the following types:
(1)
(2)
(3)
(4)
(5)

G
G
G
G
G

is
is
is
is
is

chordal;
weakly chordal;
sequentially Cohen-Macaulay bipartite;
vertex decomposable and contains no closed circuit of length 5;
(C4 , C5 )-free vertex decomposable.

Is it true that for all q  0,
reg I q = 2q + ν(G) − 1?
Note that chordal graphs and sequentially Cohen-Macaulay bipartite graphs are vertex
decomposable. Also bipartite graphs contain no closed circuit of length 5. Thus, in Question
7.9, an affirmative answer to part (4) would imply that for part (3).
It is well-known that the resolution of a monomial ideal is dependent on the characteristic
of the ground field. And yet, in all known cases where the regularity of powers of an edge
ideal can be computed, it is characteristic-independent. We would like to see examples where
this is not the case, or a confirmation that this is always the case if the regularity of the edge
ideal itself is characteristic-independent.
Problem 7.10.
(1) Find examples of graphs G for which the asymptotic linear function reg I(G)q , for
q  0, is characteristic-dependent.
(2) Suppose that reg I(G) is independent of the characteristic of the ground field. Is
the asymptotic linear function reg I(G)q , for q  0, necessarily also characteristicindependent?
When an exact formula may not be available, it is of interest to find a lower and an upper
bound. Since the lower bound in Theorem 5.1 holds for any graph, it is desirable to find
an upper bound to couple with this general lower bound. In this direction, one may either
try to prove the bound in Theorem 5.3 for any graph or to relate the regularity of powers of
I(G) to the regularity of I(G) itself.
Conjecture 7.11 (Alilooee, Banerjee, Beyarslan and Hà). Let G be any graph and let
I = I(G) be its edge ideal. Then for all q ≥ 1, we have
(1) reg I q ≤ 2q + co-chord(G) − 1.
(2) reg I q ≤ 2q + reg I − 2.
(3) reg I q+1 ≤ reg I q + 2.
Note that by Theorem 4.6, Conjecture 7.11.(3) ⇒ Conjecture 7.11.(2) ⇒ Conjecture
7.11.(1).
28

Even though, in general, reg I q is asymptotically a linear function, for small values of q,
there are examples for which reg I q > reg I q+1 . We ask if this would not be the case for edge
ideals of graphs.
Question 7.12. Let G be a graph and let I = I(G) be its edge ideal. Is the function reg I q
increasing for all q ≥ 1?
In investigating the asymptotic linear function reg I q , it is also of interest to know the
smallest value q0 starting from which reg I q attains its linear form. In known cases where the
regularity of I(G)q can be computed explicitly for all q ≥ 1, we have q0 ≤ 2. Computational
experiments seem to suggest that this is indeed always the case.
Question 7.13. Let G be a graph and let q0 be the least integer such that reg I(G)q is a
linear function for all q ≥ q0 . Is it true that q0 ≤ 2?
A much weaker question, yet still very interesting, would be whether q0 ≤ reg I(G)? —
This question is still wide open! A significant step toward answering Question 7.13 is to give
a uniform bound for q0 (i.e., a bound that does not depend on G).
Problem 7.14. Find a number N (which may depend on n and m) such that for any graph
G over n vertices and m edges, we have q0 ≤ N .
References
[1] A. Alilooee and A. Banerjee, Powers of edge ideals of regularity three bipartite graphs. J. Commut.
Algebra 9 (2017), no. 4, 441-454.
[2] A. Alilooee, S. Beyarslan and S. Selvaraja, Regularity of powers of unicyclic graphs. Preprint (2017),
arXiv:1702.00916.
[3] A. Alilooee and S. Faridi, On the resolutions of path ideals of cycles, Communications in Algebra 43
(2015), no. 12, 5413-5433.
[4] A. Bagheri, M. Chardin and H.T. Hà, The eventual shape of Betti tables of powers of ideals. Math.
Res. Lett. 20 (2013), no. 6, 1033-1046.
[5] A. Banerjee, The regularity of powers of edge ideals. J. Algebraic Combin. 41 (2015), no. 2, 303-321.
[6] C. Berge, Hypergraphs: combinatorics of finite sets. North-Holland, New York, 1989.
[7] T. Biyikoglu and Y. Civan, Vertex decomposable graphs, codismantlability, Cohen-Macaulayness and
Castelnuovo-Mumford regularity. Electron. J. Combin. 21 (2014), no. 1, Paper 1.1, 17 pp.
[8] Anders Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam,
1995, pp. 1819-1872
[9] R. Bouchat, H. T. Hà and A. O’Keefe, Path ideals of rooted trees and their graded Betti numbers. J.
Combin. Theory Ser. A 118 (2011), 2411-2425.
[10] S. Beyarslan, H.T. Hà and T.N. Trung, Regularity of powers of forests and cycles. J. Algebraic
Combin. 42 (2015), no. 4, 1077-1095.
[11] A. Banerjee, Regularity of path ideals of gap free graphs, J. Pure and Applied Alg. 221 (2017), no.
10, 2409-2419.
[12] W. Bruns and J. Herzog, Cohen-Macaulay rings. Cambridge Studies in Advanced Mathematics, 39.
Cambridge University Press, Cambridge, 1993.
[13] G. Caviglia, H. T. Hà, J. Herzog, M. Kummini, N.Terai, N. V. Trung, Depth and regularity modulo
a principal ideal. Preprint (2017), arXiv:1706.09675.
[14] M. Chardin, Some results and questions on Castelnuovo-Mumford regularity. Syzygiez and Hilbert
functions. Lect. Notes Pure Appl. Math., 254, 1-40. Chapman & Hall/CRC, 2007.
[15] S.D. Cutkosky, J. Herzog, and N.V. Trung, Asymptotic behaviour of the Castelnuovo-Mumford regularity. Composito Mathematica 118 (1999), 243-261.
29

[16] K. Cameron and T. Walker, The graphs with maximum induced matching and maximum matching
the same size. Discrete Math. 299 (2005), 49-55.
[17] H. Dao, C. Huneke and J. Schweig, Bounds on the regularity and projective dimension of ideals
associated to graphs. J. Algebraic Combin. 38 (2013), no. 1, 37-55.
[18] J.A. Eagon and V. Reiner, Resolutions of Stanley-Reisner rings and Alexander duality, J. Pure and
Appl. Algebra 130 (1998), no. 3, 265-267.
[19] D. Eisenbud, Commutative Algebra: with a View Toward Algebraic Geometry. Springer-Verlag, New
York, 1995.
[20] D. Eisenbud and S. Goto, Linear free resolutions and minimal multiplicity. J. Algebra 88 (1984), no.
1, 89-133.
[21] N. Erey, Powers of edge ideals with linear resolutions. Preprint (2017), arXiv:1703.01561.
[22] S. Faridi, The facet ideal of a simplicial complex. Manuscripta Math. 109 (2002), no. 2, 159-174.
[23] O. Fernàndez-Ramos and P. Gimenez, Regularity 3 in edge ideals associated to bipartite graphs. J.
Algebraic Combin. 39 (2014), no. 4, 919-937.
[24] A. Frühbis-Krüger and N. Terai, Bounds for the regularity of monomial ideals. LE MATEMATICHE
LIII, Supplemento, pp. 83-97, 2007.
[25] R. Fröberg, On Stanley-Reisner rings. Topics in algebra, Part 2 (Warsaw, 1988), 57-70, Banach Center
Publ., 26, Part 2, PWN, Warsaw, 1990.
[26] C. A. Francisco and A. V. Tuyl, Sequentially Cohen-Macaulay edge ideals, Proc. Amer. Math. Soc.
135 (2007), no. 8, 23-37 (electronic).
[27] H.T. Hà, Regularity of squarefree monomial ideals. Connections between algebra, combinatorics, and
geometry, 251-276, Springer Proc. Math. Stat., 76, Springer, New York, 2014.
[28] H.T. Hà and A. Van Tuyl, Resolutions of square-free monomial ideals via facet ideals: a survey. Algebra, geometry and their interactions, 91-117, Contemp. Math., 448, Amer. Math. Soc., Providence,
RI, 2007.
[29] H. T. Hà and A. Van Tuyl, Monomial ideals, edge ideals of hypergraphs, and their minimal graded
free resolutions. J. Algebraic Combin. 27 (2008), no. 2, 215-245.
[30] H.T. Hà and R. Woodroofe, Results on the regularity of square-free monomial ideals. Adv. in Appl.
Math. 58 (2014), 21-36.
[31] J. Herzog, A generalization of the Taylor complex construction. Comm. Algebra 35 (2007), no. 5,
1747-1756.
[32] J. Herzog and T. Hibi, Monomial ideals. GTM 260, Springer-Verlag, 2011.
[33] J. Herzog, T. Hibi, X. Zheng, Monomial ideals whose powers have a linear resolution. Math. Scand.
95 (2004), no. 1, 23-32.
[34] T. Hibi, A. Higashitani, K. Kimura and A. B. O’Keefe, Algebraic study on Cameron-Walker graphs,
J. Algebra 422 (2015), 257-269.
[35] M. Hochster, Cohen-Macaulay rings, combinatorics, and simplicial complexes. Proc. of the 2nd Oklahoma Conf., Lecture Notes in Pure Appl. Math. 26 (1977) Marcel Dekker, 171-224.
[36] S. Jacques, Betti numbers of graph ideals. Ph.D. Thesis, University of Sheffield, 2004.
arXiv:/0410107.
[37] A.V. Jayanthan, N. Narayanan and S. Selvaraja, Regularity of powers of bipartite graphs. J. Algebraic
Combin. 47 (2018), no.1, 17-38
[38] A.V. Jayanthan, S. Selvaraja, Asymptotic behavior of Castelnuovo-Mumford regularity of edge ideals
of very well-covered graphs. Preprint (2017), arXiv:1708.06883.
[39] G. Kalai and R. Meshulam, Intersections of Leray complexes and regularity of monomial ideals. J.
Combin. Theory Ser. A 113 (2006), no. 7, 1586-1592.
[40] F. Khosh-Ahang and S. Moradi, Regularity and projective dimension of edge ideal of C5 -free vertex
decomposable graphs. Proc. Amer. Math. Soc. 142 (2014), no. 5, 1567-1576.
[41] M. Katzman, Characteristic-independence of Betti numbers of graph ideals. J. Combin. Theory Ser.
A 113 (2006), no. 3, 435-454.
[42] V. Kodiyalam, Asymptotic behaviour of Castelnuovo-Mumford regularity. Proceedings of the American Mathematical Society, 128 (1999), no. 2, 407-411.
30

[43] M. Kummini, Regularity, depth and arithmetic rank of bipartite edge ideals. J. Algebraic Combin.
30 (2009), no. 4, 429-445.
[44] K-N. Lin and J. McCullough, Hypergraphs and Regularity of Square-free Monomial Ideals, Int. J.
Algebra Comput. 23 (2013), 1573-1590.
[45] G. Lyubeznik, The minimal non-Cohen-Macaulay monomial ideals, J. Pure Appl. Algebra 51 (1988),
261-266.
[46] M. Mahmoudi, A. Mousivand, M. Crupi, G. Rinaldo, N. Terai, and S. Yassemi, Vertex decomposability and regularity of very well-covered graphs. J. Pure Appl. Algebra 215 (2011), no. 10,
2473-2480.
[47] E. Miller and B. Sturmfels, Combinatorial Commutative Algebra. GTM 227, Springer-Verlag, 2004.
[48] N.C. Minh and N.V. Trung, Cohen-Macaulayness of monomial ideals and symbolic powers of StanleyReisner ideals. Adv. Math. 226 (2011), 1285-1306.
[49] M. Moghimian, S.A. Seyed Fakhari, S. Yassemi, Regularity of powers of edge ideal of whiskered cycles.
Comm. Algebra 45 (2017), no. 3, 1246-1259.
[50] S. Morey, Depths of powers of the edge ideal of a tree. Comm. Algebra 38 (2010), no. 11, 4042-4055.
[51] S. Morey, R.H. Villarreal, Edge ideals: algebraic and combinatorial properties. Progress in commutative algebra 1, 85-126, de Gruyter, Berlin, 2012.
[52] E. Nevo, Regularity of edge ideals of C4 -free graphs via the topology of the lcm-lattice. J. Combin.
Theory Ser. A 118 (2011), 491-501.
[53] E. Nevo and I. Peeva, C4 -free edge ideals. J. Algebraic Combin. 37 (2013), no. 2, 243-248.
[54] P. Norouzi, S.A. Seyed Fakhari, S. Yassemi, Regularity of powers of edge ideals of very well-covered
graphs. Preprint (2017), arXiv:1707.04874.
[55] I. Peeva, Graded syzygies. Algebra and Applications, 14. Springer-Verlag London, Ltd., London,
2011.
[56] R. Stanley, Combinatorics and Commutative Algebra. Progress in Mathematics, 41. Birkhäuser
Boston, Inc., Boston, MA, 1983.
[57] S. Sullivant, Combinatorial symbolic powers. J. Algebra 319 (2008), no. 1, 115-142.
[58] Y. Takayama, Combinatorial characterizations of generalized Cohen-Macaulay monomial ideals, Bull.
Math. Soc. Sci. Math. Roumanie (N.S.) 48 (2005), 327-344.
[59] D. K. Taylor, Ideals generated by monomials in an R-sequence, ProQuest LLC, Ann Arbor, MI,
Thesis (Ph.D)-The University of Chicago, 1996
[60] N.V. Trung and H. Wang, On the asymptotic behavior of Castelnuovo-Mumford regularity. J. Pure
Appl. Algebra 201 (2005), no. 1-3, 42-48.
[61] R. H. Villarreal, Monomial algebras. Monographs and Textbooks in Pure and Applied Mathematics,
238. Marcel Dekker, Inc., New York, 2001.
[62] A. Van Tuyl, Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity.
Arch. Math. (Basel) 93 (2009), no. 5, 451-459.
[63] G. Wegner, d-collapsing and nerves of families of convex sets. Arch. Math. (Basel) 26 (1975), 317-321.
[64] R. Woodroofe, Matchings, coverings, and Castelnuovo-Mumford regularity. J. Commut. Algebra 6
(2014), no. 2, 287-304.
[65] Russ Woodroofe, Vertex decomposable graphs and obstructions to shellability. Proc. Amer. Math.
Soc., 137 (2009), no. 10, 3235-3246.
[66] X. Zheng, Resolutions of facet ideals, Comm. Algebra 32 (2004) 2301-2324.

31

Ramakrishna Mission Vivekenanda University, Belur, West Bengal, India
E-mail address: 123.arindam@gmail.com
URL: https://http://maths.rkmvu.ac.in/∼arindamb/
University of South Alabama, Department of Mathematics and Statistics, 411 University
Boulevard North, Mobile, AL 36688-0002, USA
E-mail address: selvi@southalabama.edu
URL: https://selvikara.wordpress.com/selvi/
Tulane University, Department of Mathematics, 6823 St. Charles Ave., New Orleans,
LA 70118, USA
E-mail address: tha@tulane.edu
URL: http://www.math.tulane.edu/∼tai/

32

