REGULARITY OF SQUAREFREE MONOMIAL IDEALS

arXiv:1310.7912v2 [] 4 Nov 2013

HUY TÀI HÀ
Abstract. We survey a number of recent studies of the Castelnuovo-Mumford regularity of squarefree monomial ideals. Our focus is on bounds and exact values for the
regularity in terms of combinatorial data from associated simplicial complexes and/or
hypergraphs.

Dedicated to Tony Geramita, a great teacher, colleague and friend.
1. Introduction
Castelnuovo-Mumford regularity (or simply regularity) is an important invariant in
commutative algebra and algebraic geometry that governs the computational complexity
of ideals, modules and sheaves. Computing or finding bounds for the regularity is a
difficult problem. Many simply stated questions and conjectures have been verified only
in very special cases. For instance, the Eisenbud-Goto conjecture, which states that the
regularity of a projective variety is bounded by the difference between its degree and
codimension, has been proved only for arithmetic Cohen-Macaulay varieties, curves and
surfaces.
The class of squarefree monomial ideals is a classical object in commutative algebra,
with strong connections to topology and combinatorics, which continues to inspire much of
current research. During the last few decades, advances in computer technology and speed
of computation have drawn many researchers’ attention toward problems and questions
involving this class of ideals. Investigating the regularity of squarefree monomial ideals
has evolved to be a highly active research topic in combinatorial commutative algebra.
In this paper, we survey a number of recent studies on the regularity of squarefree
monomial ideals. Even for this class of ideals, the list of results on regularity is too
large to exhaust. Our focus will be on studies that find bounds and/or compute the
regularity of squarefree monomial ideals in terms of combinatorial data from associated
simplicial complexes and hypergraphs. Our aim is to provide readers with an adequate
overall picture of the problems, results and techniques, and to demonstrate similarities
and differences between these studies. At the same time, we hope to motivate interested
researchers, and especially graduate students, to start working in this area. We shall
showcase results in a timeline to exhibit (if possible) trends in developing new and/or
more general results from previous ones.
The paper is structured as follows. In the next section we collect basic notation and
terminology from commutative algebra and combinatorics that will be used in the paper.
This section provides readers who are new to the research area the necessary background to
start. More advanced readers can skip this section and go directly to Section 3. In Section
1

2

HUY TÀI HÀ

3, we outline a number of inductive results that appear to be common techniques in many
recent works. Some of these results arise from simple short exact sequences in commutative
algebra, while others may require heavier topological machineries to prove. Section 4 is
devoted to studies that provide bounds for the regularity of squarefree monomial ideals. In
Section 5, we discuss studies that explicitly compute the regularity of squarefree monomial
ideals, and identify classes of ideals with small regularity. In these sections (Sections 3, 4
and 5), we do not generally prove results being surveyed. Rather, occasionally for initial
theorems of various inductive techniques we shall sketch the proofs to demonstrate the
methods used. The last section provides a number of open problems and questions that
we would like to see answered.
Acknowledgement. The author would like to thank an anonymous referee for a careful
reading and many helpful comments. The author would also like to thank S.A. Seyed
Fakhari for pointing out a mistake in our original definition of HE in Theorem 3.5.
2. Preliminaries
We begin by recalling familiar notation and terminology from commutative algebra and
combinatorics. We follow standard texts [3, 30, 39, 45] in these fields.
We shall investigate the connection between commutative algebra and combinatorics via
the notion of Stanley-Reisner ideals and edge ideals. To illustrate a general framework, we
will not include studies that are based on constructions that do not necessarily give oneto-one correspondences between squarefree monomial ideals and combinatorial structures;
for instance, path ideals of directed trees (cf. [7]).
Throughout the paper, K will denote any infinite field and R = K[x1 , . . . , xn ] will be
a polynomial ring over K. For obvious reasons, we shall identify the variables x1 , . . . , xn
with the vertices of simplicial complexes and hypergraphs being discussed. By abusing notation, we also often identify
Q a subset V of the vertices X = {x1 , . . . , xn } with
V
the squarefree monomial x = x∈V x in the polynomial ring R. In examples, we use
a, b, c, . . . as variables instead of the xi s.
2.1. Simplicial complexes. A simplicial complex ∆ over the vertex set X = {x1 , . . . , xn }
is a collection of subsets of X such that if F ∈ ∆ and G ⊆ F then G ∈ ∆. Elements
of ∆ are called faces. Maximal faces (with respect to inclusion) are called facets. For
F ∈ ∆, the dimension of F is defined to be dim F = |F | − 1. The dimension of ∆ is
dim ∆ = max{dim F | F ∈ ∆}. The complex is called pure if all of its facets are of the
same dimension.
Let ∆ be a simplicial complex and let Y ⊆ X be a subset of its vertices. The induced
subcomplex of ∆ on Y , denoted by ∆[Y ], is the simplicial complex with vertex set Y and
faces {F ∈ ∆ | F ⊆ Y }.
Definition 2.1. Let ∆ be a simplicial complex over the vertex set X, and let σ ∈ ∆.
(1) The deletion of σ in ∆, denoted by del∆ (σ), is the simplicial complex obtained by
removing σ and all faces containing σ from ∆.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

3

(2) The link of σ in ∆, denoted by link∆ (σ), is the simplicial complex whose faces are
{F ∈ ∆ | F ∩ σ = ∅, σ ∪ F ∈ ∆}.
Definition 2.2. A simplicial complex ∆ is recursively defined to be vertex decomposable
if either
(1) ∆ is a simplex; or
(2) 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 are called a shedding order of ∆.
Recall that a simplicial complex ∆ is said to be shellable if there exists
a linearorder
S
T
k−1
of its facets F1 , F2 , . . . , Ft such that for all k = 2, . . . , t, the subcomplex
Fk
i=1 Fi
is pure 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. For more details on Cohen-Macaulay rings and modules, we refer
the reader to [8]. The notion of Stanley-Reisner rings will be discussed later in the paper.
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.
a
e

c

d

b

Figure 1. A vertex decomposable simplicial complex.
Example 2.3. The simplicial complex ∆ in Figure 1 is a nonpure simplicial complex of
dimension 2. It has 3 facets; the facet {a, b, c} is of dimension 2, the facet {c, d} is of
dimension 1, and the facet {e} is of dimension 0. The complex ∆ is vertex decomposable
with {e, d} as a shedding order.
2.2. Hypergraphs. A hypergraph H = (X, E) over the vertex set X = {x1 , . . . , xn }
consists of X and a collection E of nonempty subsets of X; these subsets are called the
edges of H. A hypergraph H is simple if there is no nontrivial containment between any
pair of its edges. Simple hypergraphs are also referred to as clutters or Sperner systems.
All hypergraphs considered in this paper will be simple.

4

HUY TÀI HÀ

When working with a hypergraph H, we shall use X(H) and E(H) to denote its vertex
and edge sets, respectively. We shall denote by is(H) the set of (isolated ) vertices that
do not belong to any edge in H, and let H red be the hypergraph obtained by removing
vertices in is(H) from the vertex set of H. An edge {v} consisting of a single vertex is
often referred to as an isolated loop (this is not to be confused with an isolated vertex).
Let Y ⊆ X be a subset of the vertices in H. The induced subhypergraph of H on Y ,
denoted by H[Y ], is the hypergraph with vertex set Y and edge set {E ∈ E | E ⊆ Y }.
The contraction of H to Y is the hypergraph with vertex set Y and edges being minimal
nonempty elements of {E ∩ Y | E ∈ E}.
Definition 2.4. Let H be a simple hypergraph.
(1) A collection C of edges in H is called a matching if the edges in C are pairwise
disjoint. The maximum size of a matching in H is called its matching number.
(2) A collection C of edges in H is called an induced matching if C is a matching,
and C consists of all edges of the induced subhypergraph H[∪E∈C E] of H. The
maximum size of an induced matching in H is called its induced matching number.
Example 2.5. Figure 1 can be viewed as a hypergraph over the vertex set {a, b, c, d, e}
with edges {a, b, c}, {c, d} and {e}. The collection {{a, b, c}, {e}} forms an induced matching in this hypergraph.
A graph is a hypergraph in which all edges are of cardinality 2. The complement of a
graph G, denoted by Gc , is the graph with the same vertex set and an edge E is in Gc if
and only if E is not in G.
Definition 2.6. A graph G is called chordal if it has no induced cycles of length ≥ 4.
A hypergraph H is d-uniform if all its edges have cardinality d. For an edge E in H,
let N (E) = {x ∈ X | ∃F ⊆ E s.t. F ∪ {x} ∈ E} be the set of neighbors of E, and let
N [E] = N (E) ∪ E.
Definition 2.7. Let H = (X, E) be a simple hypergraph. Let E be an edge and let Y be
a subset of the vertices in H.
(1) Define H \ E to be the hypergraph obtained by deleting E from the edge set of
H. This is often referred to as the deletion of E from H.
(2) Define H \ Y to be the hypergraph obtained from H by deleting the vertices in Y
and all edges containing any of those vertices.
(3) Define HE to be the contraction of H \ N (E) to X \ N [E].
Note that when H is a graph and E is an edge, then HE is just the induced subgraph
of H over the vertex set X \ N [E].
Definition 2.8. Let H = (X, E) be a simple hypergraph.
(1) A collection of vertices V in H is called an independent set if there is no edge
E ∈ E such that E ⊆ V .
(2) The independence complex of H, denoted by ∆(H) is the simplicial complex whose
faces are independent sets in H.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

5

Example 2.9. The simplicial complex ∆ in Figure 1 is the independence complex of the
graph in Figure 2.
d

b

a

e

c

Figure 2. A simple graph whose independence complex is in Figure 1.
Remark 2.10. We call a hypergraph H vertex decomposable (shellable, sequentially
Cohen-Macaulay) if its independence complex ∆(H) is vertex decomposable (shellable,
sequentially Cohen-Macaulay).
2.3. Stanley-Reisner ideals and edge ideals. The Stanley-Reisner ideal and edge
ideal constructions are well-studied correspondences between commutative algebra and
combinatorics. Those constructions arise by identifying minimal generators of a squarefree
monomial ideal with the minimal nonfaces of a simplicial complex or the edges of a simple
hypergraph.
Stanley-Reisner ideals were developed in the early 1980s (cf. [45]) and has led to many
important homological results (cf. [8, 44]).
Definition 2.11. Let ∆ be a simplicial complex on X. The Stanley-Reisner ideal of ∆
is defined to be

I∆ = xF | F ⊆ X is not a face of ∆ .
Example 2.12. Let ∆ be the simplicial complex in Figure 1 and let R = K[a, b, c, d, e].
Then the minimal nonfaces of ∆ are {a, d}, {a, e}, {b, d}, {b, e}, {c, e} and {d, e}. Thus,
I∆ = (ad, ae, bd, be, ce, de).
Example 2.13. The simplicial complex ∆ in Figure 3 represents a minimal triangulation
of the real projective plane. Its Stanley-Reisner ideal is
I∆ = (abc, abe, acf, ade, adf, bcd, bdf, bef, cde, cef ).
The edge ideal construction was introduced in [49] for graphs and later generalized to
hypergraphs in [27]. This construction is similar to that of facet ideals in [20].
Definition 2.14. Let H be a simple hypergraph on X. The edge ideal of H is defined to
be

I(H) = xE | E ⊆ X is an edge in H .

6

HUY TÀI HÀ
a

b

d

e
c

c

f

b

a

Figure 3. A minimal triangulation of the real projective plane.
The notion of Stanley-Reisner ideal and edge ideal give the following one-to-one correspondences that allow us to pass back and forth from squarefree monomial ideals to
simplicial complexes and simple hypergraphs.


simplicial complexes
over X




←→

squarefree monomial
ideals in R




←→

simple hypergraphs
over X



Stanley-Reisner ideals and edge ideals are also closely connected via the notion of
independence complex.
Lemma 2.15. Let H be a simple hypergraph and let ∆ = ∆(H) be its independence
complex. Then
I∆ = I(H).
Example 2.16. The edge ideal of the graph G in Figure 2 is the same as the StanleyReisner ideal of its independence complex, the simplicial complex in Figure 1.
2.4. Alexander duality. The Alexander duality theory for simplicial complexes carries
nicely over to squarefree monomial ideals and have proved to be a significant tool in the
study of these ideals.
Definition 2.17. Let ∆ be a simplicial complex over the vertex set X. The Alexander
dual of ∆, denoted by ∆∨ , is the simplicial complex over X with faces
{X \ F | F 6∈ ∆}.
Notice that ∆∨∨ = ∆. If I = I∆ then we shall denote by I ∨ the Stanley-Reisner ideal
of the Alexander dual ∆∨ . Also, if I = I(H) then we shall denote by H ∨ the simple
hypergraph corresponding to I ∨ .
It is a celebrated result of Terai [46] that the regularity of a squarefree monomial ideal
can be related to the projective dimension of its Alexander dual.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

7

Theorem 2.18. Let I ⊆ R be a squarefree monomial ideal. Then
reg(I) = pd(R/I ∨ ).
Theorem 2.18 basically says that studying the regularity of squarefree monomial ideals
is equivalent to studying the projective dimension of squarefree monomial ideals. Many
studies in commutative algebra take the later point of view.
2.5. Castelnuovo-Mumford regularity. The regularity of graded modules over the
polynomial ring R can be defined in various ways. Let m denote the maximal homogeneous
ideal in R.
Definition 2.19. Let M be a finitely generated graded R-module. For i ≥ 0, let
(
n
o
 i

max
l
∈
Z
H
(M
)
=
6
0
if Hmi (M ) 6= 0
m
l
ai (M ) =
−∞
otherwise.
The regularity of M is defined to be
reg(M ) = max{ai (M )}.
i≥0

Note that ai (M ) = 0 for i > dim M , so the regularity of M is well-defined. This
invariant can also be computed via the minimal free resolution (cf. [9, 16]).
Definition 2.20. Let M be a graded R-module and let
M
M
R(−j)β0j (M ) → M → 0
R(−j)βpj (M ) → · · · →
0→
j∈Z

j∈Z

be its minimal free resolution. Then the regularity of M is given by
reg(M ) = max{j − i | βij (M ) 6= 0}.
By looking at the minimal free resolution, it is easy to see that reg(R/I) = reg(I) − 1,
so we shall work with reg(I) and reg(R/I) interchangeably.
The focus of this paper is on squarefree monomial ideals. As we have seen, squarefree
monomial ideals are in direct one-to-one correspondence with simplicial complexes, and
the regularity of these ideals can also be computed from the reduced homology groups
of corresponding simplicial complexes. We summarize this connection in the following
lemma.
Lemma 2.21. For a simplicial complex ∆, the following are equivalent:
(1) reg(R/I∆ ) ≥ d.
(2) H̃d−1 (∆[S]) 6= 0, where ∆[S] denotes the induced subcomplex on some subset S of
vertices.
(3) H̃d−1 (link∆ σ) 6= 0 for some face σ of ∆.
Proof. The equivalence of (1) and (2) follows directly from Definition 2.20, together with
Hochster’s formula for graded Betti numbers (as stated in [39, Corollary 5.12]). The
equivalence of (1) and (3) follows directly from the local cohomology characterization of

8

HUY TÀI HÀ

regularity, together with the fact that Hmi (R/I∆ )−σ ∼
= H̃ i−|σ|−1 (link∆ σ) (see [39, Chapter
13.2]).

Remark 2.22. For simplicity, if I = I∆ then we sometimes write reg(∆) for reg(I), and
if I = I(H) then we write reg(H) for reg(I).
3. Regularity and induction
The backbone of most of the studies that we survey is mathematical induction based on
combinatorial structures of given simplicial complexes and hypergraphs. The technique
is to relate the regularity of a squarefree monomial ideal corresponding to a simplicial
complex and/or hypergraph to that of smaller sub-ideals corresponding to subcomplexes
and/or subhypergraphs. In this section, we discuss a number of inductive results that
lie in the core of most of these studies. It is worth noting that there are also inductive
results that go from smaller simplicial complexes and/or hypergraphs to larger ones; for
instance, in the work of [6, 41]. Since we eventually are interested in bounds or values for
the regularity, those works are beyond the scope of our survey.
We start the section by a few crude inductive bounds for the regularity of a hypergraph
(or simplicial complex) in terms of that of subhypergraphs (or subcomplexes), that follow
directly from Lemma 2.21.
Lemma 3.1.
(1) Let H be a simple hypergraph. Then reg(H) ≥ reg(H 0 ) for any induced subhypergraph H 0 of H.
(2) Let ∆ be a simplicial complex. Then reg(∆) ≥ reg(link∆ (σ)) for any face σ of ∆.
For any homogeneous ideal I ⊆ R and any homogeneous element h ∈ R of degree d,
the following short exact sequence is standard in commutative algebra:
R
R
×h R
0 −→
(3.1)
(−d) −→
−→
−→ 0.
I:h
I
I +h
By taking the long exact sequence of local cohomology modules associated to (3.1), we
get
(3.2)

reg(I) ≤ max{reg(I : h) + d, reg(I, h)}.

Remark 3.2. If h is an indeterminate of R appearing in I, then it was shown in [15,
Lemma 2.10] that, in fact, reg(I) is always equal to either reg(I : h) + 1 or reg(I, h).
In practice, induction usually starts by deleting a vertex or a face (edge). That is, h
is often taken to be the variable corresponding to a vertex or the product of variables
corresponding to a face (edge) of the simplicial complex (hypergraph).
Remark 3.3. Let I = I∆ be the Stanley-Reisner ideal of a simplicial complex ∆, and let
h = xσ for a face σ of dimension d − 1 in ∆. Then I : h = Ilink∆ (σ) and I + h = Idel∆ (σ) + h.
For a subset V of the vertices in a hypergraph H, let H : V and H + V denote the
hypergraphs corresponding to the squarefree monomial ideals I(H) : xV and I(H) + xV ,
respectively. As a consequence of (3.2), we have the following inductive bounds.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

9

Theorem 3.4.
(1) Let ∆ be a simplicial complex and let σ be a face of dimension d − 1 in ∆. Then
reg(∆) ≤ max{reg(link∆ (σ)) + d, reg(del∆ (σ))}.
(2) Let H be a simple hypergraph and let V be a collection of d vertices in H. Then
reg(H) ≤ max{reg(H : V ) + d, reg(H + V )}.
Another basic exact sequence in commutative algebra is:
R
R R
R
0 −→
−→ ⊕ −→
−→ 0.
I ∩J
I
J
I +J
Let E be an edge of a simple hypergraph H. By taking I = I(H \ E) and J = (xE ), this
sequence gives
R
R
R
R
0 −→ E
−→ E ⊕
−→
−→ 0.
(x ) ∩ I(H \ E)
(x ) I(H \ E)
I(H)
Taking the associated long exact sequence of cohomology modules again, we get

(3.3)
reg(H) ≤ max{|E|, reg(H \ E), reg (xE ) ∩ I(H \ E) − 1}.
Recall that HE is the contraction of H \ N (E) to the vertices X \ N [E]. It is easy to
see that (xE ) ∩ I(H \ E) = xE (y | y ∈ N (E)) + I(HE ). Also, since the variables in N [E]
do not appear in HE , by taking the tensor product of minimal free resolutions, we get

reg (xE ) ∩ I(H \ E) = reg(I(HE )) + |E|.
Thus, (3.3) gives the following inductive bound.
Theorem 3.5. Let H be a simple hypergraph and let E be an edge of cardinality d in H.
Then
reg(H) ≤ max{d, reg(H \ E), reg(HE ) + d − 1}.
Induction also works even when we do not necessarily split the edges of H into disjoint
subsets. Kalai and Meshulam [32] obtain the following powerful result. This result was
later extended to arbitrary (not necessarily squarefree) monomial ideals by Herzog [29].
Theorem 3.6. Let I1 , . . . , Is be squarefree monomial ideals in R. Then
!
s
s
.X
X
reg R
Ii ≤
reg(R/Ii ).
i=1

i=1

In particular, for edge ideals of a hypergraph and subhypergraphs, we have the following
inductive bound.
Corollary 3.7. Let
SsH and H1 , . . . , Hs be simple hypergraphs over the same vertex set X
such that E(H) = i=1 E(Hi ). Then
reg(R/I(H)) ≤

s
X
i=1

reg(R/I(Hi )).

10

HUY TÀI HÀ

4. Combinatorial bounds for regularity
In this section, we examine various bounds for the regularity of a squarefree monomial
ideal in terms of combinatorial data from associated simplicial complex and hypergraph.
These bounds can be proved using inductive results from Section 3. There are also works in
the literature that relate the regularity of (squarefree) monomial ideals to other algebraic
invariants (cf. [1, 11, 23, 31]). These works are beyond the scope of this survey.
For edge ideals of graphs, it turns out that the matching number and induced matching
number provide nice upper and lower bounds for the regularity. The following result is
due to Katzman [33, Lemma 2.2].
Theorem 4.1. Let G be a simple graph and let ν(G) be the maximum size of an induced
matching in G. Then
reg(I(G)) ≥ ν(G) + 1.
This result is generalized in [27, Theorem 6.5] for properly connected hypergraph, and
extended for all simple hypergraph in [42, Corollary 3.9]. In fact, the result is a direct
consequence of the inductive bound in Lemma 3.1.
Theorem 4.2. Let H be a simple hypergraph. Suppose that {E1 , . . . , Es } forms an induced
matching in H. Then
s
X
reg(H) ≥
(|Ei | − 1) + 1.
i=1

S
Proof. Let H 0 be the induced subhypergraph of H on the vertex set si=1 Ei . Since
{E1 , . . . , Es } forms an induced matching in H, these are the only edges in H 0 . Thus,
s
X
reg(H ) =
(|Ei | − 1) + 1.
0

i=1

Moreover, by Lemma 3.1, reg(H) ≥ reg(H 0 ). The result now follows.



Remark 4.3. It is clear that if H consists of disjoint edges then the bound in Theorem
4.2 becomes an equality. On the other hand, as we shall see later in Example 4.11, the
regularity of a hypergraph can be arbitrarily larger than the right hand side of the bound
in Theorem 4.2.
Lower bounds and upper bounds are more interesting when they go together. A natural
invariant related to the induced matching number is the (minimax ) matching number.
The following result was proved in [27, Theorem 6.7] and [51, Theorem 11].
Theorem 4.4. Let G be a simple graph. Let β(G) be the minimum size of a maximal
matching G. Then
reg(G) ≤ β(G) + 1.
We can also recover the proof of Theorem 4.4 as a direct consequence of an inductive
bound, Corollary 3.7. For that we first need a simple lemma.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

11

Lemma 4.5. Let G be a simple graph and assume that an edge {u, v} forms a maximal
matching of size 1 in G. Then
reg(R/I(G)) = 1.
Proof. Since reg(R/I(G)) = reg(I(G)) − 1, it suffices to show that reg(I(G)) = 2. The
assertion is trivial if G consists of exactly one edge {u, v}. We can then induct on the
number of edges in G, making use of Theorem 3.4.

of Theorem 4.4. Let β = β(G) and let {E1 , . . . , Eβ } be a maximal matching in G. For
each Ei , let Gi be the subgraph of G consisting of Ei and all edges
Sβincident to its vertices.
Since {E1 , . . . , Eβ } forms a maximal matching in G, we have i=1 E(Gi ) = E(G). The
result now follows from Corollary 3.7 and Lemma 4.5.

Remark 4.6. If G consists of disjoint edges, then the bound in Theorem 4.4 becomes an
equality. On the other hand, by taking G to be the complement of a chordal graph (in
which case, reg(I(G)) = 2), one can make β(G) + 1 arbitrarily larger than reg(I(G)).
A number of generalizations for Theorem 4.4 has been developed. Woodroofe [51] was
the first to observe that giving a matching in a graph G is a simple way to “cover” the
edges of G by subgraphs. One can also consider giving a matching in G as a special way
to “pack” edges in G. These ideas have been extended to give better bounds for graphs
and to obtain bounds for hypergraphs in general.
Let c(G) denote the minimum number of subgraphs in G whose complements are chordal
such that every edge in G belong to at least one of those subgraphs. Woodroofe [51,
Lemma 1] extends Theorem 4.4 to give the following bound.
Theorem 4.7. Let G be a simple graph. Then
reg(G) ≤ c(G) + 1.
Moradi and Kiani [40, Theorem 2.1] improve the bound in Theorem 4.4 for the class of
vertex decomposable graphs. Define γ(G) to be the maximum number of vertex disjoint
paths of length at most 2 in G such that paths of length 1 form an induced matching.
Theorem 4.8. Let G be a vertex decomposable graph. Then
reg(G) ≤ γ(G) + 1.
The author and Woodroofe [28] extend this result to any graph making use of packing
of stars in a graph. A star consists a vertex x as its center and edges xyi s incident to x
(the vertices yi s are referred to as the outer vertices of the star). A star is nondegenerate
if there are at least 2 edges incident to its center. A collection P of stars in G is called
center-separated if for any pair of stars S1 and S2 in P , at least 2 outer vertices and the
center of S1 are not contained in S2 (and vice-versa). For a center-separated collection
of nondegenerate stars P , let ζP denote the number of stars in P plus the size of the
remaining induced matching after deleting the vertices of P from G. Let ζ(G) be the
maximum value of ζP over all center-separated collection of nondegenerate stars P . It is
not hard to see that ζ(G) ≤ γ(G).

12

HUY TÀI HÀ

Theorem 4.9. Let G be a simple graph. Then
reg(G) ≤ ζ(G) + 1.
Example 4.10. Let G be the graph in Figure 2. It is easy to see that ζ(G) = 1. For
instance, the nondegenerate star centered at b gives a maximal center-separated packing
of stars in G, whose removal results in a subgraph of isolated vertices {a, c}. The bound
in Theorem 4.9 gives reg(I(G)) ≤ 2. In fact, we have the equality for this example.
For hypergraphs the problem becomes more subtle. In particular, using the matching
number to bound the regularity as in Theorem 4.4 is no longer possible.

y2

z2
y3

z1

y1

x

z3

Figure 4. A 3-uniform hypergraph with regularity greater than (3 − 1) · β.
Example 4.11. For s > 1, consider the hypergraph Hs with edges {x, yi , zi } (for i =
1, . . . , s) on the vertex set {x, y1 , . . . , ys , z1 , . . . , zs }. Figure 4 illustrates H3 . We have that
the induced matching number and minimax matching number of Hs are both 1. On the
other hand, it is straightforward to compute that reg(I(Hs )) = s + 2, which can be taken
to be arbitrarily far from (3 − 1)β(Hs ) = 2.
A generalization of Theorem 4.4 is obtained in [28, Theorem 1.2] replacing the notion
of a matching by a 2-collage.
Definition 4.12. Let H be a simple hypergraph. A subset C of the edges in H is called
a 2-collage if for each edge E in H, there exists a vertex v ∈ E such that E \ {v} is
contained in some edge of C. For a uniform hypergraph, this condition is equivalent to
requiring that for any edge E in H there is an edge F in C such that the symmetric
difference of E and F has cardinality exactly 2.
Theorem 4.13. Let H be a simple hypergraph, and let {E1 , . . . , Es } be a 2-collage in H.
Then
s
X
reg(H) ≤
(|Ei | − 1) + 1.
i=1

Instead of packing a 2-collage in a hypergraph, the concept of edgewise domination was
introduced by Dao and Schweig [13], as a covering invariant, to generalize Theorem 4.4.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

13

Definition 4.14. A collection C of edges in a hypergraph H is called edgewise dominant
if every vertex x ∈ H red not contained in some edge of C or contained in an isolated loop
has a neighbor contained in some edge of C. Define
(H) = min{|C| C is edgewise dominant}.
Theorem 4.15. For any simple hypergraph H, we have
reg(H) ≤ |X(H)| − (H ∨ ).
To prove Theorem 4.15, the inductive method of Theorem 3.4 was put in a more general
perspective by considering a hereditary family of hypergraphs that allows one to go from
a given hypergraph H to the deletion and contraction of H at a vertex.
Definition 4.16. Let Φ be a collection of simple hypergraphs. We say that Φ is hereditary
if for any hypergraph H ∈ Φ and any subset V of the vertices of H, H red , H + V and
H : V are all in Φ.
The proof of Theorem 4.15 is based on the following more general version of Theorem
3.4 (see [13, Lemma 3.3]).
Theorem 4.17. Let Φ be a hereditary family of simple hypergraphs, and let f : Φ → N
be a function such that f (H red ) = f (H) for all H ∈ Φ, f (H) ≤ |X(H)| when H contains
no edges, and f (H) = 0 when H has only isolated loops. Furthermore, suppose that f
satisfies the following condition: for any H ∈ Φ with at least one edge of cardinality ≥ 2,
there exists a sequence of subsets P
A1 , . . . , At of the vertices such that, writing Hi for the
hypergraph corresponding to H + ij=1 Aj , the following two properties are satisfied.
• |is(Ht )| > 0 and f (Ht ) + |is(Ht )| ≥ f (H), and
• for each i, f (Hi−1 : Ai ) + |is(Hi−1 )| + |Ai | ≥ f (C).
Then for any H ∈ Φ, we have
reg(H ∨ ) = pd(H) ≤ |X(H red )| − f (H).
This technique, restricted to graphs [15], gives the following numerical bound for the
regularity (see [15, Theorem 4.1]).
Theorem 4.18. Let G be a graph. Assume that the resolution of I(G) is linear up to the
k-th step for some k ≥ 1, and let d be the maximum degree of a vertex in G. Then


d
reg(G) ≤ log k+4
+ 3.
2
k+1
Remark 4.19. It is not clear how strong the bound in Theorem 4.18 is in comparison to
other known bounds using packing and covering invariants.
Lin and McCullough, in [37], introduced the notion of labeled hypergraphs that, in
complement to the well-studied constructions of Stanley-Reisner ideals and edge ideals,
also gives a one-to-one correspondence to squarefree monomial ideals, and used this notion
to study the regularity of squarefree monomial ideals. Note that the unlabeled version
of their construction coincides with the dual hypergraph notion in hypergraph theory (cf.

14

HUY TÀI HÀ

[3]). In the same spirit of employing induction, Lin and McCullough [37, Theorem 4.9]
obtain the following bound. We shall rephrase their result in terms of edge ideals of
hypergraphs.
An edge E of a simple hypergraph H is said to contain a free vertex if there exists
x ∈ E such that x does not belong to any other edge in H.
Theorem 4.20. Let H = (X, E) be a simple hypergraph, and let H 0 = (X, E 0 ) be the
hypergraph obtained by removing all edges with free vertices from H. Let β(H 0 ) be the
matching number of H 0 . Then
reg(H) ≤ |X| − |E| + |E 0 | − β(H 0 ) + 1.
d

a

c

f

g

b

e

Figure 5. Comparing bounds in Theorems 4.13, 4.15 and 4.20.
Remark 4.21. It is not quite clear which bounds among Theorems 4.13, 4.15 and 4.20
are best in general. The following examples were given in [37] to illustrate this.
Example 4.22. Let I = (abc, def, adg, beg) be the edge ideal of the hypergraph in Figure
5. Then the bounds for reg(I) in Theorems 4.13 and 4.15, respectively, are 9 and 6. On
the other hand, the bound for reg(I) in Theorem 4.20 is 5.
a

d

b

c

Figure 6. Comparing bounds in Theorems 4.13, 4.15 and 4.20.
Example 4.23. Let I = (abc, abd, acd, bcd) be the edge ideal of the hypergraph in Figure
6. Then the bounds for reg(I) in Theorems 4.13 and 4.15 are both 3, while the bound
using labeled hypergraph in Theorem 4.20 is 4.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

15

5. Small regularity and computing regularity
In this section we survey studies that explicitly compute the regularity for special classes
of squarefree monomial ideals, and identify combinatorial structures that force the ideals
to have small regularity. Ideals of regularity 0 are trivial. A squarefree monomial ideal
has regularity 1 if and only if it is generated by a collection of variables. Thus, we shall
only consider ideals with regularity at least 2.
The following result was originally stated and proved by Wegner [50] using topological
language, and re-stated in terms of monomial ideals by Fröberg [22] (see also [17, 26]). It
is in fact a direct consequence of Lemma 2.21.
Theorem 5.1. Let G be a simple graph. Then reg(I(G)) = 2 if and only if Gc is a
chordal graph.
Proof. We briefly sketch out the proof. Let ∆ be the independence complex of G. By
Lemma 2.21, reg(R/I(G)) = 1 iff no induced subcomplex of ∆ has any balls of positive
dimension. This is the case iff the 1-skeleton of ∆ has no induced cycle of length ≥ 4.
Note that the 1-skeleton of ∆ is exactly the complement of G. In fact, an induced cycle
of length ≥ 4 in Gc gives a homology cycle in ∆.

It is then natural to investigate squarefree monomial ideals with regularity 3. To the
best of our knowledge, it is still an open question to characterize these ideals; though
partial results have been obtained.
Let P be a given collection of graphs. A graph G is said to be P -free if it contains no
induced subgraphs that are the same as elements in P . In particular, a graph G is called
claw-free if it contains no 4 vertices on which the induced subgraph is a star, and a graph
G is C4 -free if it contains no induced 4-cycles. The following result was proved in [43,
Theorem 1.2] (see also [15, Theorem 3.4]).
Theorem 5.2. Let G be a claw-free simple graph such that Gc contains no C4 . Then
reg(I(G)) ≤ 3.
Example 5.3. A 5-cycle is a claw-free graph whose complement contains no C4 , and
reg(I(C5 )) = 3.
For bipartite graphs, the edge ideals having regularity 3 can be characterized. Recall
that a graph G is bipartite if the vertices X(G) can be partitioned into disjoint subsets
X(G) = Y ∪Z such that edges of G connect a vertex in Y and a vertex in Z. The bipartite
complement of a bipartite graph G, denoted by Gbc , is the bipartite graph over the same
partition of the vertices, and for y ∈ Y, z ∈ Z, {y, z} ∈ Gbc if and only if {y, z} 6∈ G. The
following classification was given in [21, Theorem 3.1].
Theorem 5.4. Let G be a connected bipartite graph. Then reg(G) = 3 if and only if Gc
has induced cycles (of length ≥ 4) and Gbc has no induced cycles of length ≥ 6.
Let us now turn to classes of ideals for which the regularity can be computed explicitly.
In most of the studies that we survey, this is the case when inductive inequalities in Section

16

HUY TÀI HÀ

3 become equalities, and the method is to find combinatorial invariants that behaves well
with respect to the induction processes.
The following result was first proved for forests in [52, Theorem 2.18] and [26, Corollary
3.11], and extended to chordal graphs in [27, Theorem 6.8].
Theorem 5.5. Let G be a chordal graph and let ν(G) be the maximum size of an induced
matching in G. Then
reg(G) = ν(G) + 1.
To prove Theorem 5.5, we shall need a lemma (see [27, Lemma 5.7 and Theorem
6.2]) which states that for chordal graphs, one can always find an edge E such that the
inductive inequality of Theorem 3.5 becomes an equality, and that this process can be
done recursively.
Lemma 5.6. Let G be a chordal graph. Then there exists an edge E in G such that
(1) reg(G) = max{reg(GE ) + 1, reg(G \ E)}.
(2) G \ E and GE are both chordal graphs.
of Theorem 5.5. We use induction on the number of edges in G. If G consists of only
isolated vertices or a single edge then the assertion is trivial. For the induction step, in
light of Lemma 5.6 it suffices to show that for an edge E in G satisfying the conclusion
of Lemma 5.6, we have
ν(G) = max{ν(GE ) + 1, ν(G \ E)}.
This is indeed true. It is easy to see that an induced matching in G \ E is also an induced
matching in G, and an induced matching in GE together with E would form an induced
matching in G. Thus, ν(G) ≥ max{ν(GE ) + 1, ν(G \ E)}. On the other hand, suppose
that C = {E1 , . . . , Ec } is an induced matching in G of maximum size. If E 6∈ C then C
is an induced matching in G \ E. If E ∈ C, then C \ {E} forms an induced matching in
GE . Therefore, ν(G) ≤ max{ν(GE ) + 1, ν(G \ E)}.

b

c

a

d

f

e

Figure 7. A chordal graph.
Example 5.7. Let G be the chordal graph in Figure 7 and let I = I(G). Then
0 → R(−5)2 ⊕ R(−6) → R(−4)10 ⊕ R(−5)2 → R(−3)16 ⊕ R(−4) → R(−2)9 → I → 0
is the minimal free resolution of I giving reg(I) = 3. On the other hand, it is easy to see
that ν(G) = 2 and {ab, cd} is a maximal induced matching.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

17

Recall that a collection of vertices V in a graph G is called a vertex cover if for any
edge E in G, V ∩ E 6= ∅. A minimal vertex cover is with respect to inclusion. Note that
the smallest size of a vertex cover in G is equal to the height of I(G). A graph G is called
unmixed if all minimal vertex cover of G has the same cardinality. For an unmixed graph
G, it is known (cf. [24]) that 2 ht I(G) ≥ |X(G)|. A graph G is called very well-covered
(see [38]) if G is unmixed, has no isolated vertices, and 2 ht I(G) = |X(G)|.
Theorem 5.5 has been extended to a number of classes of graphs. In particular, for
the following classes of graph, the regularity can be computed by its induced matching
number.
Theorem 5.8. Let G be a simple graph. Let ν(G) be the maximum size of an induced
matching in G. Then
reg(G) = ν(G) + 1
in the following cases:
(1)
(2)
(3)
(4)

G is a sequentially Cohen-Macaulay bipartite graph (see [48]);
G is an unmixed bipartite graph (see [36]);
G is a very well-covered graph (see [38]);
G is a C5 -free vertex decomposable graph (see [34], the case where G is also C4 -free
was proved in [5]).

Remark 5.9. Chordal and sequentially Cohen-Macaulay bipartite graphs are vertex decomposable. Also, bipartite graphs are C5 -free. Therefore, in Theorem 5.8, 1. follows
from 4.
Example 5.10. Let G be the induced 5-cycle. Then G is not C5 -free nor very wellcovered. Its independence complex is also an induced 5-cycle, which is vertex decomposable. Thus, the class of vertex decomposable graphs is not fully covered by Theorem
5.8.
Moreover, the minimal free resolution of I = I(G) is given by
0 → R(−5) → R(−3)5 → R(−2)5 → I → 0.
Therefore, reg(I) = 3. On the other hand, the induced matching number of G is ν(G) = 1.
Observe that reg(I(G)) 6= ν(G) + 1 in this example.
The problem is again more subtle when moving to hypergraphs. To do so, we need to
identify classes of hypergraphs where inductive inequalities in Section 3 become equalities,
and to find combinatorial invariants of hypergraphs that respect induction processes.
It is proved by the author and Woodroofe in [28, Theorem 1.5] that the inductive
inequalities of Theorem 3.4 are equalities for all vertex decomposable simplicial complexes
and hypergraphs.
Theorem 5.11. Let H be a simple hypergraph with edge ideal I = I(H). Suppose that H
is vertex decomposable and x is the initial vertex in its shedding order. Then
reg(I) = max{reg(I : x) + 1, reg(I, x)}.
The following example arises from communication with Chris Francisco. The author
would like to thank Chris Francisco for his help.

18

HUY TÀI HÀ

Example 5.12. Let I = (acd, bcd, abe, bce, bcf, cdf ) ⊆ R = K[a, . . . , f ]. Then reg(I) = 3,
reg(I, a) = 3 = reg(I) and reg(I : a) + 1 = 4 > reg(I). Thus, in this example, reg(I) is
equal to the smaller value between reg(I, a) and reg(I : a) + 1.
Example 5.10 shows that even for vertex decomposable graphs, the induced matching
number is no longer the right invariant to compute the regularity (i.e., the regularity may
be strictly bigger than the induced matching number). On the other hand, for a smaller
class of vertex decomposable hypergraphs, those that are triangulated, it was proved in
[27] that this invariant still works.
Triangulated hypergraphs were introduced in [27] as a generalization of chordal graphs.
Recall that the distance between 2 edges E and F in a d-uniform hypergraph H is the
minimum length of a sequence of edges E0 = E, E1 , . . . , Es = F such that |Ei−1 ∩ Ei | =
d − 1. A d-uniform hypergraph H is called properly connected if for any intersecting edges
E and F , the distance between E and F is exactly d − |E ∩ F |. Note that all simple graph
are properly connected. Recall also that for a vertex x, the set of neighbors of x is given
by
N (x) = {y ∈ X | ∃E ∈ E s.t. {x, y} ⊆ E}.
Definition 5.13. A d-uniform properly connected hypergraph H = (X, E) is said to be
triangulated if for every nonempty subset Y ⊆ X, the induced subgraph H[Y ] contains
a vertex x ∈ Y ⊆ X such that the induced hypergraph of H[Y ] on N (x) is a complete
hypergraph consisting of all subsets of d elements of N (x).
Note that triangulated hypergraphs are vertex decomposable. The following theorem
was proved in [27, Theorem 6.8].
Theorem 5.14. Let H be a d-uniform properly connected hypergraph, and assume that
H is triangulated. Let ν(H) denote the induced matching number of H. Then
reg(H) = (d − 1)ν(H) + 1.
Using their notion of labeled hypergraphs, Lin and McCullough [37, Proposition 4.1 and
Theorem 4.12] also compute the regularity explicitly for special classes of hypergraphs.
We shall again rephrase their results in terms of edge ideals of hypergraphs. A hypergraph
H is called saturated if every edge in H contains free vertices.
Theorem 5.15. Let H = (X, E) be a simple hypergraph with edge ideal I = I(H). The
following are equivalent:
(1) H is saturated; and
(2) The Taylor resolution of I is minimal.
In this case, we have
reg(I) = |X| − |E| + 1.
For a vertex x in a hypergraph H S
= (X, E), let Wx = {E ∈ E | x ∈ E}. Denote by SE
the set {Wx | x ∈ E}, and let P = E∈E SE . An element Wx in P is called simple if it
does not contain any other element of P as a proper subset. The hypergraph H is said
to have isolated simple edges if for any edge E in H not containing free vertices, the set
SE has exactly one simple maximal element.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

19

Theorem 5.16. Let H be a simple hypergraph with edge ideal I = I(H). Suppose that H
has isolated simple edges. Then
X
reg(I) = |X| − |V | +
(|W | − 1) + 1.
W ∈P, W simple

b

e

a

g

h

i

d
c

f

Figure 8. A labeled hypergraph having isolated simple edges.
Example 5.17. Let I = (ab, bcdef, ac, eg, f g, gh, hi) ⊆ R = K[a, b, . . . , i] be the edge
ideal of H. Then the set P of H is depicted in Figure 8, where filled points represent
edges in H with free vertices and unfilled points represent edges in H without free vertices.
Note that, as a hypergraph, this figure represents the dual hypergraph of H, and also the
labeled hypergraph corresponding to I in the sense of [37]. It can be seen that H has
isolated simple edges, and those simple sets Wx s in P are labeled by a and g. Theorem
5.16 gives
reg(I) = 9 − 7 + (2 − 1) + (3 − 1) + 1 = 6.
Remark 5.18. It can be seen that the ideal I in Example 5.17 is not sequentially CohenMacaulay. Thus, its associated simplicial complex ∆(I) is not vertex decomposable.
This example shows that inductive inequalities in Theorems 3.4 and 5.11 may become
equalities for a larger class of squarefree monomial ideals than those corresponding to
vertex decomposable simplicial complexes.
6. Open problems and questions
In this last section of the paper, we state a number of open problems and conjectures
that we would like to see answered. We first observe that the combinatorial bounds in
Theorems 4.13, 4.15 and 4.20 in practice are not easy to compute. It is desirable to find
bounds that relate to more familiar combinatorial invariants of hypergraphs and simplicial
complexes.
Problem 6.1. Find bounds for the regularity of a squarefree monomial ideal in terms of
familiar combinatorial invariants and structures of associated hypergraph and simplicial
complex.
Let χ(H) denote the chromatic number of a hypergraph H, i.e., the least number of
colors needed to color the vertices of H such that no edge (that is not an isolated loop)

20

HUY TÀI HÀ

in H is mono-colored. It was observed in [51, Theorem 2] that for any independent set T
in G,
reg(R/I(G)) ≤ χ((G \ T )c ).

(6.1)

Problem 6.2. Extend (6.1) to hypergraphs. Investigate the relation between the regularity of a hypergraph and its coloring properties.
As pointed out in Example 5.3, the class of graphs with regularity ≤ 3 is strictly larger
than that of claw-free graphs whose complements contain no induced C4 . We would like
to see this class of graphs classified.
Problem 6.3. Give a combinatorial characterization for squarefree monomial ideals I
such that reg(I) = 3. In particular, classify simple graphs G such that reg(I(G)) = 3.
It was shown in Theorem 5.11 that for vertex decomposable simplicial complexes (and
hypergraphs) the inductive inequalities in Section 3 become equalities. It is natural to
seek for combinatorial invariants that measure the regularity of these complexes (and
hypergraphs).
Problem 6.4. Let H be a vertex decomposable hypergraph. Compute reg(H).
Examples 5.12 and 5.17 show that inductive inequalities in Theorem 3.4 may become
equalities for a larger class of simplicial complexes (and hypergraphs) than vertex decomposable ones. In particular, we would like to classify squarefree monomial ideals for which
the conclusion of Theorem 5.11 holds.
Problem 6.5. Characterize squarefree monomial ideals I for which there exists a variable
x such that
reg(I) = max{reg(I : x) + 1, reg(I, x)}.
Recall that the inductive bound of Theorem 3.5 comes from the following short exact
sequence
(6.2)

0 −→

R
R
R
R
−→
⊕
−→
−→ 0.
(xE ) ∩ I(H \ E)
(xE ) I(H \ E)
I(H)

The bound in Theorem 3.5 would become an equality if the mapping cone construction
applied to (6.2) results in the minimal free resolution of R/I(H). We would like to be
able to identify all such edges E for which this is true.
Problem 6.6. Characterize all edges E in a simple hypergraph H such that the mapping cone construction applied to the short exact sequence (6.2) gives the minimal free
resolution of R/I(H).
[27, Theorem 3.2] partially answered this problem. Problem 6.6, in fact, comes from a
larger picture, when a squarefree monomial ideal I is splitted into the sum of two subideals. We would also like to see in general which combinatorial structures would enforce
the minimality of the mapping cone construction applied to a similar short exact sequence.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

21

0

Problem 6.7. Let H and H be simple hypergraphs on the same vertex set X with
disjoint edge sets E(H) and E(H 0 ). Let I = I(H) and J = I(H 0 ). Find combinatorial
conditions for the mapping cone construction applied to the short exact sequence
R
R R
R
0 −→
−→ ⊕ −→
−→ 0
I ∩J
I
J
I +J
to give the minimal free resolution of R/I + J.
Along the same line, it is also desirable to see when the inductive inequalities in Theorem
3.6 and Corollary 3.7 become equalities.
Problem 6.8. Let H,SH1 , . . . , Hs be simple hypergraphs over the same vertex set X, and
assume that E(H) = si=1 E(Hi ). Find combinatorial conditions for the following equality
to hold:
s
X
reg(R/I(H)) =
reg(R/I(Hi )).
i=1

An important problem in commutative algebra during the last few decades is to study
the regularity of powers of ideals. It is known (cf. [2, 12, 35, 47]) that for a homogeneous
ideal I ⊆ R, reg(I q ) is asymptotically a linear function, i.e., there exist constants a, b and
q0 such that for q ≥ q0 , reg(I q ) = aq + b. While the coefficient a is well-understood, the
constants b and q0 are quite mysterious. Many recent studies are devoted to investigating
these constants (cf. [4, 10, 18, 19, 25]). Even for edge ideals of graphs the exact values
for these constants are still out of reach.
Problem 6.9. Let I be a squarefree monomial ideal. Find combinatorial interpretations
of the linear function reg(I q ) for q  0.
For a very simple family of edge ideals, we would like to see constants b and q0 evaluated
explicitly.
Problem 6.10. Let I = I(Ck ) be the edge ideal of a k-cycle. Find the linear form of
reg(I q ) for q  0.
Computational experiments lead us to conjecture that for this class of edge ideals, the
regularity of I q becomes a linear function as soon as q ≥ 2.
Conjecture 6.11. Let I = I(Ck ) be the edge ideal of a k-cycle. Then reg(I q ) is a linear
function for q ≥ 2.
References
[1] S. Ahmad and I. Anwar, An upper bound for the regularity of ideals of Borel type. Comm. Algebra
36 (2008), no. 2, 670-673.
[2] A. Bagheri, M. Chardin and H.T. Hà, The eventual shape of Betti tables of powers of ideals. To
appear in Math. Res. Lett. arXiv:1110.0383.
[3] C. Berge, Hypergraphs: combinatorics of finite sets. North-Holland, New York, 1989.
[4] D. Berlekamp, Regularity defect stabilization of powers of an ideal. Math. Res. Lett. 19 (2012),
no. 1, 109-119.

22

HUY TÀI HÀ

[5] T. Biyikoglu and Y. Civan, Vertex decomposable graphs, codismantlability, Cohen-Macaulayness
and Castelnuovo-Mumford regularity. Preprint, arXiv:1205.5631
[6] T. Biyikoglu and Y. Civan, Bounding Castelnuovo-Mumford regularity of graphs via Lozin’s transformation. Preprint, arXiv:1302.3064.
[7] R.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), no. 8, 2411-2425.
[8] W. Bruns and J. Herzog, Cohen-Macaulay rings. Cambridge Studies in Advanced Mathematics,
39. Cambridge University Press, Cambridge, 1993.
[9] 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.
[10] M. Chardin, Powers of ideals and the cohomology of stalks and fibers of morphisms. Preprint.
arXiv:1009.1271.
[11] M. Cimpoeaş, Regularity for certain classes of monomial ideals. An. Ştiint,. Univ. “Ovidius”
Constanţa Ser. Mat. 15 (2007), no. 1, 33-46.
[12] S.D. Cutkosky, J. Herzog, and N.V. Trung, Asymptotic behaviour of the Castelnuovo-Mumford
regularity. Composito Mathematica, 118 (1999), 243-261.
[13] H. Dao and J. Schweig, Bounding the projective dimension of a squarefree monomial ideal via
domination in clutters. Preprint, arXiv:1301.2665.
[14] H. Dao and J. Schweig, Projective dimension, graph domination parameters, and independence
complex homology. Preprint, arXiv:1110.2841.
[15] H. Dao, C. Huneke and J. Schweig, Bounds on the regularity and projective dimension of ideals
associated to graphs. Preprint, arXiv:1110.2570.
[16] D. Eisenbud and S. Goto, Linear free resolutions and minimal multiplicity. J. Algebra 88 (1984),
no. 1, 89-133.
[17] D. Eisenbud, M. Green, K. Hulek and S. Popescu, Restricting linear syzygies: algebra and geometry. Compositio Math. 141 (2005) 1460-1478.
[18] D. Eisenbud and J. Harris, Powers of ideals and fibers of morphisms. Math. Res. Lett. 17 (2010),
no. 2, 267-273.
[19] D. Eisenbud and B. Ulrich, Notes on regularity stabilization. Proc. Amer. Math. Soc. 140 (2012),
no. 4, 1221-1232.
[20] S. Faridi, The facet ideal of a simplicial complex. Manuscripta Math. 109 (2002), no. 2, 159-174.
[21] O. Fernández-Ramos and P. Gimenez, Regularity 3 in edge ideals associated to bipartite graphs.
Preprint, arXiv:1207.5553.
[22] R. Fröberg, On Stanley-Reisner rings. Topics in algebra, Part 2 (Warsaw, 1988), 5770, Banach
Center Publ., 26, Part 2, PWN, Warsaw, 1990.
[23] A. Frühbis-Krüger and N. Terai, Bounds for the regularity of monomial ideals. Pragmatic 1997
(Catania). Matematiche (Catania) 53 (1998), suppl., 83-97 (1999).
[24] I. Gitler and C.E. Valencia, Bounds for invariants of edge-rings. Comm. Algebra 33 (2005) 16031616.
[25] H.T. Hà, Asymptotic linearity of regularity and a∗ -invariant of powers of ideals. Math. Res. Lett.
18 (2011), no. 1, 1-9.
[26] H.T. Hà and A. Van Tuyl, Splittable ideals and the resolutions of monomial ideals. J. Algebra
309 (2007), no. 1, 405-425.
[27] 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.
[28] H.T. Hà and R. Woodroofe, Results on the regularity of squarefree monomial ideals. Preprint,
arXiv:1301.6779.
[29] J. Herzog, A generalization of the Taylor complex construction. Comm. Algebra 35 (2007), no. 5,
1747-1756.
[30] J. Herzog and T. Hibi, Monomial ideals. GTM 260, Springer-Verlag, 2011.
[31] L.T. Hoa and N.V. Trung, On the Castelnuovo-Mumford regularity and the arithmetic degree of
monomial ideals. Math. Z. 229 (1998), no. 3, 519-537.

REGULARITY OF SQUAREFREE MONOMIAL IDEALS

23

[32] 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.
[33] M. Katzman, Characteristic-independence of Betti numbers of graph ideals. J. Combin. Theory
Ser. A 113 (2006), no. 3, 435-454.
[34] F. Khosh-Ahang and S. Moradi, Regularity and projective dimension of edge ideal of C5 -free
vertex decomposable graphs. Preprint, arXiv:1305:6122.
[35] V. Kodiyalam, Asymptotic behaviour of Castelnuovo-Mumford regularity. Proceedings of the
American Mathematical Society, 128, no. 2, (1999), 407-411.
[36] M. Kummini, Regularity, depth and arithmetic rank of bipartite edge ideals. J. Algebraic Combin.
30 (2009), no. 4, 429-445.
[37] K-N. Lin and J. McCullough, Hypergraphs and the Regularity of Square-free Monomial Ideals.
Preprint, arXiv:1211.4301.
[38] 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.
[39] E. Miller and B. Sturmfels, Combinatorial Commutative Algebra. GTM 227, Springer-Verlag,
2004.
[40] S. Moradi and D. Kiani, Bounds for the regularity of edge ideals of vertex decomposable and
shellable graphs. Bull. Iranian Math. Soc 36 (2010), no. 2, 267-277.
[41] M. Morales, A.A.Y. Pour and R. Zaare-Nahandi, Regularity of edge ideal of a graph. J. Pure Appl.
Algebra 216 (2012), no. 12, 2714-2719.
[42] S. Morey and R.H. Villarreal, Edge ideals: algebraic and combinatorial properties. Progress in
commutative algebra 1, 85-126, de Gruyter, Berlin, 2012.
[43] E. Nevo, Regularity of edge ideals of C4 -free graphs via the topology of the lcm-lattice. J. Combin.
Theory Ser. A 118 (2011), no. 2, 491-501.
[44] I. Peeva, Graded syzygies. Algebra and Applications, 14. Springer-Verlag London, Ltd., London,
2011.
[45] R. Stanley, Combinatorics and Commutative Algebra. Progress in Mathematics, 41. Birkhäuser
Boston, Inc., Boston, MA, 1983.
[46] N. Terai, Alexander duality theorem and Stanley-Reisner rings. Free resolution of coordinate
rings of projective varieties and related topics (Japanese) (Kyoto, 1998). Surikaisekikenkyusho
Kokyuroku No. 1078 (1999), 174-184.
[47] 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.
[48] A. Van Tuyl, Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity. Arch. Math. (Basel) 93 (2009), no. 5, 451-459.
[49] R. H. Villarreal, Monomial algebras. Monographs and Textbooks in Pure and Applied Mathematics, 238. Marcel Dekker, Inc., New York, 2001.
[50] G. Wegner, d-collapsing and nerves of families of convex sets. Arch. Math. (Basel) 26 (1975),
317-321.
[51] R. Woodroofe, Matchings, coverings, and Castelnuovo-Mumford regularity. Preprint,
arXiv:1009.2756.
[52] X. Zheng, Resolutions of facet ideals, Comm. Algebra 32 (2004) 2301-2324.
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/

