LINEARITY DEFECT OF EDGE IDEALS AND FRÖBERG’S THEOREM

arXiv:1506.05769v7 [] 16 Jan 2016

HOP D. NGUYEN AND THANH VU
Abstract. Fröberg’s classical theorem about edge ideals with 2-linear resolution can be regarded as a classification of graphs whose edge ideals have linearity defect zero. Extending his
theorem, we classify all graphs whose edge ideals have linearity defect at most 1. Our characterization is independent of the characteristic of the base field: the graphs in question are
exactly weakly chordal graphs with induced matching number at most 2. The proof uses the
theory of Betti splittings of monomial ideals due to Francisco, Hà, and Van Tuyl and the structure of weakly chordal graphs. Along the way, we compute the linearity defect of edge ideals
of cycles and weakly chordal graphs. We are also able to recover and generalize previous results due to Dochtermann-Engström, Kimura and Woodroofe on the projective dimension and
Castelnuovo-Mumford regularity of edge ideals.

1. Introduction
Let (R, m) be a standard graded algebra over a field k with the graded maximal ideal m. Let
M be a finitely generated graded R-module. For integers i, j, the (i, j)-graded Betti number of
M is defined by βi,j (M) = dimk TorR
i (k, M)j . The following number is called the (CastelnuovoMumford) regularity of M over R
regR M = sup{j − i : βi,j (M) 6= 0}.
The regularity is an important invariant of graded modules over R. When R is a polynomial ring
and M is a monomial ideal of R, its regularity exposes many combinatorial flavors. This fact
has been exploited and proved to be very useful for studying the regularity; for recent surveys,
see [13], [28], [38]. A classical and instructive example is Fröberg’s theorem. Recall that if G is a
graph on the vertex set {x1 , . . . , xn } (where n ≥ 1), and by abuse of notation, R is the polynomial
ring k[x1 , . . . , xn ], then the edge ideal of G is I(G) = (xi xj : {xi , xj } is an edge of G). Unless
otherwise stated, whenever we talk about an invariant of I(G) (including the regularity and the
linearity defect, to be defined below), it is understood that the base ring is the polynomial ring R.
For m ≥ 3, the cycle Cm is the graph on vertices x1 , . . . , xm with edges x1 x2 , . . . , xm−1 xm , xm x1 .
We say that a graph G is weakly chordal (or weakly triangulated) if for every m ≥ 5, neither
G, nor its complement contains Cm as an induced subgraph. G is chordal if for any m ≥ 4,
Cm is not an induced subgraph of G. Fröberg’s theorem [10] says that I(G) has regularity 2
if and only if the complement graph of G is chordal. It is of interest to find generalizations of
this important result; see, for instance, [7], [8]. Fernández-Ramos and Gimenez [8, Theorem 4.1]
extended Fröberg’s theorem by providing a combinatorial characterization of connected bipartite
graphs G such that reg I(G) = 3. In general, the regularity 3 condition on edge ideals is not
2010 Mathematics Subject Classification. 05C25, 13D02, 13H99.
Key words and phrases. Edge ideal; Linearity defect; Weakly chordal graph; Castelnuovo-Mumford regularity.
This work is partially supported by the NSF grant DMS-1103176. Part of this work was done when Nguyen
was a Marie Curie fellow of the Istituto Nazionale di Alta Matematica.

1

2

HOP D. NGUYEN AND THANH VU

purely combinatorial as it depends on the characteristic of the field; see Katzman’s example in
[24, Page 450].
The linearity defect was introduced by Herzog and Iyengar [19] motivated by work of Eisenbud,
Fløystad, and Schreyer [6]. It is defined via the linear part of minimal free resolutions of modules
over R, see Section 2 for details. The linear part appears naturally: from [6, Theorem 3.4],
taking homology of a complex over a polynomial ring is equivalent to taking the linear part of
a minimal free complex over the (Koszul dual) exterior algebra. The linearity defect itself is
interesting because it yields stronger homological information than the regularity: over a local
ring, Herzog and Iyengar [19, Proposition 1.8] proved that modules with finite linearity defect
have rational Poincaré series with constant denominator. On the other hand, there exist modules
which have finite regularity and transcendental Poincaré series [22, Page 252]. Furthermore, the
linearity defect is flexible enough to generate a rich theory: going beyond regular rings, one still
encounters reasonable classes of rings over which every module has finite linearity defect, e.g.
exterior algebras [6], homogeneous complete intersections defined by quadrics [19].
Let R again be a polynomial ring over k and M a finitely generated graded R-module. The
linearity defect of M over R is denoted by ldR M or simply ld M. Then ld M equals ℓ (where
ℓ ≥ 0) if and only if the first syzygy module of M which is componentwise linear in the sense
of Herzog and Hibi [17] is the ℓ-th one. In particular, the condition that an edge ideal has
2-linear resolution is equivalent to the condition that its linearity defect is 0. Fröberg’s theorem
can be rephrased as a classification of edge ideals with linearity defect 0. Our motivation is to
find a purely combinatorial characterization for linearity defect 1 edge ideals; it turns out that
indeed there is one. Finding such a characterization is non-trivial due to several reasons. First,
while the Hochster’s formula can give much information about the regularity of Stanley-Reisner
ideals (see for example Dochtermann and Engström [5]), up to now there is no combinatorial
interpretation of the linearity defect of Stanley-Reisner ideals. (See [32], [35] for some results
about the linearity defect of such ideals.) Second and furthermore, the linearity defect generally
cannot be read off from the Betti table: for example (see [20, Example 2.8]), the ideals
I1 = (x41 , x31 x2 , x21 x22 , x1 x32 , x42 , x31 x3 , x21 x2 x23 , x21 x33 , x1 x22 x23 )
and
I2 = (x41 , x31 x2 , x21 x22 , x31 x3 , x1 x22 x3 , x1 x2 x23 , x1 x42 , x21 x33 , x42 x3 )
in k[x1 , x2 , x3 ] have the same graded Betti numbers, but the first one has linearity defect 0
while the second one has positive linearity defect (equal to 1). Third, the quest of finding the
aforementioned characterization yields interesting new insights even to the more classical topics
concerning Castelnuovo-Mumford regularity or the projective dimension. Indeed, in proving one
of the main results (Theorem 5.5), we recover a theorem of Woodroofe [40, Theorem 14] on
regularity of edge ideals of weakly chordal graphs. In Theorem 7.7, we prove a new result about
the projective dimension of edge ideals of weakly chordal graphs, extending previous work of
Dochtermann and Engström [5] and Kimura [26], [27].
As mentioned earlier, our motivation is to see if the linearity defect one condition is purely
combinatorial. Recall that for g ≥ 1, the gK2 graph is the graph consisting of g disjoint edges.
The induced matching number of a graph G, denoted by indmatch(G), is the largest number
g such that there is an induced gK2 subgraph in G. The first main result of our paper is the
following new generalization of Fröberg’s theorem.

LINEARITY DEFECT OF EDGE IDEALS

3

Theorem 1.1 (See Theorem 7.6). Let G be a graph. Then ld I(G) = 1 if and only if G is a
weakly chordal graph with induced matching number indmatch(G) = 2.
This suggests (to us) a surprising, if little exploited connection between the linearity defect of
edge ideals and combinatorics of graphs. The hard part of Theorem 1.1, the sufficiency, follows
from a more general statement about the linearity defect of edge ideals of weakly chordal graphs.
Thus the second main result of our paper, which was inspired by the aforementioned theorem
of Woodroofe [40, Theorem 14], is
Theorem 1.2 (See Theorem 5.5). Let G be a weakly chordal graph with at least one edge. Then
there is an equality ld I(G) = indmatch(G) − 1.
Our proof of Theorem 1.2 takes a cue from the theory of Betti splittings due to Francisco, Hà,
and Van Tuyl [9]. Let I be a monomial ideal of R, and G(I) its set of uniquely determined minimal
monomial generators. Let J, K be monomial ideals contained in I such that G(J) ∩ G(K) = ∅
and G(I) = G(J) ∪ G(K), so that in particular I = J + K. The decomposition of I as J + K is
called a Betti splitting if for all i ≥ 0 and all j ≥ 0, the following equality of Betti numbers
βi,j (I) = βi,j (J) + βi,j (K) + βi−1,j (J ∩ K)

(1.1)

holds. In [9], [14], [15], Betti splittings were used to study Betti numbers and regularity of edge
ideals and more general squarefree monomial ideals. What makes Betti splittings useful to the
study of linearity defect is the following fact, proven in [9, Proposition 2.1]: the decomposition
R
I = J + K is a Betti splitting if and only if the natural maps TorR
i (k, J ∩ K) −→ Tori (k, J)
R
and TorR
i (k, J ∩ K) −→ Tori (k, K) are trivial for all i ≥ 0. It is proved in Proposition 4.3 of
Section 4 that we have a good control of the linearity defect along short exact sequences for
which certain induced maps of Tor have strong vanishing properties. This result implies that
Betti splittings are suitable for bounding the linearity defect (Theorem 4.9).
The second component of the proof of Theorem 1.2 comes from the structure theory of weakly
chordal graphs. Specifically, we use the existence of co-two-pair edges [16] in a weakly chordal
graph. The main work of Section 5 is to show that any co-two-pair in a weakly chordal graph
gives rise to a Betti splitting of the corresponding edge ideal; see Theorem 5.5. A variety of
techniques is employed to prove the last result, including the theory of lcm-lattice in monomial
resolutions developed in [11] and [33].
The paper is organized as follows. We start by recalling the necessary background in Section
2. Section 3 provides a lower bound for the linearity defect of edge ideals in terms of the
induced matching number of the associated graphs. This bound plays a role in the proof of
the necessity part of Theorem 1.1 and in Theorem 1.2. The main result of Section 4 is that
linearity defect behaves well with respect to Betti splittings (Theorem 4.9). In Section 5, we
compute the linearity defect of edge ideals associated to weakly chordal graphs. In particular
we prove in Section 5 Theorem 1.2 introduced above. Section 6 concerns with the computation
of linearity defect for the simplest non-weakly-chordal graphs, namely cycles of length ≥ 5. (For
complements of cycles, the computation was done in [32, Theorem 5.1].) Besides applications
to the theory of regularity and projective dimension of edge ideals, in Section 7, we prove
Theorem 1.1. In Section 8, we study the dependence of the linearity defect of edge ideals on the
characteristic of the field k, and propose some open questions.
Since the linearity defect was originally defined in [19] for modules over local rings, we state
some of our results in this greater generality; see for example Proposition 4.3, Theorem 4.9 and

4

HOP D. NGUYEN AND THANH VU

Proposition 4.10. The reader may check easily that the analogues of these results for graded
algebras are also true, using the same method.
2. Background
We assume that the reader is familiar with the basic of commutative algebra; a good reference
for which is [3]. For the theory of free resolutions, we refer to [2].
2.1. Linearity defect. Let (R, m, k) be a standard graded k-algebra with the graded maximal
ideal m, or a noetherian local ring with the maximal ideal m and the residue field k. By a
“standard graded k-algebra”, we mean that R is a commutative algebra over k, R is N-graded
with R0 = k, and R is generated over k by finitely many elements of degree 1. Sometimes, we
omit k and write (R, m) for simplicity.
Let us define the linearity defect for complexes of modules over local rings; the modification
for graded algebras is straightforward. Let (R, m) be a noetherian local ring, and M be a chain
complex of R-modules with homology H(M) degreewise finitely generated and bounded below,
i.e. Hi (M) is finitely generated for all i ∈ Z and Hi (M) = 0 for i ≪ 0. Let F be its minimal
free resolution:
F : · · · −→ Fi −→ Fi−1 −→ · · · −→ F1 −→ F0 −→ F−1 −→ · · · .
In particular, up to isomorphism of complexes, F is the unique complex of finitely generated
free R-modules that fulfills the following conditions:
(i) Im(Fi ) ⊆ mFi−1 for all i ∈ Z,
(ii) there is a morphism of complexes F −→ M which induces isomorphism on homology.
The complex F can be chosen such that Fi = 0 for all i < inf M := inf{i : Hi (M) 6= 0}. See the
monograph of Roberts [34] for more details.
The complex F admits a filtration (F i F )i≥0 , where F i F is the complex
F i F : · · · −→ Fi+1 −→ Fi −→ mFi−1 −→ · · · −→ mi−1 F1 −→ mi F0 −→ mi+1 F−1 −→ · · · ,
with the differential being induced by that of F . The complex
M F iF
linR F =
F i+1 F
i∈Z

is called the linear part of F . It is a complex of graded free grm R-modules. Here, as usual,
M mi R
grm R =
mi+1 R
i≥0

is the associated graded ring of R with respect to the m-adic filtration. By a straightforward
computation, one has for all i ≥ 0 an isomorphism of graded grm R-modules:
Fi
(linR F )i = (grm Fi ) (−i) ∼
⊗R/m (grm R)(−i).
(2.1)
=
mFi
It is worth pointing out here a simple procedure for computing the linear part of minimal free
resolutions if R is a graded algebra. Now M is a complex of graded R-modules with H(M)
degreewise finitely generated and bounded below, and F is the minimal graded free resolution of
M. It is not hard to see that linR F has the same underlying module structure as F itself, and

LINEARITY DEFECT OF EDGE IDEALS

5

the matrices of differentials of linR F are obtained from that of F by replacing each non-zero
entry of degree at least 2 by zero.
For example, let R = k[x, y] and I = (x2 , xy 2 , y 4), then a minimal graded free resolution of I
is


−y 2 0


 x
−y 2 


0
x
F : 0 −→ R(−4) ⊕ R(−5) −−−−−−−−−−−→ R(−2) ⊕ R(−3) ⊕ R(−4) −→ 0.
The linear part of F is the following complex
0 0

x 0 

0
x
linR F : 0 −→ R(−1)2 −−−−−−−→ R3 −→ 0.







The linearity defect of M over R, denoted by ldR M, is defined as follows:
ldR M = sup{i : Hi (linR F ) 6= 0}.
By convention, ldR M = 0 if M is the trivial module 0. Except for the proof of Proposition
4.3, we will work solely with linearity defect of modules. The notion of linearity defect was
introduced by Herzog and Iyengar in 2005; see their paper [19] for more information about the
homological significance of the complex linR F and the linearity defect.
In the above example, we can verify that H1 (linR F ) = 0 and ldR I = 0. Following [19],
modules which have linearity defect zero are called Koszul modules.
2.2. Castelnuovo-Mumford regularity. Let (R, m) now be a standard graded k-algebra, and
M a finitely generated graded R-module. The Castelnuovo-Mumford regularity of M over R is
regR M = sup{j − i : TorR
i (k, M)j 6= 0}.
Ahangari Maleki and Rossi [1, Proposition 3.5] showed that if ldR M = ℓ < ∞ then the regularity
of M can be computed using the first ℓ steps in its minimal free resolution:
regR M = sup{j − i : TorR
i (k, M)j 6= 0 and i ≤ ℓ}.
In particular, if M is a Koszul R-module then regR M equals the maximal degree of a minimal
homogeneous generator of M.
We say that M has a linear resolution if for some d ∈ Z, M is generated in degree d and
regR M = d. We also say that M has a d-linear resolution in that case.
Römer [35] proved that if R is a Koszul algebra, i.e. regR k = 0, then the following statements
are equivalent:
(i) M is a Koszul module;
(ii) M is componentwise linear, namely for every d ∈ Z, the submodule Mhdi of M generated
by homogeneous elements of degree d has a d-linear resolution.
A proof of this result can be found in [21, Theorem 5.6]. From Römer’s theorem, one gets
immediately that if R is a Koszul algebra, and M is generated in a single degree d, then ldR M = 0
if and only if M has a d-linear resolution.

6

HOP D. NGUYEN AND THANH VU

2.3. Graphs and their edge ideals. We always mean by a graph G a pair (V (G), E(G)),
where V (G) = {x1 , . . . , xn } is a finite set (with n ≥ 1), and E(G) is a collection of non-ordered
pairs {xi , xj } where 1 ≤ i, j ≤ n, i 6= j. Elements in V (G) are called vertices of G, while elements
in E(G) are termed edges of G. In this paper, we do not consider infinite graphs, nor do we
consider graphs with loops or multiple edges between two vertices. Most of the material on
graph theory that we need can be found in [38].
For a graph G and x ∈ V (G), a vertex y ∈ V (G) is called a neighbor of x if {x, y} ∈ E(G).
We also say that y is adjacent to x in that case. We denote by N(x) the set of neighbors of x.
The graph Gc with the same vertices as G and with edge set consisting of non-ordered pairs
{x, y} of non-adjacent vertices of G, is called the complement graph of G.
By a cycle, we mean a graph with vertices x1 , . . . , xm (with m ≥ 3) and edges x1 x2 , . . . ,
xm−1 xm , xm x1 . In that case, m is called the length of the cycle. The complement graph of a
cycle (of length m) is called an anticycle (of length m). The path of length m − 1 (where m ≥ 2),
denoted by Pm , is the graph with vertices x1 , . . . , xm and edges x1 x2 , . . . , xm−1 xm .
A subgraph of G is a graph H such that V (H) ⊆ V (G) and E(H) ⊆ E(G). For a set of edges
E ⊆ E(G), the deletion of G to E is the subgraph of G with the same vertex set as G and with
the edge set E(G) \ E. If E consists of a single edge e, we denote G \ E simply by G \ e.
A subgraph H of G is called an induced subgraph if for every pair (x, y) of vertices of H, x
and y are adjacent in H if and only if they are adjacent in G. Clearly for any subset V of V (G),
there exists a unique induced subgraph of G with the vertex set V . For a subset of vertices
V ⊆ V (G), the deletion of G to V , denoted by G \ V is the induced subgraph of G on the vertex
set V (G) \ V . If V consists of a single vertex x, then we denote G \ V simply by G \ x.
For a graph G on the vertex set {x1 , . . . , xn }, let R be the polynomial ring on n variables, also
denoted by x1 , . . . , xn . The edge ideal of G is
I(G) = (xi xj : {xi , xj } is an edge of G) ⊆ R.
We will usually refer to the symbol xi xj (where i 6= j, 1 ≤ i, j ≤ n) both as an edge of G and as
a monomial of R. Instead of writing regR I(G) and ldR I(G), we will usually omit the obvious
base ring and write simply reg I(G) and ld I(G). We refer to [39, Chapter 6] for a rich source of
information about the theory of edge ideals.
2.4. Induced matchings. The graph with 2m vertices x1 , . . . , xm , y1 , . . . , ym (where m ≥ 1)
and exactly m edges x1 y1 , . . . , xm ym is called the mK2 graph.
Let G be a graph. A matching of G is a collection of edges e1 , . . . , em (where m ≥ 1) such that
no two of them have a common vertex. The number m is then called the size of the matching.
A matching e1 , . . . , em of G is an induced matching if the induced subgraph of G on the vertex
set e1 ∪ · · · ∪ em is the mK2 graph. The induced matching number indmatch(G) is defined as
the largest size of an induced matching of G.
2.5. Weakly chordal graphs.
Definition 2.1. A graph G is said to be weakly chordal if every induced cycle in G or in Gc
has length at most 4. G is said to be chordal if it does not contain any induced cycle of length
greater than 3. We say that G is co-chordal if Gc is a chordal graph.
Example 2.2. Every chordal graph is weakly chordal: for such a graph G, clearly G has no
induced cycle of length greater than 3. Moreover, Gc has no induced cycle of length at least 5.

LINEARITY DEFECT OF EDGE IDEALS

7

Indeed, if Gc contains an induced cycle of length 5, then taking the complement, we see that G
contains an induced cycle of length 5. If Gc contains an induced cycle of length at least 6, then
Gc contains an induced 2K2 . This implies that G contains an induced cycle of length 4. In any
case, we get a contradiction.
From the definition, G is weakly chordal if and only if Gc is weakly chordal. Hence the above
arguments also show that every co-chordal graph is weakly chordal.
Theorem 2.3 (Fröberg’s theorem [10]). Let G be a graph. Then the following statements are
equivalent:
(i) ld I(G) = 0;
(ii) G is co-chordal;
(iii) G is weakly chordal and indmatch(G) = 1.
Proof. Since I(G) is generated in degree 2, (i) is equivalent to the condition that I(G) has 2linear resolution; see Section 2.2. Hence that (i) ⇐⇒ (ii) is a reformulation of Fröberg’s theorem.
It is not hard to see that (ii) ⇐⇒ (iii).

3. Linearity defect and induced matchings
Firstly we have the following simple change-of-rings statement.
Lemma 3.1. Let (R, m) → (S, n) be a morphism of noetherian local rings such that grn S is a
flat grm R-module. Let M be a finitely generated R-module. Then there is an equality
ldR M = ldS (M ⊗R S).
Proof. Let F be the minimal free resolution of M over R. Since grm R → grn S is a flat morphism,
so is the map R → S. Hence F ⊗R S is a minimal free resolution of M ⊗R S over S. Observe
that we have an isomorphism of complexes of grn S-modules
linS (F ⊗R S) ∼
= linR F ⊗grm R (grn S).
Indeed, at the level of modules, we wish to show


linS (F ⊗R S) i ∼
= linR F i ⊗grm R (grn S)

(3.1)

(3.2)

as graded grn S-modules for each i ≥ 0. On the one hand, there is the following chain in which
the first isomorphism follows from (2.1),


Fi
R
∼
(lin F )i ⊗grm R (grn S) =
⊗R/m (grm R)(−i) ⊗grm R (grn S)
mFi
Fi
∼
⊗R/m (grn S)(−i)
=
mFi


Fi
∼
⊗R/m (S/n) ⊗S/n (grn S)(−i).
=
mFi
On the other hand, also from (2.1), there is an isomorphism

Fi ⊗R S
⊗S/n (grn S)(−i).
linS (F ⊗R S) i ∼
=
n(Fi ⊗R S)

8

HOP D. NGUYEN AND THANH VU

Since Fi is a free R-module, we have a natural isomorphism of (S/n)-modules
Fi ⊗R S ∼ Fi
⊗R/m (S/n).
=
n(Fi ⊗R S)
mFi
Hence the isomorphisms of type (3.2) were established. We leave it to the reader to check that
such isomorphisms give rise to an isomorphism at the level of complexes.
Since grm R → grn S is a morphism of standard graded algebras, it is also faithfully flat. Hence
the isomorphism (3.1) gives us
sup{i : Hi (linR F ) 6= 0} = sup{i : Hi (linS (F ⊗R S)) 6= 0},
which is the desired conclusion.



Corollary 3.2. Let (R, m) → (S, n) be a flat extension of standard graded k-algebras, and I a
homogeneous ideal of R. Then there are equalities
ldR I = ldS (IS),
regR I = regS (IS).
Proof. For the first equality, use the graded analog of Lemma 3.1 for the map R → S and
note that grm R ∼
= R. The second equality follows from the same line of thought and is even
simpler.

Hence below, especially in Sections 5 and 6, whenever we work with a polynomial ring S, a
polynomial subring R and an ideal I of R, there is no danger of confusion in writing simply ld I
instead of ldR I or ldS (IS). The same remark applies to the regularity.
Now we prove that for any graph G, ld I(G) is bounded below by indmatch(G) − 1. Although
this inequality is simple, it becomes an equality for a non-trivial class of graphs – weakly chordal
graphs. This will be proved in Theorem 5.5.
Recall that a ring homomorphism θ : R → S is called an algebra retract if there exists a local
homomorphism ϕ : S → R such that ϕ ◦ θ is the identity map of R. In such a case, ϕ is called
the retraction map of the algebra retract θ. If R, S are graded rings, we require θ, ϕ to preserve
the gradings. The following result can be proved in the same manner as [30, Lemma 4.7]. Note
that the proof of ibid. depends critically on a result of Şega [36, Theorem 2.2] which was stated
for local rings, but holds in the graded case as well.
Lemma 3.3. Let θ : (R, m) → (S, n) be an algebra retract of standard graded k-algebras with the
retraction map ϕ : S → R. Let I ⊆ m be a homogeneous ideal of R. Let J ⊆ n be a homogeneous
ideal containing θ(I)S such that ϕ(J)R = I. Then there are inequalities
ldR (R/I) ≤ ldS (S/J),
ldR I ≤ ldS J,
regR I ≤ regS J.
Corollary 3.4. Let G be a graph and H an induced subgraph. Then there are inequalities
reg I(H) ≤ reg I(G),
ld I(H) ≤ ld I(G).
Proof. Straightforward application of Lemma 3.3.



LINEARITY DEFECT OF EDGE IDEALS

9

A direct consequence is the following statement. The bound for the regularity in the next
corollary is well-known; see [24, Lemma 2.2], [40, Lemma 7].
Corollary 3.5. Let G be a graph. Then there are inequalities
ld I(G) ≥ indmatch(G) − 1,
reg I(G) ≥ indmatch(G) + 1.
Proof. Let m = indmatch(G) and x1 y1 , . . . , xm ym be an induced matching of G. Then by
Corollary 3.4,
ld I(G) ≥ ld(x1 y1 , . . . , xm ym ) = m − 1 = indmatch(G) − 1,
where the second equality follows from direct inspection. The same proof works for the regularity.

It is of interest to find good upper bounds for the linearity defect of edge ideals in terms of
the combinatorics of their associated graphs. A trivial bound exists: using Taylor’s resolution
[18, Section 7.1], we have that ld I(G) is not larger than the number of edges of G minus 1.
4. Morphisms which induce trivial maps of Tor
4.1. Exact sequence estimates. The following result will be employed several times in the
sequel. It was proved using Şega’s interpretation of the linearity defect in terms of Tor modules
[36, Theorem 2.2].
Lemma 4.1 (Nguyen, [29, Proposition 2.5 and Corollary 2.10]). Let (R, m, k) be a noetherian
local ring. Let 0 −→ M −→ P −→ N −→ 0 be an exact sequence of finitely generated R-modules.
Denote
R
dP = inf{m ≥ 0 : TorR
i (k, M) −→ Tori (k, P ) is the trivial map for all i ≥ m},
R
dN = inf{m ≥ 0 : TorR
i (k, P ) −→ Tori (k, N) is the trivial map for all i ≥ m},
R
dM = inf{m ≥ 0 : TorR
i+1 (k, N) −→ Tori (k, M) is the trivial map for all i ≥ m}.

(i) There are inequalities
ldR P ≤ max{ldR M, ldR N, min{dM , dN }},
ldR N ≤ max{ldR M + 1, ldR P, min{dM + 1, dP }},
ldR M ≤ max{ldR P, ldR N − 1, min{dP , dN − 1}}.
(ii) If moreover P is a free module, then ldR M = ldR N − 1 if ldR N ≥ 1 and ldR M = 0 if
ldR N = 0.
Remark 4.2. Unfortunately, in general without the correcting terms dM , dN , dP , none of the
“simplified” inequalities
ldR P ≤ max{ldR M, ldR N},
ldR N ≤ max{ldR M + 1, ldR P },
ldR M ≤ max{ldR P, ldR N − 1}.
is true. See [29, Example 2.9] for details.

10

HOP D. NGUYEN AND THANH VU

We state now the main technical result of this section. Although the second inequality will
not be employed much in the sequel, it might be of independent interest.
φ

Proposition 4.3. Let (R, m, k) be a noetherian local ring. Let M −→ P be an injective morTorR (k,φ)

i
phism of finitely generated R-modules, and N = Coker φ. Assume that TorR
i (k, M) −−−−−→
R
Tori (k, P ) is the trivial map for all i ≥ max{ldR M, ldR P − 1}. Then there are inequalities:

ldR N ≤ max{ldR M + 1, ldR P },
ldR P ≤ max{ldR M, ldR N}.
If additionally, the map TorR
i (k, φ) is trivial for all i ≥ 0, then there is one further inequality
ldR M ≤ max{ldR P, ldR N − 1}.
Proof. We have an exact sequence of R-modules
0 −→ M −→ P −→ N −→ 0.
Consider the number
dP = inf{m ≥ 0 : TorR
i (k, φ) is the trivial map for all i ≥ m}.
By Lemma 4.1, there are inequalities
ldR N ≤ max{ldR P, ldR M + 1, dP },
ldR M ≤ max{ldR P, ldR N − 1, dP }.
By the hypothesis, dP ≤ max{ldR M, ldR P − 1}. Hence ldR N ≤ max{ldR M + 1, ldR P }. In the
second part of the statement, dP = 0, hence ldR M ≤ max{ldR P, ldR N − 1}.
It remains to show that if dP ≤ max{ldR M, ldR P − 1} then ldR P ≤ max{ldR M, ldR N}.
If ldR P ≤ ldR M, then we are done. Assume that ldR P = s ≥ ldR M + 1, then s ≥ 1.
Let F, G be the minimal free resolution of M, P , respectively. Let ϕ : F −→ G be a lifting of
φ : M −→ P . By the hypothesis, ϕ ⊗R k is the zero map for all i ≥ s − 1, hence ϕ(Fi ) ⊆ mGi
for all such i.
The mapping cone of ϕ is a free resolution of N. Let L be this mapping cone, then L =
G ⊕ F [−1]. Note that L is not necessarily minimal. Consider the complex
H = L≥s−1 : · · ·
/

Li
/

Li−1
/

···
/

Ls
/

Ls−1
/

0,

and U = Coker(Ls → Ls−1 ). Let Σs−1 U denote the complex with U in homological position
s − 1 and 0 elsewhere. Then H is a minimal free resolution of Σs−1 U, as ϕ(Fi ) ⊆ mGi for all
i ≥ s − 1.
It is enough to show that ldR (Σs−1 U) ≥ s, namely ldR U ≥ 1. Indeed, using the fact that
ldR U ≥ 1 and applying repeatedly Lemma 4.1(ii) for the complex
0
/

U
/

Ls−2
/

···
/

L1
/

L0
/

N
/

0,

we obtain ldR N = ldR U + s − 1 ≥ s. This gives us ldR P ≤ ldR N, as desired.
Since Hs (linR G) 6= 0, there exists a cycle u ∈ mi Gs /(mi+1 Gs ) in (linR G)s which is not a
boundary of linR G (where i ≥ 0). Let us show that the cycle
mi Gs M mi Fs−1
,
(u, 0) ∈ i+1
m Gs
mi+1 Fs−1

LINEARITY DEFECT OF EDGE IDEALS

11

in (linR H)s is not a boundary of linR H. Assume the contrary is true. Denoting by ∂ F , ∂ G , ∂ H
the differential of F, G, H, respectively, then there exists
mi−1 Gs+1 M mi−1 Fs
⊆ (linR H)s+1
(u′, v ′ ) ∈
mi Gs+1
mi Fs
such that
(u, 0) = ∂ H (u′ , v ′ ) = (∂ G (u′ ) + ϕ(v ′), ∂ F (v ′ )).
We have ∂ F (v ′ ) = 0. But v ′ ∈ (linR F )s and s ≥ ldR M + 1, so v ′ − ∂ F (v ′′ ) ∈ mi Fs for some
v ′′ ∈ mi−2 Fs+1 . Applying ϕ, we obtain
ϕ(v ′ ) − ∂ G (ϕ(v ′′ )) = ϕ(v ′ ) − ϕ(∂ F (v ′′ )) ∈ mi ϕ(Fs ).
Observe that ϕ(Fs ) ⊆ mGs by the above argument. Hence the last chain gives ϕ(v ′ ) ≡ ∂ G (ϕ(v ′′ ))
modulo mi+1 Gs .
Combining the last statement with the equality u = ∂ G (u′ ) + ϕ(v ′), we have the following
congruence modulo mi+1 Gs :
0 ≡ u − ∂ G (u′ ) − ϕ(v ′ ) ≡ u − ∂ G (u′ − ϕ(v ′′ )).
Recall that v ′′ ∈ mi−2 Fs+1 , hence ϕ(v ′′ ) ∈ mi−2 ϕ(Fs+1 ) ⊆ mi−1 Gs+1 . The last inclusion follows
from the fact that ϕ(Fi ) ⊆ mGi for i ≥ s − 1.
Hence u ∈ mi Gs /(mi+1 Gs ) equals to the image of u′ − ϕ(v ′′ ) ∈ mi−1 Gs+1 /(mi Gs+1 ). This
contradicts with the condition that u is not a boundary of linR G. Hence (u, 0) is not a boundary
of linR H, and Hs (linR H) 6= 0, as desired.
The last fact yields ldR (Σs−1 U) ≥ s, finishing the proof.

4.2. Betti splittings. Let (R, m, k) be a noetherian local ring. For a finitely generated Rmodule M, denote βi (M) = dimk TorR
i (k, M) its i-th Betti number. Observe that β0 (M) equals
the minimal number of generators of M. The following statement is an analog of [9, Proposition
2.1] and admits the same proof.
Lemma 4.4. Let (R, m, k) be a noetherian local ring and I, J, K ⊆ m are ideals such that
I = J + K. The following statements are equivalent:
R
R
(i) for all i ≥ 0, the natural maps TorR
i (k, J ∩ K) −→ Tori (k, J) and Tori (k, J ∩ K) −→
TorR
i (k, K) are trivial;
(ii) for all i ≥ 0, the equality
βi (I) = βi (J) + βi (K) + βi−1 (J ∩ K)
holds;
(iii) the mapping cone construction for the map J ∩ K −→ J ⊕ K yields a minimal free
resolution of I.
The following concept is particularly useful to our purpose. It is a straightforward generalization of the notion introduced by Francisco, Hà, and Van Tuyl in [9, Definition 1.1]. Its
modification for graded algebras and homogeneous ideals is routine.
Definition 4.5. Let (R, m, k) be a noetherian local ring and I ⊆ m an ideal. A decomposition
I = J + K of I, where J, K ⊆ m are ideals such that β0 (I) = β0 (J) + β0 (K), is called a Betti
splitting if one of the equivalent conditions in Lemma 4.4 holds.

12

HOP D. NGUYEN AND THANH VU

Remark 4.6. Strictly speaking, we do not need the condition β0 (I) = β0 (J) + β0 (K) in Definition
4.5 because of Lemma 4.4: in part (ii) of that lemma, choosing i = 0, we get β0 (I) = β0 (J) +
β0 (K). However, we include this condition to stress the special feature of the decomposition of
I as J + K.
We record the following example of a Betti splitting for the sake of clarity.
Example 4.7. Let (R1 , m), (R2 , n) be standard graded k-algebras and J ⊆ m, K ⊆ n be homogeneous ideals. Let I = J + K ⊆ R = R1 ⊗k R2 . We claim that the decomposition I = J + K is a
Betti splitting.
First, notice the following fact: Let M, N be finitely generated graded modules over R1 , R2 ,
respectively. Let FM , FN be the minimal free resolutions of M, N over R1 , R2 . Then FM ⊗k FN
is a minimal free resolution of M ⊗k N over R. Next, consider the short exact sequence
J ∼
R2
0 −→ JK −→ J −→
−→ 0.
= J ⊗k
JK
K
Let F and G be the minimal free resolutions of J and R2 /K over R1 and R2 , in that order.
The map F −→ F ⊗k G naturally yields a lifting of the natural map J −→ J ⊗k (R2 /K). This
R
implies that the map TorR
i (k, J) −→ Tori (k, J/(JK)) is injective for all i ≥ 0. From the above
R
exact sequence we get Tori (k, JK) −→ TorR
i (k, J) is trivial for all i ≥ 0. It is an elementary
R
fact that JK = J ∩ K in R, thus the map TorR
i (k, J ∩ K) −→ Tori (k, J) is also trivial for i ≥ 0.
R
R
Similar arguments apply for the map Tori (k, J ∩ K) −→ Tori (k, K), hence the decomposition
I = J + K is a Betti splitting.
It is not hard to show that if R1 , R2 are polynomial rings and J, K are monomial ideals over
them, then the decomposition I = J + K is an Eliahou-Kervaire splitting in the sense of [9].
Given a Betti splitting I = J + K, the projective dimension and regularity (in the graded
case) of I can be read off from that of J, K and J ∩ K.
Corollary 4.8 (See Hà and Van Tuyl [14, Theorem 2.3]). Let (R, m) be a noetherian local ring
and I ⊆ m an ideal with a Betti splitting I = J + K. Then there is an equality
pdR I = max{pdR J, pdR K, pdR (J ∩ K) + 1}.
If moreover R is a standard graded k-algebra and I, J, K are homogeneous ideals then we also
have
regR I = max{regR J, regR K, regR (J ∩ K) − 1}.
Proof. Straightforward from (the graded analog of) Lemma 4.4(ii).



Interestingly, the linearity defect stays under control as well in the presence of a Betti splitting.
Theorem 4.9. Let (R, m) be a noetherian local ring, I ⊆ m an ideal with a Betti splitting
I = J + K. Then there are inequalities
ldR I ≤ max{ldR J, ldR K, ldR (J ∩ K) + 1},
max{ldR J, ldR K} ≤ max{ldR (J ∩ K), ldR I},
ldR (J ∩ K) ≤ max{ldR J, ldR K, ldR I − 1}.
Proof. Applying Proposition 4.3 to the natural inclusion J ∩ K −→ J ⊕ K, we get the desired
conclusion.


LINEARITY DEFECT OF EDGE IDEALS

13

We do not know any example of a Betti splitting I = J + K for which the inequality
max{ldR J, ldR K} ≤ ldR I does not hold.
A class of Betti splittings is supplied by the following
Proposition 4.10. Let (R, m) be a noetherian local ring and I ⊆ m an ideal. Let J, L ⊆ m
be ideals and 0 6= y ∈ m be an element such that I = J + yL and the following conditions are
satisfied:
(i) L is a Koszul ideal,
(ii) J ∩ L ⊆ mL,
(iii) y is a regular element w.r.t. (R/J),
(iv) y is a regular element w.r.t. J and L, e.g. R is a domain.
Then the decomposition I = J + yL is a Betti splitting. Moreover, there are inequalities
ldR I ≤ max{ldR J, ldR (J ∩ L) + 1},
ldR J ≤ max{ldR (J ∩ L), ldR I},
ldR (J ∩ L) ≤ max{ldR J, ldR I − 1}.
The following lemma is useful for the proof of Proposition 4.10 as well as that of Theorem 5.5.
φ

Lemma 4.11 (Nguyen, [29]). Let (R, m) be a noetherian local ring, and M −→ P be a morphism
of finitely generated R-modules. Then the following statements hold:
R
(a) If for some ℓ ≥ ldR M, the map TorR
i (k, M) −→ Tori (k, P ) is injective at i = ℓ, then
that map is also injective for all i ≥ ℓ.
(a1) In particular, if M is a Koszul module and φ−1 (mP ) = mM then the natural map
R
TorR
i (k, M) −→ Tori (k, P ) is injective for all i ≥ 0.
R
(b) If for some ℓ ≥ ldR P , the map TorR
i (k, M) −→ Tori (k, P ) is trivial at i = ℓ, then that
map is also trivial for all i ≥ ℓ.
(b1) In particular, if P is a Koszul module and φ(M) ⊆ mP then the map TorR
i (k, M) −→
TorR
(k,
P
)
is
trivial
for
all
i
≥
0.
i
Proof. For (a) and (b), see [29, Lemma 2.8].
R
For (a1), note that if φ−1 (mP ) = mM then the map TorR
i (k, M) −→ Tori (k, P ) is injective at
i = 0. Since M is Koszul, the conclusion follows from (a). Similar arguments work for (b1). 
Proof of Proposition 4.10. Consider the following short exact sequence, in which the equality
holds because of the assumption (iii):
0
/

J ∩ yL = y(J ∩ L)
/

J ⊕ yL
/

I
/

0.

R
R
Since J ∩ L ⊆ J, the map TorR
i (k, y(J ∩ L)) → Tori (k, J) factors through Tori (k, yJ) →
R
R
TorR
i (k, J). The last map is trivial since y is J-regular. Hence Tori (k, y(J ∩ L)) → Tori (k, J)
is also the trivial map.
Since y(J ∩ L) ∼
= L (by the assumption (iv)), the map TorR
= J ∩ L, yL ∼
i (k, y(J ∩ L)) →
R
R
R
Tori (k, yL) can be identified with the map Tori (k, J ∩ L) → Tori (k, L). Since L is Koszul
and J ∩ L ⊆ mL, the last map is trivial by Lemma 4.11(b1). Therefore TorR
i (k, y(J ∩ L)) →
R
Tori (k, yL) is also the trivial map. This means that I = J + yL is a Betti splitting.
For the remaining inequalities, note that J ∩ yL = y(J ∩ L) ∼
= J ∩ L, so Theorem 4.9 and the
fact that ldR L = 0 yield the desired conclusion.


14

HOP D. NGUYEN AND THANH VU

Let R = k[x1 , . . . , xn ] be a polynomial ring, I a monomial ideal and y one of the variables.
The ideal I can be written as I = J + yL, where J is generated by monomials in I which are
not divisible by y and yL is the ideal generated by the remaining generators of I. If y does not
divide any minimal monomial generator of I, then J = I, L = 0. Following [9], we say that the
unique decomposition I = J + yL is the y-partition of I.
Among other things, the following result generalizes the second statement of [9, Corollary 2.7].
It will be employed in Section 6.
Corollary 4.12. Let R = k[x1 , . . . , xn ] be a polynomial ring over k, where n ≥ 1. Let y be one
of the variables. Let I be a monomial ideal and I = J + yL its y-partition. Assume that L is
Koszul. Then I = J + yL is a Betti splitting and there are inequalities
ldR I ≤ max{ldR J, ldR (J ∩ L) + 1},
ldR J ≤ ldR I,
ldR (J ∩ L) ≤ max{ldR J, ldR I − 1}.
In particular, either ldR I = ldR J ≥ ldR (J ∩ L), or ldR I = ldR (J ∩ L) + 1 ≥ ldR J + 1.
Proof. It is straightforward to check that the conditions of Proposition 4.10 are satisfied. Hence
the first and third inequalities follow. The second one is a consequence of Lemma 3.3. The last
statement is an immediate consequence of the three inequalities.

5. Weakly chordal graphs and co-two-pairs
The following notion will be important to inductive arguments with edge ideals of weakly
chordal graphs.
Definition 5.1. Two vertices x, y of a graph G form a two-pair if they are not adjacent and
every induced path connecting them is of length 2. If x and y form a two-pair of Gc then we say
that they are a co-two-pair.
Clearly if two vertices form a co-two-pair then they are adjacent. By abuse of terminology,
we also say that xy is a two-pair (or co-two-pair) of G if the pair x, y is so.
Recall that a subset of vertices of a graph G is called a clique if every two vertices in that
subset are adjacent. The existence of two-pairs is guaranteed by the following result.
Lemma 5.2 (Hayward, Hoàng, Maffray [16, The WT Two-Pair Theorem, Page 340]). If G is a
weakly chordal graph which is not a clique, then G contains a two-pair.
A useful property of co-two-pairs is the following
Lemma 5.3. If xy is a co-two-pair of a graph G, then any induced matching of G \ xy is also
an induced matching of G. In particular, indmatch(G \ xy) ≤ indmatch(G).
Proof. It suffices to prove the first part. Assume the contrary, there exists an induced matching
of G \ xy which is not an induced matching of G. Then necessarily, there are two edges in this
matching of the form xu and yv. But then in Gc , we have an induced path of length two xvuy.
This contradicts the assumption that xy is a co-two-pair. The proof is concluded.

Another simple but useful property of co-two-pairs is the following

LINEARITY DEFECT OF EDGE IDEALS

15

Lemma 5.4. Let G be a weakly chordal graph, and xy be a co-two-pair of G. Then G \ xy is
also weakly chordal.
Proof. From the definition of weak chordality, that G is weakly chordal is equivalent to Gc being
weakly chordal. Note that (G \ xy)c is the addition of the edge xy to Gc . By [37, Edge addition
lemma, Page 185], the graph (G \ xy)c is weakly chordal. Therefore G \ xy is weakly chordal
itself.

Recall that a graph G is said to be weakly chordal if both G and Gc have no induced cycle of
length 5 or larger. We can now prove Theorem 1.2 from the introduction.
Theorem 5.5. Let G be a weakly chordal graph with at least one edge. Then:
(i) For any co-two-pair e in G, the decomposition I(G) = (e) + I(G \ e) is a Betti splitting.
(ii) There is an equality ld I(G) = indmatch(G) − 1.
We remark that the argument below yields a new proof to the implication (ii) =⇒ (i) of
Theorem 2.3 (Fröberg’s theorem). The reverse implication follows easily from Corollary 3.4 and
Lemma 6.1.
Proof of Theorem 5.5. For simplicity, whenever possible we will omit the obvious superscripts
of Tor modules. Thanks to Corollary 3.2, we will systematically omit subscripts in writing
regularity and linearity defect of ideals. Since (e) has 2-linear resolution and (e) ∩ I(G \ e) is
generated in degree at least 3, the map
Tori (k, (e) ∩ I(G \ e)) −→ Tori (k, (e))
is trivial for all i ≥ 0. Hence to prove that I(G) = (e) + I(G \ e) is a Betti splitting, it suffices
to prove that the map Tori (k, (e) ∩ I(G \ e)) −→ Tori (k, I(G \ e)) is trivial for all i ≥ 0.
We prove by induction on |E(G)| and indmatch(G) the following stronger result.
Claim: Let G be a weakly chordal graph with at least one edge. Then the following statements
hold:
(S1) for any co-two-pair e in G, the natural map
Tori (k, (e) ∩ I(G \ e)) −→ Tori (k, I(G \ e))
is trivial for all i ≥ 0,
(S2) ld I(G) = indmatch(G) − 1, and,
(S3) reg I(G) = indmatch(G) + 1.
If G has only one edge then the statements are clear. Assume that G has at least 2 edges and
indmatch(G) = 1. Let e = xy and consider the exact sequence
0
/

(xy)(I(G \ e) : xy)
/

I(G \ e) ⊕ (xy)
/

I(G)
/

0,

Let y1 , . . . , yp be elements of the set N(x) ∪ N(y) \ {x, y}. Since indmatch(G) = 1, any edge of
G \ e contains at least a neighbor of either x or y. Therefore I(G \ e) : xy = (y1 , . . . , yp ). Clearly
p ≥ 1, so the first term in the above exact sequence has regularity
reg(y1 , . . . , yp ) + 2 = 3.
By Lemmas 5.3 and 5.4, G \ e is weakly chordal of induced matching number 1. Hence by the
induction hypothesis, I(G \ e) has 2-linear resolution. From the last exact sequence, we deduce

16

HOP D. NGUYEN AND THANH VU

that reg I(G) ≤ 2, proving (S2) and (S3). Since (e) ∩ I(G \ e) is generated in degree at least 3
and reg I(G \ e) = 2, statement (S1) is true by inspecting degrees. Therefore the case |E(G)| ≥ 2
and indmatch(G) = 1 was established.
Now assume that |E(G)| ≥ 2 and indmatch(G) ≥ 2. We divide the remaining arguments into
several steps.
Step 1: We derive statements (S2) and (S3) by assuming that the statement (S1) is true.
Since Gc is not a clique, by Lemma 5.2, there exists a co-two-pair xy in G. Denote e =
xy, W = I(G \ e). Consider the short exact sequence
0
/

(e) ∩ W
/

W ⊕ (e)
/

I(G)
/

0.

(5.1)

Denote by L the ideal generated by the variables in N(x) ∪ N(y) \ {x, y}. Denote by H the
induced subgraph of G on the vertex set G \ (N(x) ∪ N(y)). Then
(e) ∩ W = e(W : e) = e(L + I(H)) ∼
= (L + I(H)) (−2),
We have indmatch(H) ≤ indmatch(G) − 1, since we can add xy to any induced matching of H
to obtain a larger induced matching in G. Since H is an induced subgraph of G, it is weakly
chordal. Using [30, Lemma 4.10(ii)] and the induction hypothesis for H, we obtain the first and
second equality, respectively, in the following display
ld((e) ∩ W ) = ld I(H) = indmatch(H) − 1 ≤ indmatch(G) − 2.
Similarly, there is a chain
reg((e) ∩ W ) = reg(L + I(H)) + 2 = reg I(H) + 2 = indmatch(H) + 3 ≤ indmatch(G) + 2.
The second equality in the chain holds since I(H) and L live in different polynomial subrings.
By Lemma 5.4, G \ e is again weakly chordal. Now there is a chain
ld W = ld I(G \ e) = indmatch(G \ e) − 1 ≤ indmatch(G) − 1,

(5.2)

in which the second equality follows from the induction hypothesis, the last inequality from
Lemma 5.3. Similarly, the induction hypothesis gives
reg W = indmatch(G \ e) + 1 ≤ indmatch(G) + 1.
Since (S1) was assumed to be true, the decomposition I(G) = (e) + I(G \ e) is a Betti splitting.
So using Theorem 4.9, we get
ld I(G) ≤ max{ld((e) ∩ W ) + 1, ld W, ld(e)} ≤ indmatch(G) − 1.
Together with Corollary 3.5, we get (S2).
From the sequence (5.1), we also see that
reg I(G) ≤ max{reg((e) ∩ W ) − 1, reg W, reg(e)} ≤ indmatch(G) + 1.
The reverse inequality is true by Corollary 3.5, thus we obtain (S3).
Step 2: Set g = indmatch(G), then g ≥ 2 by our working assumption. In order to prove (S1), it
suffices to prove the following weaker statement: the map
Tori (k, (e) ∩ W ) −→ Tori (k, W )
is trivial for all i ≤ g − 1.

LINEARITY DEFECT OF EDGE IDEALS

17

Indeed, since e is a co-two-pair, by Lemma 5.4, we get that G \ e is weakly chordal. Furthermore, similarly to the chain (5.2) in Step 1, we have ld W = indmatch(G \ e) − 1 ≤ g − 1.
Combining the last inequality with the statement, we deduce that
Tori (k, (e) ∩ W ) −→ Tori (k, W )
is trivial for all i ≤ ld W . An application of Lemma 4.11(b) for the map (e) ∩ W −→ W implies
that
Tori (k, (e) ∩ W ) −→ Tori (k, W )
is also trivial for all i ≥ ld W .
Step 3: It remains to prove the statement that the map
φ : Tori (k, (e) ∩ W ) −→ Tori (k, W )
is trivial for i ≤ g − 1. Since G \ e is weakly chordal and indmatch(G \ e) ≤ g, we infer from the
induction hypothesis for G \ e that
reg W = reg I(G \ e) = indmatch(G \ e) + 1 ≤ g + 1.
Hence it suffices to show that the map
φj

Tori (k, (e) ∩ W )j −→ Tori (k, W )j
is trivial for all j ≤ i + g + 1 ≤ 2g.
Since (e)∩W and W are squarefree monomial ideals, it suffices to prove the claim for squarefree
multidegrees; see [11, Theorem 2.1 and Lemma 2.2]. So we will show that φm = 0 for each
squarefree monomial m of degree ≤ 2g. Furthermore, by the just cited results, it is harmless to
assume that e divides m and supp(m) ⊆ V (G).
Let G† be the induced subgraph of G on the vertex set supp m, and W≤m the submodule of W
generated by elements whose multidegree divides m. By [33, Proposition 3.10], there is a chain
TorR (k, W )m ∼
= TorR (k, W≤m )m = TorR (k, I(G† \ e))m
i

i

i

for all i ≥ 0. For the same reason,
R
†
∼
TorR
i (k, (e) ∩ W )m = Tori (k, (e) ∩ I(G \ e))m

for all i ≥ 0. Note that e is automatically a co-two-pair of G† , and |V (G† )| = | supp(m)| ≤ 2g.
Denote S = k[xi | xi ∈ supp(m)]. If indmatch(G† ) ≤ g − 1 then as G† is also weakly chordal,
the induction hypothesis for G† implies that the map
TorSi (k, (e) ∩ I(G† \ e)) −→ TorSi (k, I(G† \ e))
is trivial for all i ≥ 0. Since S −→ R is a faithfully flat extension, we also get that
R
†
†
TorR
i (k, (e) ∩ I(G \ e)) −→ Tori (k, I(G \ e))

is trivial for all i ≥ 0. In particular, the last map is trivial for i ≤ g − 1, which is the desired
conclusion.
If indmatch(G† ) ≥ g, then having at most 2g vertices, there is no possibility for G† other than
being a gK2 . After relabeling the vertices of G† , assume that G† has vertices x1 , . . . , xg , z1 , . . . , zg ,
edges x1 z1 , . . . , xg zg , and e = x1 z1 . Denote J = (x2 z2 , . . . , xg zg ) ⊆ S = k[x1 , . . . , xg , z1 , . . . , zg ].
What we have to show is
TorSi (k, (x1 z1 ) ∩ J) −→ TorSi (k, J)

18

HOP D. NGUYEN AND THANH VU

is trivial for i ≤ g − 1. This is easy: in fact we prove the claim for all i ≥ 0. First note that
(x1 z1 ) ∩ J = (x1 z1 )J, and x1 z1 is J-regular. Hence the map
TorSi (k, (x1 z1 ) ∩ J) −→ TorSi (k, J)
is nothing but the multiplication with x1 z1 of TorSi (k, J). The latter is a trivial map.
This finishes the induction step and the proof of the theorem.



Remark 5.6. Let R = k[x1 , . . . , xn ] be a standard graded polynomial ring over k (where n ≥ 0),
and I a monomial ideal of R. Let J, K be monomial ideals of R such that I = J +K. A sufficient
condition for the decomposition I = J + K to be a Betti splitting is that I is a splittable ideal
with the (Eliahou-Kervaire) splitting as J + K; see [15, Definition 2.3 and Theorem 2.4].
Following Hà and Van Tuyl [15, Definition 3.1], we say that an edge e of a graph G is a splitting
edge if the decomposition I(G) = (e)+I(G\e) makes I(G) into a splittable ideal. Splitting edges
(of hypergraphs) are characterized in [15, Theorem 3.2]. By the above discussion, any splitting
edge yields a Betti splitting in the sense that if e is a splitting edge of G, then I(G) = (e)+I(G\e)
is a Betti splitting.
Theorem 5.5(i) produces a new class of Betti splittings which do not come from splitting
edges. For example, let G = C4 and e be any of its edge. The conditions of Theorem 5.5 are
satisfied, so I(G) = (e) + I(G \ e) is a Betti splitting. Nevertheless, it is easy to check that e is
not a splitting edge of G since it does not satisfy the condition specified in [15, Theorem 3.2].
6. Cycles
The linearity defect of edge ideals of anticycles is known; we recall the statement here. The
following lemma is contained in [32, Theorem 5.1], which calls upon the case d = 2 of Example
4.7 in the same paper. We give a brief argument for the sake of clarity.
Lemma 6.1 (See Okazaki and Yanagawa [32, Theorem 5.1]). Let G be the anticycle of length
n ≥ 4. Then ld I(G) = n − 3.
Proof. It is well-known, e.g. from [3, Theorem 5.6.1], that R/I(G) is Gorenstein of dimension
2. Therefore the resolution of R/I(G) is symmetric of length n − 2. In particular, the last
differential matrix of the minimal free resolution F of R/I(G) is a column of elements of degree
2. This implies that Hn−2 (linR F ) 6= 0. Therefore ldR R/I(G) = n − 2.
Since n − 2 ≥ 2, the last equality implies that ldR I(G) = n − 3.

The main result of this section is
Theorem 6.2. Let Cn be the cycle of length n, where n ≥ 3. Then ld I(Cn ) = 2⌊ n−2
⌋.
3
Proof. We prove by induction on n. For simplicity, we omit the subscript concerning the ring in
the notation of linearity defect. The case n ∈ {3, 4} is a straightforward application of Fröberg’s
theorem. The case n = 5 follows from Lemma 6.1.
Assume that the conclusion is true up to n ≥ 5, we establish it for n + 1. Let Pn , as usual, be
the path with edges x1 x2 , x2 x3 , . . . , xn−1 xn . By Corollary 4.12 we have that the xn+1 -partition
I(Cn+1 ) = I(Pn ) + xn+1 (x1 , xn ) is a Betti splitting since (x1 , xn ) is Koszul. By Corollary 4.12
we also get
ld I(Cn+1 ) ≤ max{ld I(Pn ), ld (I(Pn ) ∩ (x1 , xn )) + 1},
ld (I(Pn ) ∩ (x1 , xn )) ≤ max{ld I(Pn ), ld I(Cn+1 ) − 1}.

(6.1)
(6.2)

LINEARITY DEFECT OF EDGE IDEALS

19

Denote I = I(Pn ) ∩ (x1 , xn ). Then
I = x1 (x2 , x3 x4 , x4 x5 , . . . , xn−2 xn−1 ) + xn (x2 x3 , x3 x4 , . . . , xn−3 xn−2 , xn−1 ).
By abuse of notation, denote I(Pn−4 ) = (x3 x4 , x4 x5 , . . . , xn−3 xn−2 ). By convention, for n = 5,
I(P1 ) = 0. Denote J = (x2 , x3 x4 , x4 x5 , . . . , xn−2 xn−1 ) = (x2 , xn−2 xn−1 ) + I(Pn−4 ), and
L = (x2 x3 , x3 x4 , . . . , xn−3 xn−2 , xn−1 ) = (x2 x3 , xn−1 ) + I(Pn−4 ).
With the above notation, I = x1 J + xn L.
Claim: The decomposition I = x1 J + xn L is a Betti splitting.
Indeed, consider the exact sequence
0
/

x1 J ∩ xn L = x1 xn (J ∩ L)
/

x1 J ⊕ xn L
/

I
/

0.

R
R
Take i ≥ 0. The map TorR
i (k, x1 xn (J ∩ L)) → Tori (k, x1 J) factors through Tori (k, x1 xn J) →
TorR
i (k, x1 J), which is the trivial map. Hence the former map is also trivial. Arguing similarly
R
for the map TorR
i (k, x1 xn (J ∩ L)) → Tori (k, xn L), we get the claim.
∼
∼
Note that J = (x2 ) + I(Pn−3 ) and L = (xn−1 ) + I(Pn−3). Hence by [30, Lemma 4.10(ii)],

ld J = ld L = ld I(Pn−3).
Thanks to Corollary 7.5 (which is a direct consequence of Theorem 5.5), we then obtain


n−2
− 1.
ld J = ld L =
3
Furthermore, J ∩ L = (x2 x3 , x3 x4 , . . . , xn−2 xn−1 , x2 xn−1 ) ∼
= I(Cn−2 ). Hence by the induction
hypothesis,


n−4
ld(x1 J ∩ xn L) = ld(J ∩ L) = ld I(Cn−2 ) = 2
.
3
Since I = x1 J + xn L is a Betti splitting, Theorem 4.9 yields the inequalities
ld I ≤ max{ld J, ld L, ld(J ∩ L) + 1},
ld(J ∩ L) ≤ max{ld J, ld L, ld I − 1}.

(6.3)
(6.4)

Now we distinguish three cases according to whether n = 5, or n = 6, or n ≥ 7.
Case 1: Consider the case n = 5. Now J = (x2 , x3 x4 ), L = (x2 x3 , x4 ) and I = x1 J + x5 L =
(x1 x2 , x4 x5 , x1 x3 x4 , x2 x3 x5 ). Since J ∩ L = (x2 x3 , x3 x4 , x2 x4 ), we see from (6.3) that ld I ≤ 1.
Using (6.1), we obtain ld I(C6 ) ≤ 2.
Let U = (x1 x6 , x1 x2 , x2 x3 ), V = (x3 x4 , x4 x5 , x5 x6 ), then they are ideals with 2-linear resolutions. Clearly I(C6 ) = U + V . Obviously U ∩ V ⊆ mU and U ∩ V ⊆ mV , hence Lemma 4.11(b1)
implies that the decomposition I(C6 ) = U +V is a Betti splitting. Using Theorem 4.9, we obtain
an inequality
ld(U ∩ V ) ≤ ld I(C6 ) − 1.
If ld I(C6 ) < 2 then ld(U ∩ V ) = 0. On the other hand, (U ∩ V )h3i = (x1 x5 x6 , x2 x3 x4 ) does not
have 3-linear resolution. This is a contradiction. So ld I(C6 ) = 2, as desired.
Case 2: Consider the case n = 6. Arguing as in the case n = 5, we obtain ld I(C7 ) ≤ 2.
Let the presentation of I(C7 ) be F/M, where F = R(−2)7 has a basis e1 , . . . , e7 such that
ei maps to xi xi+1 for i = 1, . . . , 6 and e7 maps to x7 x1 . Since M ⊆ mF , obviously Mj = 0 for

20

HOP D. NGUYEN AND THANH VU

j ≤ 2. It is easy to check that the following 7 elements belong to k-vector space M3 and they
are k-linearly independent:
f1 = x3 e1 − x1 e2 , f2 = x4 e2 − x2 e3 , f3 = x5 e3 − x3 e4 , f4 = x6 e4 − x4 e5 ,
f5 = x7 e5 − x5 e6 , f6 = x1 e6 − x6 e7 , f7 = x2 e7 − x7 e1 .
There is an exact sequence of k-vector spaces 0 −→ M3 −→ F3 −→ I(C7 )3 −→ 0. It is not
hard to see that dimk F3 = 49 and dimk I(C7 )3 = 42, hence dimk M3 = 7. In particular, M3 is
generated by exactly the above elements.
Let N = Mh3i . If ld I(C7 ) ≤ 1 then M must be Koszul, hence N must have a 3-linear
resolution. Note that N is not a free module since we can check directly that
x4 x5 x6 x7 f1 + x1 x5 x6 x7 f2 + x1 x2 x6 x7 f3 + x1 x2 x3 x7 f4 + x1 x2 x3 x4 f5 + x2 x3 x4 x5 f6 + x3 x4 x5 x6 f7 = 0.
In particular, N has at least one non-trivial linear syzygy. So there exist linear forms a1 , . . . , a7
in R, not all of which are zero, such that
a1 f1 + · · · + a7 f7 = 0.
Looking at the coefficients of e1 and e2 , we get
a1 x3 = a7 x7 , a1 x1 = a2 x4 .
This implies that x7 and x4 divide a1 , which yields a1 = 0. From the two equations in the last
display, we deduce that a2 = a7 = 0.
Similarly, we get a3 = · · · = a6 = 0, a contradiction. Hence N does not have a 3-linear
resolution, and thus ld I(C7 ) ≥ 2. Hence ld I(C7 ) = 2, as desired.
 n−4 
>
Case
3:
Now
assume
that
n
≥
7.
Elementary
considerations
show
that
ld(J
∩
L)
=
2
3
 n−2 
−1 =
ld J
3
 n−4
 = ld L. Hence from the inequalities (6.3) and (6.4), we obtain ld I = ld(J ∩
L) + 1 = 2 3 + 1.




+ 1 > n−2
= ld I(Pn ) for all n ≥ 7. So inspecting
From the above discussions, ld I = 2 n−4
3
3
(6.1) and (6.2), we obtain




n−1
n−4
+2=2
.
ld I(Cn+1) = ld I + 1 = 2
3
3
The induction step and hence the proof is now completed.



7. Applications
7.1. Regularity. The proof of Theorem 5.5 yields the following consequence.
Corollary 7.1 (Woodroofe, [40, Theorem 14]). Let G be a weakly chordal graph with at least
one edge. Then there is an equality
reg I(G) = indmatch(G) + 1.
Remark 7.2. Woodroofe’s proof of his result depends on the Kalai-Meshulam’s inequality [23],
which asserts that for a polynomial ring R = k[x1 , . . . , xn ] (where n ≥ 1), and squarefree
monomial ideals I1 , . . . , Im (where m ≥ 2), there is an inequality
reg(I1 + I2 + · · · + Im ) ≤ reg I1 + reg I2 + · · · + reg Im − m + 1.

LINEARITY DEFECT OF EDGE IDEALS

21

However, the following example shows that there is no hope for a straightforward analog of the
Kalai-Meshulam’s inequality for linearity defect.
Example 7.3. Take I to be the edge ideal of the anticycle of length n where n ≥ 5. Let I1 be
the edge ideal of the induced subgraph of the anticycle on the vertex set {x1 , . . . , xn−1 }, and
I2 = (x2 xn , . . . , xn−2 xn ). Clearly I = I1 + I2 . Moreover ldR I1 = 0, since I1 is the edge ideal of a
co-chordal graph, and ldR I2 = 0 since I2 ∼
= (x2 , . . . , xn−2 ). On the other hand, by Lemma 6.1,
ldR (I1 + I2 ) = n − 3.
7.2. Chordal graphs. In view of Example 2.2, an immediate corollary of Theorem 5.5 is
Corollary 7.4. Let G be a chordal graph with at least one edge. Then there is an equality
ld I(G) = indmatch(G) − 1.
We can give a simplified proof of this result, using a Betti splitting statement in [15].
Alternative proof of Corollary 7.4. By Corollary 3.5, it is enough to show that
ld I(G) ≤ indmatch(G) − 1.
We use induction on |V (G)| and |E(G)|. The case G has at most 3 vertices is immediate. It is
equally easy if |E(G)| = 1. Assume that |V (G)| ≥ 4 and |E(G)| ≥ 2.
By a classical result due to Dirac, there exists a vertex of G whose neighbors form a clique
(such a vertex is called a simplicial vertex). Working with a connected component of G with at
least one edge if necessary, we can assume that the vertex in question has at least one neighbor.
Assume that x is a simplicial vertex and y is a vertex in N(x). By [15, Lemma 5.7(i)] and the
discussion in Remark 5.6, I(G) = (xy) + I(G \ xy) is a Betti splitting.
By Theorem 4.9, we obtain
ld I(G) ≤ max{ld I(G \ xy), ld(I(G \ xy) ∩ (xy)) + 1}.

(7.1)

Let L be the ideal generated by the variables in N(x) ∪ N(y) \ {x, y}. Let H be the induced
subgraph of G on the vertex set V (G) \ (N(x) ∪ N(y)). Then
I(G \ xy) ∩ (xy) = (xy)(I(G \ xy) : xy) = (xy)(L + I(H)).
In particular, [30, Lemma 4.10(ii)] yields the second equality in the following display
ld(I(G \ xy) ∩ (xy)) = ld(L + I(H)) = ld I(H).
Substituting in (7.1), it follows that
ld I(G) ≤ max{ld I(G \ xy), ld I(H) + 1}.
We know that G \ xy and H are also chordal graphs; see [15, Lemma 5.7]. Moreover, we have
indmatch(H) ≤ indmatch(G) − 1 as seen in the proof of Theorem 5.5.
It is routine to check that xy is a co-two-pair. Thus by Lemma 5.3, we obtain indmatch(G \
xy) ≤ indmatch(G). Now by the induction hypothesis,
ld I(G) ≤ max{ld I(G \ xy), ld I(H) + 1} ≤ max{indmatch(G \ xy) − 1, indmatch(H)},
which is not larger than indmatch(G) − 1. The proof is now completed.



Recall that G is called a forest if it contains no cycle. The connected components of a forest
are trees. As a consequence of Corollary 7.4, we get

22

HOP D. NGUYEN AND THANH VU

Corollary 7.5. Let G be a forest with at least one edge. Then ld I(G) = indmatch(G) − 1.
In particular, let Pn be the path of length n − 1 (where n ≥ 2), then ld I(Pn ) = ⌊ n−2
⌋.
3
Proof. For the first part, note that any forest is chordal. Hence Corollary 7.4 applies.
For the second, use the simple fact that indmatch(Pn ) = ⌊ n+1
⌋.
3



7.3. Linearity defect one. Now we prove Theorem 1.1 from the introduction. Together with
Theorem 2.3, the next result gives the extension of Fröberg’s theorem advertised in the abstract.
Theorem 7.6. Let G be a graph. Then ld I(G) = 1 if and only if G is weakly chordal and
indmatch(G) = 2.
Proof. For the “only if” direction: By Lemma 6.1 and Theorem 6.2, the linearity defect of any
cycle/anticycle of length at least 5 is greater than or equal to 2. Hence Corollary 3.4 implies
that G has to be weakly chordal. Obviously, for example by using Taylor’s resolution, we have
that any homogeneous syzygy of I(G) is either linear or quadratic, hence the first syzygy of
I(G) is generated in degree at most 4. But ld I(G) ≤ 1, so the first syzygy of I(G) is Koszul,
hence from Section 2.2, its regularity is also at most 4. As I(G) is generated in degree 2, this
implies that reg I(G) ≤ 3. But ld I(G) > 0, so reg I(G) = 3. By Corollary 7.1, we deduce that
indmatch(G) = 2, as desired.

The “if” direction follows from Theorem 5.5.
7.4. Projective dimension. First, recall that a graph G = (V, E) is called a bipartite graph if
(i) the vertex set V is a disjoint union of two subsets V1 and V2 ,
(ii) if two vertices are adjacent then they are not both elements of Vi for any i ∈ {1, 2}.
In this case, the decomposition of V as V1 ∪ V2 is called its bipartite partition. We also denote
G by (V1 , V2 , E) given a bipartite partition V1 ∪ V2 of the vertex set.
A bipartite graph G = (V1 , V2 , E) is called a complete bipartite graph if E = {{x, y} : x ∈
V1 , y ∈ V2 }.
In this section, we will use the notion of a strongly disjoint family of complete bipartite
subgraphs, introduced by Kimura [27], to compute the projective dimension of edge ideals of
weakly chordal graphs. For a graph G, we consider all families of (non-induced) subgraphs
B1 , . . . , Bg of G such that
(i) each Bi is a complete bipartite graph for 1 ≤ i ≤ g,
(ii) the graphs B1 , . . . , Bg have pairwise disjoint vertex sets,
(iii) there exist an induced matching e1 , . . . , eg of G for which ei ∈ E(Bi ) for 1 ≤ i ≤ g.
Such a family is termed a strongly disjoint family of complete bipartite subgraphs. We define
( g
)
X
d(G) = max
|V (Bi )| − g
i=1

where the maximum is taken over all the strongly disjoint families of complete bipartite subgraphs
B1 , . . . , Bg of G.
The following result is a generalization of [26, Theorem 4.1(1)] and [5, Corollary 3.3]; the
latter was reproved in [27, Corollary 5.3].
Theorem 7.7. Let G be a weakly chordal graph with at least one edge. Then there is an equality
pd I(G) = d(G) − 1.

LINEARITY DEFECT OF EDGE IDEALS

23

The inequality pd I(G) ≥ d(G) − 1 was established by Kimura’s work [27]. The following
lemma, which might be of independent interest, is the crux in proving the reverse inequality. We
are grateful to an anonymous referee for suggesting the main idea of the proof of the lemma.
Lemma 7.8. Let x1 x2 be a co-two-pair of a graph G. Then there is a complete bipartite subgraph
of G with the vertex set N(x1 ) ∪ N(x2 ) (the last union need not be the bipartite partition for that
subgraph).
Proof. Let V be the set N(x1 ) ∪ N(x2 ). Define the subsets V1,n and V2,n of V inductively on
n ≥ 0 as follows: V1,0 = {x1 }, V2,0 = {x2 }. For n ≥ 0, we let
V1,n+1 = V1,n ∪ {z ∈ V : V1,n 6⊆ N(z)},
and similarly
V2,n+1 = V2,n ∪ {z ∈ V : V2,n 6⊆ N(z)}.
Clearly V1,n ⊆ V1,n+1 and V2,n ⊆ V2,n+1 for all n ≥ 0. We set V1,−1 = V2,−1 = ∅ for systematic
reason. Our aim is to prove the following statements:
(i) V1,n ⊆ {z ∈ V : V2,n−1 ⊆ N(z)}, and V2,n ⊆ {z ∈ V : V1,n−1 ⊆ N(z)},
(ii) V1,n ∩ V2,n = ∅,
(iii) G has a complete bipartite subgraph with the bipartite partition V1,n ∪ V2,n .
Let us use induction on n. If n = 0, then (i) holds vacuously, while V1,0 = {x1 }, V2,0 = {x2 }
therefore (ii) and (iii) are also true.
Assume that the statements (i) – (iii) are true for n ≥ 0. We establish them for n + 1.
For (i): if (i) was not true, we can assume that V1,n+1 6⊆ {z ∈ V : V2,n ⊆ N(z)}. Choose
z ∈ V1,n+1 such that V2,n 6⊆ N(z). Clearly z ∈
/ V1,n because of the induction hypothesis for (iii).
Hence the definition of V1,n+1 forces V1,n 6⊆ N(z). Again the last non-containment implies that
z∈
/ V2,n .
As N(z) contains neither V1,n nor V2,n , we can choose xi,n ∈ Vi,n such that xi,n ∈
/ N(z) for
i = 1, 2.
By the definition of V1,n we can choose nr ≥ 0 such that x1,n ∈ V1,nr \ V1,nr −1 (recall that
V1,−1 = ∅). Set x1,nr = x1,n . Since x1,nr ∈ V1,nr \ V1,nr −1 , there exists x1,nr−1 ∈ V1,nr −1 such that
x1,nr and x1,nr−1 are not adjacent.
Continuing this argument, finally we find a sequence of indices 0 = n0 < n1 < · · · < nr ≤ n
and vertices x1 = x1,n0 , x1,n1 , . . . , x1,nr = x1,n such that x1,ni ∈ V1,ni \ V1,ni −1 for all 0 ≤ i ≤ r
and x1,ni and x1,ni+1 are not adjacent for 0 ≤ i ≤ r − 1.
Similarly, there exist a sequence of indices 0 = m0 < m1 < · · · < ms ≤ n and vertices
x2 = x2,m0 , x2,m1 , . . . , x2,ms = x2,n such that x2,mj ∈ V2,mj \ V2,mj −1 for all 0 ≤ j ≤ s and x2,mj
and x2,mj+1 are not adjacent for 0 ≤ j ≤ s − 1.
Note that we have a path, called P , with vertices
x1 = x1,n0 , x1,n1 , . . . , x1,nr = x1,n , z, x2,n = x2,ms , x2,ms−1 , . . . , x2,m0 = x2
connecting x1 and x2 in Gc with length r + s + 2 (see Figure 1). We claim that this is an induced
path and its length is > 2.
For the second part of the last claim, it suffices to observe that r and s cannot be both zero,
otherwise z ∈ V but z ∈
/ N(x1 ) ∪ N(x2 ), which is absurd. For the first part, note that as
z∈
/ V1,n ∪ V2,n , we have V1,n−1 ∪ V2,n−1 ⊆ N(z). Hence z is adjacent (in G) to all the vertices in

24

HOP D. NGUYEN AND THANH VU

x1 = x1,n0

x2,m0 = x2

x1,n1

x2,m1
..
.

..
.

x1,nr−1

x2,ms−1

x1,nr

x2,ms
z

Figure 1. The path P in Gc
P except x1,n and x2,n . Since G has a complete bipartite subgraph with vertex set V1,n ∪ V2,n , it
is clear that x1,ni is adjacent to x2,mj for all 0 ≤ i ≤ r, 0 ≤ j ≤ s.
Now consider 0 ≤ i, j ≤ r such that i ≤ j − 2. We wish to show that x1,ni and x1,nj are
adjacent. As x1,nj ∈ V1,nj \ V1,nj −1 , we see that V1,nj −2 ⊆ N(x1,nj ). Since i ≤ j − 2, clearly
ni ≤ nj − 2, hence x1,ni ∈ V1,nj −2 ⊆ N(x1,nj ). Therefore x1,ni and x1,nj are adjacent. Similarly,
for 0 ≤ i, j ≤ s with i ≤ j − 2, the vertices x2,mi and x2,mj are adjacent.
This shows that P is an induced path connecting x1 and x2 in Gc with length > 2. But then
we get a contradiction, since x1 x2 is a co-two-pair.
In other words, we have V1,n+1 ⊆ {z ∈ V : V2,n ⊆ N(z)} and similarly V2,n+1 ⊆ {z ∈ V :
V1,n ⊆ N(z)}. This finishes the induction step for (i).
For (ii): assume that there exists z ∈ V1,n+1 ∩ V2,n+1 . As we have seen,
V2,n+1 ⊆ {z ∈ V : V1,n ⊆ N(z)}.
So the definition of V1,n+1 yields z ∈ V1,n . Similarly, z ∈ V2,n , but then V1,n ∩ V2,n 6= ∅, a
contradiction. This finishes the induction step for (ii).
For (iii): taking z1 ∈ V1,n+1 and z2 ∈ V2,n+1 , we want to show that {z1 , z2 } ∈ E(G). First, assume
that z1 ∈ V1,n . From (i), we have the second inclusion in the following chain
z2 ∈ V2,n+1 ⊆ {z ∈ V : V1,n ⊆ N(z)},
hence z1 is adjacent to z2 . Hence it suffices to consider the case z1 ∈
/ V1,n and for the same
reason, we restrict ourselves to the case z2 ∈
/ V2,n .
Note that z1 ∈
/ V2,n since V1,n+1 ∩ V2,n ⊆ V1,n+1 ∩ V2,n+1 = ∅. Hence z1 ∈
/ V1,n ∪ V2,n , and the
same thing happens for z2 .
Assume that on the contrary, {z1 , z2 } ∈
/ E(G). As in the induction step for (i), we can
choose a sequence of indices 0 = n0 < · · · < nr ≤ n + 1 (where r ≥ 0) and elements x1 =
x1,n0 , x1,n1 , . . . , x1,nr = z1 such that x1,ni ∈ V1,ni \ V1,ni −1 for 0 ≤ i ≤ r and x1,ni and x1,ni+1
are not adjacent for 0 ≤ i ≤ r − 1. Similarly, we can choose a sequence of indices 0 = m0 <

LINEARITY DEFECT OF EDGE IDEALS

25

· · · < ms ≤ n + 1 (where s ≥ 0) and elements x2 = x2,m0 , x2,m1 , . . . , x2,ms = z2 with the similar
properties. Since z1 ∈
/ V1,n and x1 ∈ V1,n , we have that r ≥ 1. Analogously, s ≥ 1.
Since {z1 , z2 } ∈
/ E(G), we have a path
x1 = x1,n0 , x1,n1 , . . . , x1,nr = z1 , z2 = x2,ms , x2,ms−1 , . . . , x2,m0 = x2
of length r + s + 1 ≥ 3 connecting x1 and x2 in Gc . As in the induction step for (i), we see
that the last path is an induced path in Gc . Again this yields a contradiction since x1 x2 is a
co-two-pair. So {z1 , z2 } ∈ E(G), as desired. This finishes the induction step for (iii), so that all
the statements (i)–(iii) are true.
Since {V1,n }n≥0 and {V2,n }n≥0 are two monotonic sequences (with respect to inclusion) consisting of subsets of the finite set V , there exist q ≥ 0 such that V1,n = V1,n+1 , V2,n = V2,n+1 for
all n ≥ q.
If V = V1,q ∪ V2,q then we are done by statement (iii). Otherwise, consider an element
z ∈ V \ (V1,q ∪ V2,q ). We have z ∈
/ V1,q+1 = V1,q , so V1,q ⊆ N(z). Enlarging V2,q with all such
elements z of V , again we see that there is a complete bipartite subgraph of G with the vertex
set V . Hence the lemma is now proved.

Proof of Theorem 7.7. That pd I(G) ≥ d(G) − 1 follows from [27, Theorem 1.1]. We prove the
reverse inequality by induction on |E(G)|. If |E(G)| = 1 then there is nothing to do. Assume
that |E(G)| ≥ 2.
Let e = x1 x2 be a co-two-pair of G, which exists because of Lemma 5.2. Denote V =
N(x1 ) ∪ N(x2 ). Let L be the ideal generated by the variables in V \ {x1 , x2 } and H be the
induced subgraph of G on the vertex set G \ V . Again we have
I(G \ e) : x1 x2 = L + I(H).
Denote p = |V | − 2; note that p ≥ 0 since x1 , x2 ∈ V . If I(H) = 0 then L 6= 0 since |E(G)| ≥ 2.
From the exact sequence
0
/

(x1 x2 )(L + I(H))
/

I(G \ e) ⊕ (x1 x2 )
/

I(G)
/

0

(7.2)

we get that
pd I(G) ≤ max{pd I(G \ e), pd L + 1} = max{pd I(G \ e), p}.
Since G\e is again a weakly chordal graph, by the induction hypothesis pd I(G\e) ≤ d(G\e)−1 ≤
d(G) − 1. The last inequality follows from the fact that d(G \ e) ≤ d(G), which in turn follows
easily from Lemma 5.3.
By Lemma 7.8, there is an complete bipartite subgraph B1 of G with the vertex set V . Now
B1 has p + 2 vertices, hence by the definition of d(G), it follows that (p + 2) − 1 = p + 1 ≤ d(G).
Finally
pd I(G) ≤ max{pd I(G \ e), p} ≤ d(G) − 1,
as desired.
Assume that I(H) 6= 0. Since L and I(H) live in different polynomial subrings of R and L
has codimension p, we obtain
pd(L + I(H)) = pd I(H) + p.
Since H is weakly chordal with fewer edges than G, by the induction hypothesis
pd I(H) = d(H) − 1.

26

HOP D. NGUYEN AND THANH VU

Let B2 , . . . , Bg be a strongly disjoint family of complete bipartite subgraphs of H which realizes
d(H). Note that if e2 , . . . , eg form an induced matching of H, where ei ∈ Bi , then e, e2 , . . . , eg
is an induced matching in G. Therefore B1 , B2 , . . . , Bg is a strongly disjoint family of complete
bipartite subgraphs of G. In particular,
d(G) ≥ |V (B1 )| +

g
X

|V (Bi )| − g = p + 2 + d(H) − 1 = pd I(H) + p + 2.

i=2

All in all, we see that

pd(L + I(H)) = pd I(H) + p ≤ d(G) − 2.
As above pd I(G \ e) = d(G \ e) − 1 ≤ d(G) − 1. So from the exact sequence (7.2), we obtain
pd I(G) ≤ max{pd I(G \ e), pd(L + I(H)) + 1} ≤ d(G) − 1.
This finishes the induction and the proof of the theorem.



Remark 7.9. See also, e.g., [25], [26], [27], for more results about the relationship between the
projective dimension of I(G) and invariants coming from families of complete bipartite subgraphs
of G.
8. Characteristic dependence
It is well-known that the regularity of edge ideals depend on the characteristic of the field. In
fact Katzman [24] shows that if R = k[x1 , . . . , xn ] is a polynomial ring of dimension n ≤ 10, then
any edge ideal on the vertex set {x1 , . . . , xn } has characteristic-independent regularity. On the
other hand, from dimension 11 onward, there are examples of edge ideals with characteristicdependent regularity.
The following example is taken from Katzman’s paper [24, Page 450]. It comes from a triangulation of the projective plane P2k . The Macaulay2 package [31] is employed in our various
computations of the linearity defect.
Example 8.1. Let I ⊆ k[x1 , . . . , x11 ] be the following edge ideal:
I = (x1 x2 , x1 x6 , x1 x7 , x1 x9 , x2 x6 , x2 x8 , x2 x10 , x3 x4 , x3 x5 , x3 x7 , x3 x10 ,
x4 x5 , x4 x6 , x4 x11 , x5 x8 , x5 x9 , x6 x11 , x7 x9 , x7 x10 , x8 x9 , x8 x10 , x8 x11 , x10 x11 ).
Computations with Macaulay2 [12] show that ld I = 3 if char k = 0 and ld I = 7 if char k = 2.
So for any m ≥ 0, applying [30, Lemma 4.10], we see that the edge ideal I +(y1 z1 , . . . , ym zm ) ⊆
k[x1 , . . . , x11 , y1 , . . . , ym , z1 , . . . , zm ] has linearity defect ld I + ld(y1 z1 , . . . , ym zm ) + 1 = m + 3 if
char k = 0 and m + 7 if char k = 2. Moreover, we can replace I + (y1 z1 , . . . , ym zm ) by the edge
ideal of a connected graph using Lemma 8.2. Indeed, take a new vertex y, then the edge ideal
I + (y1 z1 , . . . , ymzm ) + y(x1 , . . . , x11 , y1, . . . , ym ) ⊆ k[x1 , . . . , x11 , y1 , . . . , ym , z1 , . . . , zm , y] comes
from a connected graph and has the same linearity defect as I + (y1 z1 , . . . , ym zm ).
Lemma 8.2. Let J ⊆ R = k[x1 , . . . , xn ] be a monomial ideal which does not contain a linear
form. Let L be an ideal generated by variables such that J ⊆ L. Consider the ideal I = J + yL
in the polynomial extension S = R[y]. There is an equality ldR J = ldS I.

LINEARITY DEFECT OF EDGE IDEALS

27

Proof. By Lemma 3.3, we get ldR J ≤ ldS I. For the reverse inequality, let p = (x1 , . . . , xn , y) ⊆
S. Consider the exact sequence
J
J
=
−→ 0.
0 −→ yL −→ I −→
yL ∩ J
yJ
The equality follows from the fact that yL ∩ J = y(L ∩ J) = yJ. Note that yL is Koszul and
yL∩pI = pyL by degree reasons. Hence by either [29, Theorem 3.1], or Lemma 4.11(a1) together
with Lemma 4.1(i), we get the first inequality in the following chain




J
k[y]
J
= ldS
= ldR J.
= ldS J ⊗k
ldS I ≤ max 0, ldS
yJ
yJ
yk[y]
The last equality follows from [30, Lemma 4.9]. This completes the proof.



The linearity defect of edge ideals of bipartite graphs also may depend on the characteristic.
Example 8.3. Dalili and Kummini [4, Example 4.8] found an example of a bipartite graph such
that the regularity of the corresponding edge ideal depends on the characteristic. Specifically,
their ideal is
I = (x1 y1 , x2 y1 , x3 y1 , x7 y1 , x9 y1 , x1 y2 , x2 y2 , x4 y2 , x6 y2 , x10 y2 , x1 y3 , x3 y3 , x5 y3 ,
x6 y3 , x8 y3 , x2 y4 , x4 y4 , x5 y4 , x7 y4 , x8 y4 , x3 y5 , x4 y5 , x5 y5 , x9 y5 , x10 y5 ,
x6 y6 , x7 y6 , x8 y6 , x9 y6 , x10 y6 ) ⊆ k[x1 , . . . , x10 , y1 , . . . , y6].
Computations with Macaulay2 using our package [31] show that ld I = 6 if char k = 0 and
ld I = 11 if char k = 2.
We have seen from Theorem 7.6 that the condition ld I(G) = 1 is equivalent to G being weakly
chordal and having induced matching number 2. Therefore we would like to ask the following
Question 8.4. Can the condition ld I(G) = 2 be characterized solely in terms of the combinatorial properties of the graph G, independent of the characteristic of k?
Remark 8.5. The analog of Question 8.4 for regularity has a clear answer. We know from
Fröberg’s theorem that the condition reg I(G) = 2 is independent of characteristic. FernánderzRamos and Gimenez [8, Theorem 4.1] show that if G is bipartite and connected, then the
following are equivalent:
(i) reg I(G) = 3;
(ii) Gc has an induced C4 and the bipartite complement of G has no induced Cm with m ≥ 5.
It is not hard to see that (ii) is equivalent to the condition that the bipartite complement of
G is weakly chordal and indmatch(G) = 2. Also, the reader may check that if G is bipartite
and disconnected, then reg I(G) = 3 if and only if G has two connected components G1 , G2 ,
each of which is co-chordal. In particular, for a bipartite graph G, the condition reg I(G) = 3 is
independent of the characteristic.
On the other hand, if G is not bipartite, then the condition reg I(G) = 3 might depend on the
characteristic: for Katzman’s ideal in Example 8.1, reg I(G) = 3 if char k = 0 and 4 if char k = 2.
Dalili and Kummini’s ideal in Example 8.3 shows that for connected bipartite graphs, the
condition reg I(G) = 4 is dependent on the characteristic: for their ideal, reg I = 4 if char k = 0
and 5 if char k = 2.

28

HOP D. NGUYEN AND THANH VU

In view of Example 8.3, we wonder if for a bipartite graph G and 2 ≤ ℓ ≤ 5, the condition
ld I(G) = ℓ is independent of the value of char k.
Acknowledgments
Parts of this work were finished when the first author was visiting the Department of Mathematics, University of Nebraska – Lincoln. We are grateful to Luchezar Avramov for his generosity
and constant encouragement. The first author is grateful to Tim Römer for his useful comments
and suggestions. Finally, we are indebted to two anonymous referees for their careful reading of
the paper and for pointing a gap in the proof of Theorem 7.7 in a previous version. We were able
to fill the gap and improve the readability of our paper thanks to their thoughtful suggestions
and comments.
References
[1] R. Ahangari Maleki and M.E. Rossi, Regularity and linearity defect of modules over local rings. J. Commut.
Algebra 6, no. 4 (2014), 485–504.
[2] L.L. Avramov, Infinite free resolution. in Six lectures on Commutative Algebra (Bellaterra, 1996), 1–118,
Progr. Math., 166, Birkhäuser (1998).
[3] W. Bruns and J. Herzog, Cohen-Macaulay rings. Revised edition. Cambridge Studies in Advanced Mathematics 39, Cambridge University Press (1998).
[4] K. Dalili and M. Kummini, Dependence of Betti numbers on characteristic. Comm. Algebra 42, no. 2 (2014),
563–570.
[5] A. Dochtermann and A. Engström, Algebraic properties of edge ideals via combinatorial topology. Electron.
J. Combin. 16 (2009), Special volume in honor of Anders Björner, Research Paper 2.
[6] D. Eisenbud, G. Fløystad and F. -O. Schreyer, Sheaf cohomology and free resolutions over exterior algebras.
Trans. Amer. Math. Soc. 355 (2003), 4397–4426.
[7] D. Eisenbud, M. Green, K. Hulek and S. Popescu, Restricting linear syzygies: algebra and geometry. Compos.
Math. 141 (2005), no. 6, 1460–1478.
[8] O. Fernández-Ramos and P. Gimenez, Regularity 3 in edge ideals associated to bipartite graphs. J. Algebr.
Combin. 39 (2014), 919–937.
[9] C. Francisco, H.T. Hà and A. Van Tuyl, Splittings of monomial ideals. Proc. Amer. Math. Soc. 137 (2009),
3271–3282.
[10] R. Fröberg, On Stanley-Reisner rings. In: Topics in Algebra, vol. 26 Part 2, pp. 57–70. Banach Center
Publications, PWN-Polish Scientific Publishers, Warsaw (1990).
[11] V. Gasharov, I. Peeva and V. Welker, The lcm-lattice in monomial resolutions. Math. Research Letters 6
(1999), 521–532.
[12] D. Grayson and M. Stillman, Macaulay2, a software system for research in algebraic geometry. Available at
http://www.math.uiuc.edu/Macaulay2.
[13] H.T. Hà, Regularity of squarefree monomial ideals. In: Connections between algebra, combinatorics, and
geometry, Springer Proc. Math. Stat., 76, Springer, New York (2014), pp. 251–276.
[14] H.T. Hà and A. Van Tuyl, Splittable ideals and the resolutions of monomial ideals. J. Algebra 309 (2007),
405–425.
[15] H.T. Hà and A. Van Tuyl, Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers. J.
Algebr. Combin. 27 (2008), 215–245.
[16] R. Hayward, C.T. Hoàng and F. Maffaray, Optimizing weakly triangulated graphs. Graphs and Combinatorics
5 (1989), no. 1, 339–349.
[17] J. Herzog and T. Hibi, Componentwise linear ideals. Nagoya Math. J. 153 (1999), 141–153.
[18] J. Herzog and T. Hibi, Monomial ideals. Graduate Texts in Mathematics 260, Springer (2011).
[19] J. Herzog and S.B. Iyengar, Koszul modules. J. Pure Appl. Algebra 201 (2005), 154–188.

LINEARITY DEFECT OF EDGE IDEALS

29

[20] J. Herzog, L. Sharifan and M. Varbaro, The possible extremal Betti numbers of a homogeneous ideal. Proc.
Amer. Math. Soc. 142 (2014), no. 6, 1875–1891.
[21] S.B. Iyengar and T. Römer, Linearity defects of modules over commutative rings. J. Algebra 322 (2009),
3212–3237.
[22] C. Jacobsson, Finitely presented graded Lie algebras and homomorphisms of local rings. J. Pure Appl. Algebra
38 (1985) 243–253.
[23] G. Kalai and R. Meshulam, Intersections of Leray complexes and regularity of monomial ideals. J. Combin.
Theor. 113 (2006), 1586–1592.
[24] M. Katzman, Characteristic-independence of Betti numbers of graph ideals. J. Combin. Theory, Ser. A 113
(2006) 435 – 454.
[25] F. Khosh-Ahang and S. Moradi, Regularity and projective dimension of the edge ideal of C5 -free vertex
decomposable graphs. Proc. Amer. Math. Soc. 142 (2014), 1567–1576.
[26] K. Kimura, Non-vanishingness of Betti numbers of edge ideals. In: Harmony of Gröbner bases and the
modern industrial society, World Sci. Publ., Hackensack, NJ (2012), pp. 153–168.
[27] K. Kimura, Non-vanishingness of Betti numbers of edge ideals and complete bipartite subgraphs. Preprint
(2013), Available online at http://arxiv.org/abs/1306.1333.
[28] S. Morey and R. Villarreal, Edge ideals: algebraic and combinatorial properties. in Progress in Commutative
Algebra, Combinatorics and Homology, Vol. 1 (C. Francisco, L. C. Klingler, S. Sather-Wagstaff and J. C.
Vassilev, Eds.), De Gruyter, Berlin (2012), pp. 85–126.
[29] H.D. Nguyen, Notes on the linearity defect and applications. Submitted (2015), available online at
http://arxiv.org/abs/1411.0261.
[30] H.D. Nguyen and T. Vu, Linearity defects of powers are eventually constant. Submitted (2015), available
online at http://arxiv.org/abs/1504.04853.
[31] H.D. Nguyen and T. Vu, LinearityDefect. A Macaulay2 package for computing the linearity defect. Available
at http://www.math.unl.edu/~tvu5/research/LinearityDefect.m2.
[32] R. Okazaki and K. Yanagawa, Linearity defect of face rings. J. Algebra 314 (2007), 362–382.
[33] I. Peeva and M. Velasco, Frames and degenerations of monomial resolutions. Trans. Amer. Math. Soc. 363,
no. 4 (2011), 2029–2046.
[34] P. Roberts, Homological invariants of modules over commutative rings. Seminaire de Mathematiques Superieures 72, Les Presses de l’Universite de Montreal (1980).
[35] T. Römer, On minimal graded free resolutions. Dissertation, Essen (2001).
[36] L.M. Şega, On the linearity defect of the residue field. J. Algebra 384 (2013), 276–290.
[37] J. Spinrad and R. Sritharan, Algorithms for weakly triangulated graphs. Discrete Appl. Math. 59 (1995),
181–191.
[38] A. Van Tuyl, A beginner’s guide to edge and cover ideals. in Monomial ideals, computations and applications,
63–94, Lecture Notes in Math., 2083, Springer, Heidelberg (2013).
[39] R.H. Villarreal, Monomial Algebras. Monographs and Textbooks in Pure and Applied Mathematics, 238.
Marcel Dekker, Inc., New York (2001).
[40] R. Woodroofe, Matchings, coverings, and Castelnuovo-Mumford regularity. J. Commut. Algebra 6 (2014),
no. 2, 287–304.
Fachbereich Mathematik/Informatik, Institut für Mathematik, Universität Osnabrück, Albrechtstr. 28a, 49069 Osnabrück, Germany
Dipartimento di Matematica, Università di Genova, Via Dodecaneso 35, 16146 Genoa, Italy
E-mail address: ngdhop@gmail.com
Department of Mathematics, University of Nebraska-Lincoln, Lincoln, NE 68588, USA
E-mail address: tvu@unl.edu

