arXiv:1508.03799v1 [] 16 Aug 2015

STABILITY OF BETTI NUMBERS UNDER REDUCTION PROCESSES:
TOWARDS CHORDALITY OF CLUTTERS
MINA BIGDELI, ALI AKBAR YAZDAN POUR, RASHID ZAARE-NAHANDI

Abstract. For a given clutter C, let I := I C̄ be the circuit ideal in the polynomial
ring S. In this paper, we show that the Betti numbers of I and I + (xF ) are the same in
their non-linear strands, for some suitable F ∈ C. Motivated by this result, we introduce
a class of clutters that we call chordal. This class, is a natural extension of the class of
chordal graphs and has the nice property that the circuit ideal associated to any member
of this class has a linear resolution over any field. Finally we compare this class with all
known families of clutters which generalize the notion of chordality, and show that our
class contains several important previously defined classes of chordal clutters. We also
show that in comparison with others, this class is possibly the best approximation to the
class of d-uniform clutters with linear resolution over any field.

introduction
Square-free monomial ideals are in strong connection to topology and combinatorics.
There are at least two approaches to investigate these ideals in terms of topology or
combinatorics. One approach is to associate a simplicial complex to a given square-free
monomial ideal I, whose faces come from square-free monomials which do not belong to
I. Another approach is to associate a clutter to I whose circuits come from the minimal
generators of I. The main goal in both cases is to obtain algebraic properties of I via
combinatorial or topological properties of associated objects. One of the highlighted result
on this subject is Fröberg’s theorem.
R. Fröberg in 1990 showed that, the edge ideal of a graph G has a linear resolution
if and only if the complement graph Ḡ is chordal [10]. In particular, for a square-free
monomial ideal generated in degree 2, the problem of having linear resolution depends
only on the shape of the associated graph, and does not depend on the characteristic of
the base field. This is not the case for square-free monomial ideals generated in degree
d > 2. The ideal associated to a triangulation of the projective plane, is a classical
example of a square-free monomial ideal generated in degree 3 whose resolution depends
on the characteristic of the base field (see e.g. [17, Section 4]). So it is too much to
expect a combinatorial characterization (as in Fröberg’s theorem) for arbitrary squarefree monomial ideals with linear resolution. However, it is reasonable to ask, if one may
find such a characterization for (square-free) monomial ideals with linear resolution over
any field. It is worth to say that, via Alexander duality, this problem is equivalent to
characterization of all simplicial complexes which are Cohen-Macaulay over any field (c.f.
[9, Theorem 3]). As a partial result on this subject, in [7, 11, 23, 24], the authors defined
several generalizations of chordality to higher dimensions, and they showed that the ideal
associated to their classes, have a linear resolution over any field. However, it is not so
difficult to give a counterexample for the other direction. On the other hand, in [4], the
2010 Mathematics Subject Classification. Primary 13D02, 13F55; Secondary 05E45, 05C65.
Key words and phrases. Betti number, Linear resolution, Regularity, index, Chordal clutter.
1

2

M. BIGDELI, A. A. YAZDAN POUR, R. ZAARE-NAHANDI

authors made the attempt to prove the other direction, by showing that every squarefree monomial ideal with linear resolution over any field, comes from a chorded simplicial
complex, where in that paper chorded is defined pretty technically. Yet, the authors show
by an example that not any ideal admitting a linear resolution over any field, need to be
chorded in their sense [4, Example 7.2].
The main aim of this paper is twofold. First we show that, for a given square-free
monomial ideal I, we may add (remove) some generators to (from) I in a way that, the
corresponding non-linear strands do not change under this process. Then, motivated by
this result, we introduce a class of clutters whose associated ideal of any member of this
class has a linear resolution over any field. The advantage of this definition is that, this
class contains other known families of clutters with this property, and at the moment, we
don’t know of any counterexample for the other direction (see Question 1).
The paper is organized as follows: In the first section, we present the background
material. This involves some preliminaries on graded modules and Betti numbers together
with some basic notions of combinatorics. Then, in Section 2, we state one of the main
theorems of this paper (Theorem 2.1). Indeed, with the required preparations, we show
that, if I is a square-free monomial ideal corresponded to a clutter C and F ∈ C is chosen
appropriately, then the ideals I + (xF ) and I share the same Betti numbers in their nonlinear strands. In Section 3, we introduce the class Cd of chordal clutters. It is shown that,
for any member of Cd , the associated ideal has a linear resolution over any field. Then we
show that, this class contains other families of chordal clutters as defined in [7, 11, 23, 24].
We close the paper by showing that, unlike in the graph case, it is not true that for
arbitrary element of Cd , the associated ideal has linear quotients. A counterexample for
the last assertion, comes from a triangulation of the dunce hat.
1. preliminaries
Algebraic backgrounds. Throughout this paper, S = K[x1 , . . . , xn ] denotes the polynomial ring over a field K with the standard grading (i.e. deg(xi ) = 1). Let M 6= 0 be a
finitely generated graded S-module and
· · · → F2 → F1 → F0 → M → 0
K

a graded minimal free resolution of M with Fi = ⊕j S(−j)βi,j for all i.
K (M ) = dim TorS (K, M ) are called the graded Betti numbers of M
The numbers βi,j
K
j
i
and
projdim(M ) = sup{i :
= max{i :

TorSi (M, K) 6= 0}
K
(M ) 6= 0 for some j}
βi,i+j

is called the projective dimension of M . For simplicity, in this paper, we fix a field K and
K.
we write simply βi,j instead of βi,j
The Castelnuovo-Mumford regularity of M =
6 0, reg(M ), is given by
reg(M ) = sup{j − i :

βi,j (M ) 6= 0}.

The initial degree of M , indeg(M ), is given by
indeg(M ) = inf{i :

Mi 6= 0}.

We say that a finitely generated graded S-module M 6= 0 has a d-linear resolution, if its
regularity is equal to d = indeg(M ). An important class of graded modules with linear
resolution, is the class of modules which are generated in the same degree and have linear

REDUCTION AND CHORDALITY

3

quotients [14]. Recall that M is said to have linear quotients, if M has an ordered set
of minimal generators {m1 , . . . , mr } such that the colon ideals (m1 , . . . , mi−1 ) : mi are
generated by linear forms, for i = 2, . . . , r.
In this paper, we concentrate on homogeneous ideals of S, in particular monomial ideals.
An invariant of a homogeneous ideal in the polynomial ring, is the Green-Lazarsfeld index
which measures the number of linear steps in the graded minimal free resolution of an ideal.
The ideal I ⊂ S is called r steps linear, if I has a linear resolution up to homological degree
r, in other words, if βi,i+j (I) = 0 for all pairs (i, j) with 0 ≤ i ≤ r and j > indeg(I). The
number
index(I) = sup{r :

I is r steps linear} + 1

is called the index of I. In particular, I has a linear resolution if and only if index(I) = ∞.
Clutters and circuit ideals. Let us introduce some notations and terminologies which
concerns about combinatorial commutative algebra. Let [n] = {1, . . . , n}.
Definition 1.1 (Clutter). A clutter C with vertex set [n] is a collection of subsets of [n],
called circuits of C, such that if F1 and F2 are distinct circuits, then F1 * F2 . A d-circuit
is a circuit consisting of exactly d vertices, and a clutter is called d-uniform, if every circuit
has d vertices. A (d − 1)-subset e ⊂ [n] is called a submaximal circuit of C, if there exists
F ∈ C such that e ⊂ F . The set of all submaximal circuits of C is denoted by SC(C).
Let C be a clutter with vertex set [n]. For a subset W ⊆ [n], the induced subclutter on
W is denoted by C|W and is defined as follows:
C|W = {F ∈ C :

F ⊆ W}.

Also, for a non-empty clutter C with vertex set [n], we define the ideal I (C), as follows:
I(C) = (xT :

T ∈ C) ,

where xT = xi1 · · · xit for T = {i1 , . . . , it }, and we define I(∅) = 0.
Let n, d be positive integers. For n ≥ d, we define Cn,d , the complete d-uniform clutter
on [n], as follows:
Cn,d = {F ⊂ [n] : |F | = d} .
In the case that n < d, we let Cn,d be some isolated points. It is well-known that, for n ≥ d
the ideal I (Cn,d ) has a d-linear resolution (see e.g. [18, Example 2.12]).
¯ the complement of C, to be
If C is a d-uniform clutter on [n], we define C,
C¯ = Cn,d \ C = {F ⊂ [n] :

|F | = d, F ∈
/ C}.

Frequently in this paper, we take a d-uniform clutter C 6= Cn,d with vertex set [n] and
¯ in the polynomial ring S = K[x1 , . . . , xn ].
consider the square-free
monomial ideal I = I(C)

¯
The ideal I = I C is called the circuit ideal of C.

Definition 1.2. Let C be a d-uniform clutter on [n]. A subset V ⊂ [n] is called a clique
in C, if all d-subsets of V belong to C. Note that a subset of [n] with less than d elements
is supposed to be a clique.
For any (d − 1)-subset e of [n], let
NC [e] = e ∪ {c ∈ [n] :

e ∪ {c} ∈ C}.

4

M. BIGDELI, A. A. YAZDAN POUR, R. ZAARE-NAHANDI

We call NC [e] the closed neighborhood of e in C. We say that e is simplicial in C, if NC [e]
is a clique in C. Let us denote by Simp (C), the set of all simplicial elements of C. More
generally, for a subset A ⊂ [n] with |A| < d, let
NC [A] = A ∪ {c ∈ [n] :

A ∪ {c} ⊆ F, for some F ∈ C} .

Example 1.3. Figure 1 displays a 3-uniform clutter C whose circuits are
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {2, 3, 6}, {2, 5, 6}, {2, 5, 7}, {2, 6, 7}, {5, 6, 7}.
In this clutter, {2, 3} and {2, 6} are not simplicial in C, but all the other submaximal
circuits of the set {1, . . . , 7} are simplicial in C.
5

1

4

2
3

7
6

Figure 1. A 3-uniform clutter
Definition 1.4. Let C be a d-uniform clutter and let e be a (d − 1)-subset of [n]. By C \ e
we mean the d-uniform clutter
{F :

F ∈ C, e * F } .

It is called the deletion of e from C. In the case that e is not a submaximal circuit of C,
we have C \ e = C.
2. stability of non-linear strands under removing simplicial elements
The goal of this section is to show that deletion of simplicial elements of a d-uniform
clutter does not change the Betti numbers of the corresponding non-linear strands. Indeed,
the main goal of this section is to prove the following theorem.
Theorem 2.1. Let C be a d-uniform clutter and e ∈ Simp(C) a simplicial element of C.
Let A ⊆ {F ∈ C : e ⊂ F } and D = C \ A. Then,


βi,i+j I C¯ = βi,i+j I D̄ ,
for all i and all j > d. Consequently,


(a) reg I C¯ 
= reg I D̄ ; 
(b) index I C¯ 
= index I D̄ ; 
(c) projdim I C¯ ≤ projdim I D̄ .

To prove Theorem 2.1, we need some preparations and we consider more generally
graded ideals. In the next sections, we will introduce several applications of this theorem.
Among other applications, Theorem 2.1 recovers and extends [19, Theorem 2.7] and [18,
Theorem 3.7].

Lemma 2.2. Let I, L ⊂ S be graded ideals generated in degree d, and suppose that L has
a d-linear resolution. Then the following statements are equivalent:

REDUCTION AND CHORDALITY

5

(a) the natural map αi,j : Tori (I, K)i+j → Tori (I + L, K)i+j induced by the inclusion
I ֒→ I + L is an isomorphism for all i and all j > d;
(b) reg (I ∩ L) ≤ d + 1 and the connecting homomorphism
γi+1,j : Tori+1 (I + L, K)(i+1)+j → Tori (I ∩ L, K)i+(j+1)
is surjective for all i and all j ≥ d.
If the equivalent conditions are satisfied, then βi,i+j (I) = βi,i+j (I + L) for all i and all
j > d.
Proof. (a) ⇒ (b): For all j ≥ d, the short exact sequence
0 →I ∩L →I ⊕L→I +L→ 0
induces the long exact sequence
αi+1,j

γi+1,j

· · · −−−−→ Tori+1 (I + L, K)(i+1)+j −−−−→ Tori (I ∩ L, K)i+(j+1)
−−−−→

Tori (I, K)i+(j+1)

αi,j+1

−−−−→ Tori (I + L, K)i+(j+1) −−−−→ · · · .

Here we used the fact that Tori (I ⊕ L, K)i+(j+1) = Tori (I, K)i+(j+1) for all j ≥ d. Condition (a) implies that Ker (αi,j+1 ) = 0 and hence γi+1,j is surjective for all j ≥ d.
The above sequence implies that Tori (I ∩ L, K)i+(j+1) = 0 for all i and all j > d,
since the maps αi+1,j and αi,j+1 are isomorphism for all i and all j > d. Therefore
reg(I ∩ L) ≤ d + 1.
(b) ⇒ (a): For j > d consider the exact sequence
γi+1,j−1

· · · −−−−−→ Tori (I ∩ L, K)i+j −−−−→

Tori (I, K)i+j

αi,j

−−−−→ Tori (I + L, K)i+j −−−−→ Tori−1 (I ∩ L, K)(i−1)+(j+1) −−−−→ · · · .
Our assumptions in (b) implies that Tori−1 (I ∩ L, K)(i−1)+(j+1) = 0 and that γi+1,j−1
is surjective. Hence αi,j is an isomorphism for all i and all j > d.

Lemma 2.3. Let J ⊆ I be homogeneous ideals generated in the same degree d. Then,
(a) βi,i+d (J) ≤ βi,i+d (I), for all i.
Moreover, if for all i and j > d, one has
(1)

βi,i+j (I) = βi,i+j (J)

then:
(b) reg (I) = reg (J);
(c) index (I) = index (J);
(d) projdim(I) ≤ projdim(J).
Proof. (a) From the short exact sequence
0 −→ J −→ I −→

I
−→ 0
J

we get the long exact sequence:
φ

· · · → Tori+1 (I/J, K)(i+1)+(d−1) → Tori (J, K)i+d −→ Tori (I, K)i+d → · · · .
Since I/J is generated in degree d, Tori+1 (I/J, K)(i+1)+(d−1) = 0 and so φ is injective.
Therefore,
βi,i+d (J) = dimK (Tori (J, K)i+d ) ≤ dimK (Tori (I, K)i+d ) = βi,i+d (I).

6

M. BIGDELI, A. A. YAZDAN POUR, R. ZAARE-NAHANDI

(b) Let r := reg(J). Since J is generated by elements of degree d, it follows that r ≥ d.
If r = d, then (1) implies that βi,j (I) = 0, for all j > i + d. Hence, reg(I) = d = reg(J).
If r > d, then using (1) again, we get the conclusion.
(c) If index(I) = ∞, then I has a d-linear resolution and by (b), the ideal J has a
d-linear resolution too. This is equivalent to say that index(J) = ∞. In the case that
index(I) is finite, (c) is again a direct consequence of (1).
(d) Our assumption in (1) together with part (a), implies that
βi,i+j (J) ≤ βi,i+j (I)
for all i and j. This implies that,
projdim(J) = max{i : βi,i+j (J) 6= 0 for some j} ≤ max{i : βi,i+j (I) 6= 0 for some j}
= projdim(I).

Proposition 2.4. Let I and L be graded ideals generated in degree d such that both ideals
I ∩ L and L have a d-linear resolution. Then,
(a) βi,i+j (I) = βi,i+j (I + L), for all i and all j > d;
(b) projdim (I + L) = max {projdim (I) , projdim (L)}.
Proof. Statement (a) is an immediate consequence of Lemma 2.2. To obtain (b), let
ρ = projdim (I + L). Then βρ,ρ+j (I + L) 6= 0, for some j ≥ d. If j > d, then βρ,ρ+j (I) 6= 0
by (a). Therefore in this case, max {projdim(I), projdim(L)} ≥ ρ.
Now assume that j = d. The short exact sequence
0 −→ I ∩ L −→ I ⊕ L −→ I + L −→ 0
induces the long exact sequence
· · · −→ Torρ+1 (I + L, K)(ρ+1)+(d−1) → Torρ (I ∩ L, K)ρ+d → Torρ (I ⊕ L, K)ρ+d
−→ Torρ (I + L, K)ρ+d
→ Torρ−1 (I ∩ L, K)(ρ−1)+(d+1) −→ · · · .
Since the ideal I ∩L has a d-linear resolution, Torρ−1 (I ∩ L, K)(ρ−1)+(d+1) = 0. Moreover,
Torρ+1 (I + L, K)(ρ+1)+(d−1) = 0. Thus, we obtain the following short exact sequence:
0 → Torρ (I ∩ L, K)ρ+d → Torρ (I, K)ρ+d ⊕ Torρ (L, K)ρ+d → Torρ (I + L, K)ρ+d → 0.
Since βρ,ρ+d (I + L) 6= 0 by assumption, this short exact sequence implies that either
βρ,ρ+d (I) 6= 0 or βρ,ρ+d (L) 6= 0. Hence, again in this case we have
max {projdim(I), projdim(L)} ≥ ρ.
In order to prove the opposite inequality, we set ρ′ := max{projdim(I), projdim(L)}.
Suppose that projdim (L) = ρ′ . Then βρ′ ,ρ′ +j (L) 6= 0, for some j ≥ d. Since L has a
d-linear resolution, j = d. Using Lemma 2.3(a), we have βρ′ ,ρ′ +d (L) ≤ βρ′ ,ρ′ +d (I + L).
Thus projdim (I + L) ≥ ρ′ .
Suppose now that projdim (I) = ρ′ . Then βρ′ ,ρ′ +j (I) 6= 0 for some j ≥ d. If j > d,
then βρ′ ,ρ′ +j (I + L) 6= 0 by (a). So projdim (I + L) ≥ ρ′ . If j = d, then βρ′ ,ρ′ +d (I) ≤
βρ′ ,ρ′ +d (I + L), by Lemma 2.3(a). It follows that projdim (I + L) ≥ ρ′ , in this case too.

In the following proposition we discuss on the hypotheses of Proposition 2.4 in the case
that I and L are monomial ideals generated in degree d and the generators of L have a
common factor of degree d − 1. As we shall see, in this case, for the ideal I ∩ L the matter

REDUCTION AND CHORDALITY

7

of having linear resolution is independent of the characteristic of the base field. To state
this proposition, first we fix some notations.
For a given monomial w = xc11 . . . xcnn , let νi (w) be the integer ci . Also, for a monomial
ideal I, let G(I) denotes the unique minimal set of monomial generators of I. Recall that,
for monomial ideals I and L, one has (see e.g. [14, Proposition 1.2.1])
I ∩ L = (lcm (u, v) :

u ∈ G(I) and v ∈ G(L)) .

Proposition 2.5. Let 0 6= I ⊂ S = K[x1 , . . . , xn ] be a monomial ideal generated in degree
d, u a non-zero monomial of degree d − 1 and L a non-empty subset of {x1 , . . . , xn }. Let
L = (xi u : xi ∈ L). The following conditions are equivalent:
(a) the ideal I ∩ L has a d-linear resolution;
(b) I ∩ L is a non-zero monomial ideal generated in degree d;
(c) either L ⊆ I, or for all v ∈ G(I) there exists xi ∈ L with xi u ∈ I such that
νi (u) + 1 ≤ νi (v);
(d) either L ⊆ I, or I ∩ L = (xi u : xi ∈ L and xi u ∈ I) 6= 0.
Proof. First of all note that:
(2)

I ∩ L = (lcm (xi u, v) :

xi ∈ L and v ∈ G(I)) .

The implication (a) ⇒ (b) is obvious.
(b) ⇒ (c): Suppose that L * I and take a generator v ∈ G(I). The assumption
L * I implies that there exists xj ∈ L such that xj u ∈
/ I. In particular, xj u 6= v and
deg (lcm (xj u, v)) > d. Since I ∩ L 6= 0 is generated in degree d, it follows that there exists
xi ∈ L such that xi u ∈ G(I) and xi u divides lcm(v, xj u). Note that i 6= j, for xi u ∈ I.
Furthermore,
1 + νi (u) = νi (xi u) ≤ max {νi (xj u) , νi (v)} = max {νi (u) , νi (v)} .
The above inequality shows that νi (u) + 1 ≤ νi (v).
(c) ⇒ (d): If L ⊆ I, there exists nothing to prove. So assume that L * I and let
L′ = (xi u :

xi ∈ L and xi u ∈ I) .

By (2), it is enough to show that lcm (xj u, v) ∈ L′ , for all xj ∈ L and v ∈ G(I).
Let v ∈ G(I) and xj ∈ L. Our assumption implies that there exists xi ∈ L with xi u ∈ I
such that νi (u) + 1 ≤ νi (v). So, xi u ∈ L′ and
νi (xi u) = νi (u) + 1 ≤ νi (v);
νk (xi u) = νk (u) ≤ νk (xj u), for k 6= i.
Thus νk (xi u) ≤ max {νk (xj u) , νk (v)} = νk (lcm (xj u, v)), for all k = 1, . . . , n. This
implies that, xi u divides lcm (xj u, v).
(d) ⇒ (a): The assumption implies that:

I ∩ L = xi u : xi ∈ L ′ ,
where L′ is a non-empty subset of {x1 , . . . , xn }. One may easily verify that such ideals
have a linear resolutions.

Remark 1. Let 0 6= I ⊂ S = K[x1 , . . . , xn ] be a square-free monomial ideal generated in
degree d, u a non-zero square-free monomial of degree d − 1 and L a non-empty subset of
{x1 , . . . , xn } such that,
• xi does not divide u for all xi ∈ L,
• L = (xi u : xi ∈ L) * I.

8

M. BIGDELI, A. A. YAZDAN POUR, R. ZAARE-NAHANDI

Then, L has a d-linear resolution with projdim (L) = |L| − 1 and Proposition 2.5 implies
the equivalence of the following statements:
(a) the ideal I ∩ L has a d-linear resolution;
(b) for all v ∈ G(I) there exists xi ∈ L such that xi u ∈ I and xi divides v.
The following corollary is an essential part of proving the main theorem (Theorem 2.1)
of this section.
Corollary 2.6. Let C be a d-uniform
 clutter on thevertex set [n], e a simplicial element
of C and C ′ = C \ e. Let I = I C¯ and J = I C¯′ be the corresponding circuit ideals.
Then,
(a) βi,i+j (I) = βi,i+j (J), for all i and all j > d.
(b) projdim(J) ≥ projdim(I). Indeed, if e ∈ SC(C), then projdim (J) = n − d.
Proof. If e ∈
/ SC(C), then C \ e = C and Q
there is nothing to prove. So assume that
e ∈ SC(C) is simplicial. In this case, let u = i∈e xi and L = (xi u : i ∈ [n] \ e). Then L
has a d-linear resolution with projdim (L) = n − d and J = I + L. We claim that I ∩ L
has a d-linear resolution. To prove our claim, first note that L * I, because e ∈ SC(C).
So, it is enough to show that statement (b) in Remark 1 is satisfied for the ideal I and
the subset L = {xi : i ∈ [n] \ e} of variables. Assume that v ∈ G(I). Then v = xF for
¯ Since e is a simplicial submaximal circuit of C, we have F * NC [e]. Take an
some F ∈ C.
¯ xi |v and xi u ∈ I. This completes the
element i ∈ F \ NC [e]. Then xi ∈ L, {i} ∪ e ∈ C,
proof of the claim.
Since L and I ∩ L have linear resolutions, statements (a) and (b) can be obtained from

Proposition 2.4.
Now we are ready to prove our main theorem.
Proof of Theorem 2.1. If A = {F ∈ C : e ⊂ F }, then the Corollary 2.6(a), yields the
conclusion. So assume that A′ := {F ∈ C : e ⊂ F and F ∈
/ A} =
6 ∅. Then, it is clear
′
that D = (C \ e) ∪ A and e is a simplicial submaximal circuit of D (and C). Moreover,
D \ e = C \ e. Hence, by Corollary 2.6(a), we conclude that:
 
 




βi,i+j I D̄ = βi,i+j I D \ e = βi,i+j I C \ e = βi,i+j I C¯

for all i and j > d, as desired. The other assertions are direct consequences of Lemma 2.3.

3. chordal clutters

Chordal graphs are probably the most important combinatorial objects in the problem
of classification of monomial ideals with linear resolution (quotients). Thanks to Fröberg,
we know that a square-free monomial ideal I generated in degree 2 has a linear resolution
(over any field K) if and only if I = I Ḡ , for some chordal graph G ([10]). Later, this

result has been improved by showing that I has linear quotients if and only if I = I Ḡ ,
where G is a chordal graph ([15]).
This successful combinatorial characterization of ideals generated in degree 2 with linear
resolution (quotients), motivated many mathematicians to generalize this result for squarefree monomial ideals generated in degree d > 2. Some partial results on this subject are
given in [2, 3, 4, 7, 11, 18, 20, 23, 24]. The goal of this section is to introduce a class
of d-uniform clutters (which we call chordal clutters) which extends the definition of the

REDUCTION AND CHORDALITY

9

class of chordal graphs, and the corresponding circuit ideal has a linear resolution over
any field. The idea to state the definition in this manner comes from Theorem 2.1(a).
Definition 3.1. Let C be a d-uniform clutter. We call C a chordal clutter, if either C = ∅,
or C admits a simplicial submaximal circuit e such that C \ e is chordal.
Following the notation in [18], we use Cd , to denote the class of all d-uniform chordal
clutters. Our aim in this section is to show that, this definition is the natural generalization
of chordal graphs. That is, with this definition, we show that the circuit ideal associated
to these clutters has a linear resolution over any field. Note that the definition of chordal
clutters can be restated as follows:
The d-uniform clutter C is chordal if either C = ∅, or else there exists a sequence of
submaximal circuits of C, say e1 , . . . , et , such that e1 is simplicial submaximal circuit of
C, ei is simplicial submaximal circuit of (((C \ e1 ) \ e2 ) \ · · · ) \ ei−1 for all i > 1, and
(((C \ e1 ) \ e2 ) \ · · · ) \ et = ∅.
To simplify the notation, we use Ce1 ...ei for (((C \ e1 ) \ e2 ) \ · · · ) \ ei .
Example 3.2. In Figure 2, the 3-uniform clutter C is chordal, while the 3-uniform clutter
D is not.
C = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 5}, {1, 2, 6}, {1, 5, 6}, {2, 5, 6}}.
D = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}}.

1

1

3

5

2
4

6

2

3
4

5

Figure 2. The Clutter C on the left and D on the right
Remark 2. It is worth to say that this definition of chordal clutters coincides with the
graph theoretical definition of chordal graphs in the case d = 2. To see this, we recall
that, a graph G is chordal, if and only if for every induced subgraph G′ of G, one has
Simp (G′ ) 6= ∅ (essentially [5]). It follows that, a graph G is chordal, if and only if there
exists an order on vertices of G, say v1 , . . . vn , such that vi is simplicial in G|{v1 ,...,vi−1 } .
This is equivalent to say that G ∈ C2 .
The following result, which is contained in [18, Remark 3.10], justifies our definition of
chordality, because the property of being chordal should, as in Fröberg’s theorem, imply
that the circuit ideal has a d-linear resolution over any field K.
Theorem 3.3. Let C =
6 Cn,d be a d-uniform chordal clutter on the vertex set [n]. Then
¯ has a d-linear resolution over any field K.
I(C)
Proof. Since C is chordal, there exists a sequence of submaximal circuits of C, say e1 , . . . , et ,
such that e1 is simplicial submaximal circuit of C, ei is simplicial submaximal circuit
of

Ce1 ...ei−1 for all i > 1, and Ce1 ...et = ∅. It follows from Theorem 2.1(b) that I C¯ has a

10

M. BIGDELI, A. A. YAZDAN POUR, R. ZAARE-NAHANDI


d-linear resolution if and only if I Ce1 ...et has a d-linear resolution. This is indeed the

¯ = I (Cn,d ).

case, because I Ce1 ...et = I (∅)

As mentioned at the beginning of this section, the nice characterization of square-free
monomial ideals generated in degree 2 in terms of chordal graphs (Fröberg’s theorem),
motivated many mathematicians to generalize the definition of chordal graphs. Some of
the most important results are due to Emtander [7], Woodroofe [24], Connon and Faridi
[4], and Nevo et al [3] (ordered chronologically). In the remaining of this section, we
compare the class Cd with the other known families of chordal clutters.

3.1. Woodroofe’s chordal class vs Cd . A nice class of clutters whose circuit ideals
have a linear resolution over any field (in fact have linear quotients) has been defined by
Woodroofe in [24]. This class is named chordal clutters in that text and for the avoidance
of ambiguity, we call it W-chordal in this paper. Below, we state the definition of a Wchordal clutter and show that this class is strictly contained in Cd . To state the definition
of W-chordal clutters, first we need the following operations as defined in [24].
Given a clutter C (not necessarily uniform), there are two ways of removing a vertex
that are of interest. Let v ∈ V (C). The deletion, C \ v, is the clutter on the vertex set
V (C) \ {v}, with circuits {F ∈ C : v ∈
/ F }. The contraction, C/v, is the clutter on the
vertex set V (C) \ {v}, which the circuits are the minimal sets of {F \ {v} : F ∈ C}. Thus,
C \ v deletes all circuits containing v, while C/v removes v from each circuit containing it
and then removes any redundant circuits.
A clutter D obtained from C by a sequence of deletions and/or contractions is called a
minor of C. It is straightforward to prove that, if v 6= w are vertices, then:
(C \ v) \ w = (C \ w) \ v,

(C/v)/w = (C/w)/v,

(C \ v)/w = (C/w) \ v.

Definition 3.4 (W-chordal). Let C be a clutter. A vertex v of C is W-simplicial, if for
every two circuits F1 and F2 of C that contain v, there is a third circuit F3 such that,
F3 ⊆ (F1 ∪F2 )\{v}. A clutter C is called W-chordal, if every minor of C has a W-simplicial
vertex.
As it is mentioned in [24], W-chordal clutters contain a variety of classes of combinatorial
objects, including chordal graphs, complete d-uniform clutters, matroids, etc. To show
that W-chordal clutters are contained in Cd , we need the following intermediate steps.
Lemma 3.5. Let C be a d-uniform clutter and e be a submaximal circuit of C. Then, e is
simplicial if and only if each vertex of e is W-simplicial in C|NC [e] .
Proof. The implication (⇒) is straightforward. For the other direction, assume that each
vertex of e is W-simplicial in C|NC [e] . We must show that each d-subset of NC [e] is a
circuit in C. Suppose that e = {v1 , . . . , vd−1 } and let G be a d-subset of NC [e]. The
proof is by induction on i = |G \ e|. For i = 1, we have then e ⊂ G, and G is a circuit
by definition of NC [e]. Suppose that i > 1. Without loss of generality, we may assume
that G = {vi , vi+1 , . . . , vd−1 , w1 , . . . , wi }. Then, the sets G1 = {v1 } ∪ (G \ {w1 }) and
G2 = {v1 } ∪ (G \ {w2 }) are circuits in C by the induction hypothesis. On the other hand,
v1 ∈ G1 ∩ G2 and v1 is W-simplicial and therefore G = (G1 ∪ G2 ) \ {v1 } is a circuit in
C.

Lemma 3.6. Let C be a d-uniform clutter, and v1 be a W-simplicial vertex such that
C|NC [{v1 }] is W-chordal. Then, there exists a simplicial submaximal circuit e such that
v1 ∈ e.

REDUCTION AND CHORDALITY

11


Proof. The clutter C|NC [{v1 }] /v1 is a minor of C|NC [{v1 }] and has a W-simplicial vertex,
namely v2 . In this case, v2 is also a W-simplicial vertex in C1 := C|NC [{v1 ,v2 }] /v1 . Moreover,
the clutter C1 /v2 is again a minor of C|NC [{v1 }] and has a W-simplicial vertex as v3 which
is a W-simplicial vertex in C2 := C|NC [{v1 ,v2 ,v3 }] /v1 /v2 too. By this process, we obtain a
set of vertices e := {v1 , v2 , . . . , vd−1 } which is a submaximal circuit of C. We prove that
for each 1 ≤ i ≤ d − 1, the vertex vi is W-simplicial in C|NC [e] . Then, by Lemma 3.5, we
may deduce that e is simplicial. To do this, first we claim that:
Claim.
For any (d − 1)-subset B = {w1 , . . . , wd−1 } of NC [e] \ {v1 }, the set
B ∪ {v1 } is a circuit in C|NC [e] .
Proof of the claim. Without loss of generality we may assume that B ∩ e =
{v1 , . . . , vt−1 } and B \ e = {wt , wt+1 , . . . , wd−1 }, for some integer 1 ≤ t ≤ d − 1. If
|B \ e| = 1, then {v1 } ∪ B = e ∪ {wd−1 } which is obviously a circuit in C|NC [e] . Let
|B \ e| > 1. Then, e ∪ {wd−1 } and e ∪ {wd−2 } are circuits in C|NC [e] . Therefore,
{vd−1 , wd−1 } and {vd−1 , wd−2 } are circuits in the minor C|NC [e] /v1 /v2 / · · · /vd−2 .
In this minor, vd−1 is also W-simplicial and hence {wd−1 , wd−2 } is a circuit in
this minor. Therefore, {v1 , . . . , vd−2 , wd−1 , wd−2 } is a circuit in C|NC [e] . Similarly {v1 , . . . , vd−2 , wd−1 , wd−3 } is a circuit in C|NC [e] . Thus, {vd−2 , wd−1 , wd−3 }
and {vd−2 , wd−1 , wd−2 } are circuits in the minor C|NC [e] /v1 / · · · /vd−3 which has
vd−2 as a W-simplicial vertex. Now, as the above argument, we conclude that
{v1 , . . . , vd−3 , wd−1 , wd−2 , wd−3 } is a circuit in C|NC [e] . Continuing this process, we
obtain the conclusion.
Now, we are ready to show that, for each 1 ≤ i ≤ d − 1, the vertex vi is W-simplicial in
C|NC [e] . Note that v1 is a W-simplicial vertex of C and hence is a W-simplicial in C|NC [e] .
For 1 < i ≤ d − 1, let E and F be two circuits in C|NC [e] containing vi .
• If v1 ∈
/ E ∪F , then {v1 }∪(E \ {vi }) and {v1 }∪(F \ {vi }) are circuits containing the
W-simplicial vertex v1 and therefore, there is a circuit contained in (E ∪ F ) \ {vi }.
• If v1 ∈ E ∩ F , then for each (d − 1)-subset D of (E ∪ F ) \ {v1 , vi }, we have D ∪ {v1 }
is a circuit in C|N [e] which is also contained in (E ∪ F ) \ {vi }.
• If v1 ∈ E and v1 ∈
/ F , then there exists u ∈ F \ E such that (E \ {vi }) ∪ {u} and
(F \ {vi }) ∪ {v1 } are circuits in C which contain v1 . Hence, there is a circuit inside
(E ∪ F ) \ {vi }.

The reader may notice that, in the middle of the proof of Lemma 3.6, it is actually
proved the following statement:
Corollary 3.7. Let C be a d-uniform clutter and v1 , . . . , vd−1 be a sequence of vertices of
C such that:
(i) v1 is W-simplicial in C;

(ii) vi is W- simplicial in C|NC [{v1 ,...,vi−1 }] /v1 / · · · /vi−1 , for i = 2, . . . , d − 1;
Then e = {v1 , . . . , vd−1 } is a simplicial submaximal circuit in C.

Proposition 3.8 (W-chordals are chordal). If C is a d-uniform W-chordal clutter,
then C ∈ Cd .
Proof. Since C is W-chordal, C has a W-simplicial vertex v. Let e1 be a simplicial submaximal circuit as in the proof of Lemma 3.6, which contains v. It is easy to see that, v is Wsimplicial in C \e1 , if v is still a non-isolated vertex in C \e1 . Let e1 = {v, w1 , w2 , . . . , wd−2 }

12

M. BIGDELI, A. A. YAZDAN POUR, R. ZAARE-NAHANDI

and e′1 = {v, w1 , . . . , wd−3 }. Since e′1 ∪ {wd−2 } = e1 , there is no circuit in C \ e1 containing
e′1 ∪ {wd−2 }. Hence,





(C \ e1 ) |NC\e [e′ ] /v/w1 / · · · /wd−3 = (C \ e1 ) |NC\e [e′ ] /v/w1 / · · · /wd−3 \ wd−2
1
1 1
 1


= C|NC\e [e′ ] /v/w1 / · · · /wd−3 \ wd−2
1

1

′
wd−2

in this minor. We claim that e2 =
is a minor of C. Pick a W-simplicial vertex

′
v, w1 , w2 , . . . , wd−3 , wd−2
is a simplicial submaximal circuit in C \ e1 .
Proof of the claim. We show that the vertices of e2 satisfy the conditions of
′
, these vertices satisfy in
Corollary 3.7. Note that, by our choice of v and wd−2
Corollary 3.7. Now, let:



D1′ := C|NC [{v}] /v,
D1 := (C \ e1 ) |NC\e [{v}] /v,
1

and for i > 1, let


Di := (C \ e1 ) |NC\e

1

[{v,w1 ,...,wi−1 }]



/v/w1 / · · · /wi−1 ,

Di′ := C|NC [{v,w1 ,...,wi−1 }] /v/w1 / · · · /wi−1 .


It is enough to show that wi is a W-simplicial vertex in Di , for i = 1, . . . , d − 3.
Let F1 and F2 be circuits in Di which contain wi . Since wi is W-simplicial in
Di′ , there exists a circuit F3 ∈ Di′ such that F3 ⊂ (F1 ∪ F2 ) \ {wi }. Then, F3 ⊂
NC\e1 [{v, w1 , . . . , wi−1 }], wi ∈
/ F3 and F3 ∪ A ∈ C|NC\e [{v,w1 ,...,wi−1 }] , for a subset
1
A ⊆ {v, w1 , . . . , wi−1 }. Since wi ∈
/ F3 , we conclude that e1 * F3 ∪ A. Hence
F3 ∪ A ∈ (C \ e1 ) |NC\e

1

[{v,w1 ,...,wi−1 }] .

This means that F3 ∈ Di is a circuit which is contained in (F1 ∪ F2 ) \ {wi }, as
desired.
Continuing this process, by removing all simplicial submaximal circuits containing e′1 ,
after a finite number of steps, say r, the clutter Ce1 ...er has no circuit containing e′1 . Now
we put e′2 = e′1 \ {wd−3 } and we do the same as above, to obtain a subclutter of Ce1 ...er
which has no circuit containing e′2 . Repeating this argument, finally, the vertex v will
be an isolated vertex and the remaining clutter is C \ v which is a d-uniform W-chordal
clutter. Now induction completes the proof.

The following example shows that the containment in Proposition 3.8 is strict.
Example 3.9. Let C be the following 3-uniform clutter with vertex set {1, . . . , 5}:
C = {123, 134, 235, 345} ,
observing {1, 2, 3} by 123 and so on.
1

2

3

4

5

Figure 3. A clutter C in C3 which is not W-chordal

REDUCTION AND CHORDALITY

13

Then C does not have any W-simplicial vertex, so is not W-chordal. But it is clear that
C ∈ C3 . Hence the class of W-chordal clutters is strictly contained in Cd .
3.2. Emtander’s chordal class vs Cd . Towards partial generalization of Fröberg’s theorem, E. Emtander in [7] has also defined several concepts of chordality (called triangulated,
triangulated*, chordal and having perfect elimination ordering) by different approaches
and he showed that all of these concepts are the same [7, Theorem-definition 2.1]. He also
made a good discussion about different attempts on defining chordal clutters in section
2.2 of [7]. Next, he defined the notion of “generalized chordal clutter” as a generalization
of his previous objects, celebrating by showing that such clutters admit linear resolutions
over any field K. In the following, we show that the class of generalized chordal clutters
as defined by Emtander is strictly contained in Cd .
Definition 3.10 ([7, Definition 4.1]). A generalized chordal clutter is a d-uniform clutter,
obtained inductively as follows:
(i) Cn,d is a generalized chordal clutter for n, d ∈ N;
(ii) If C is generalized chordal, then so is C ∪Ci,d Cn,d , for 0 ≤ i < n (This we think of
glueing Cn,d to C by identifying Cn,d with the corresponding part, Ci,d of C);
(iii) If C is generalized chordal, F ⊂ V (C) with |F | = d and there exists e ⊂ F ,
|e| = d − 1, with e ∈
/ SC(C), then C ∪ F is generalized chordal.
Let us denote by ‘E-chordal’, the class of generalized chordal clutters as defined by
Emtender.
Remark 3. A d-uniform clutter C which is obtained inductively by (i)-(ii) of Definition 3.10,
is called chordal by Emtander while chordal in thispaper, is an element of Cd . Emtander
showed that, if C is an E-chordal clutter, then I C¯ has a linear resolution over any field
([7, Theorem 4.1]). In particular, if C is a chordal clutter in Emtander’s sense, then I C¯
has a linear resolution over any
 field. In his later work, he showed that for a chordal
clutter C, in fact, the ideal I C¯ has linear quotients [8] while it is still an open question
whether this is true for generalized chordal clutters as well.
In the following, we show that, E-chordal clutters are strictly contained in Cd . To do
this, first we prove the following lemma.
Lemma 3.11. Let v ∈ [n] and T be the set {e ⊂ [n] : |e| = d − 1, v ∈ e}. Then, by a
suitable ordering of the elements of T , T = {e1 , . . . , em }, we have
ei ∈ Simp ((Cn,d \ e1 ) \ · · · \ ei−1 ) ,
for 2 ≤ i ≤ m.
Proof. Without loss of generality we may assume that v = 1. We define a total order on
T as follows:
let e = {1, i1 , i2 , . . . , id−2 } and e′ = {1, j1 , j2 , . . . , jd−2 }, where 1 < i1 < i2 < · · · <
id−2 and 1 < j1 < j2 < · · · < jd−2 . Then e ≺ e′ if and only if there exists an
integer t such that i1 = j1 , . . . , it−1 = jt−1 and it < jt .
Now, let T = {e1 , . . . , em } with e1 ≺ e2 ≺ · · · ≺ em . Clearly, e1 = {1, 2, . . . , d − 1}, and
since Cn,d is d-complete we have N [e1 ] = [n] which is a clique of Cn,d and so e1 ∈ Simp(Cn,d ).
Set D0 := Cn,d , and for i ≥ 1, let Di := Di−1 \ ei . Let i > 1 and assume that
ei−1 ∈ Simp (Di−2 ) and ei = {1, i1 , . . . , id−2 } ∈ SC (Di−1 ) with 1 < i1 < · · · < id−2 . We
claim that NDi−1 [ei ] = ei ∪ {id−2 + 1, . . . , n}.

14

M. BIGDELI, A. A. YAZDAN POUR, R. ZAARE-NAHANDI

Proof of the claim. To show that {id−2 + 1, . . . , n} ⊆ NDi−1 [ei ], pick an element
j ∈ {id−2 + 1, . . . , n}. We show that ei ∪ {j} ∈ Di−1 . It will follow that j ∈
NDi−1 [ei ]. Since ei ∪ {j} ∈ Cn,d , it is enough to prove that ek 6⊂ ei ∪ {j}, for
all 1 ≤ k ≤ i − 1. Suppose that there exists 1 ≤ k ≤ m, k 6= i, such that
ek ⊂ ei ∪ {j}. So, ek = ({j} ∪ ei ) \ {is } for some 1 ≤ s ≤ d − 2. Since j > il , for
all 1 ≤ l ≤ d − 2, we have ei ≺ ek . So k > i, which implies that ek 6⊂ ei ∪ {j}.
Therefore, ei ∪ {j} ∈ Di−1 .
Conversely, suppose that j ∈ NDi−1 [ei ] \ ei . Then ei ∪ {j} ∈ Di−1 . Thus
ek 6⊂ ei ∪ {j} for all 1 ≤ k ≤ i − 1. In particular, ek 6= ({j} ∪ ei ) \ {il }, for
all 1 ≤ l ≤ d − 2. Since il 6= 1, we have ({j} ∪ ei ) \ {il } ∈ T and so for any
1 ≤ l ≤ d − 2 there exists i + 1 ≤ kl ≤ m such that ekl = ({j} ∪ ei ) \ {il }. Since
kd−2 > i, the order of elements of T implies that ei ≺ ekd−2 , and so j > id−2 .
Hence NDi−1 [ei ] \ ei ⊆ {id−2 + 1, . . . , n}.
Now, we prove that NDi−1 [ei ] is a clique in Di−1 . Let F ⊆ NDi−1 [ei ] with |F | = d. We
show that F ∈ Di−1 . Since F ∈ Cn,d , it is enough to prove that F does not contain any ek
with k < i.
Assume that ek ⊂ F for some k < i. Since ek ⊂ NDi−1 [ei ] and k 6= i, there exists
j ∈ {id−2 + 1, . . . , n} such that j ∈ ek . Therefore, j > il for all il ∈ ei and hence ei ≺ ek
which implies that k > i. Thus ek 6⊂ F for all 1 ≤ k ≤ i − 1, as desired. This completes
the proof.

Corollary 3.12. The complete clutter Cn,d is chordal.
Proposition 3.13 (E-chordals are chordal). If C is a d-uniform E-chordal clutter,
then C ∈ Cd .
Proof. The proof is recursive as in the definition of E-chordal clutters. First note that by
Corollary 3.12, the clutter C is chordal if it is a complete clutter. Assume that C = D ∪ F ,
where D is E-chordal and F ⊂ V (C) is such that |F | = d and there exists e ⊂ F , |e| = d−1,
with e ∈
/ SC (D). Since F is the only circuit containing e, we conclude that, e ∈ Simp (C).
Moreover, C \ e = D. So induction on the number of circuits of C shows that C ∈ Cd .
Suppose now that C = D ∪Ci,d Cn,d . In this case there exists v ∈ V (Cn,d ) \ V (D).
Without loss of generality we may suppose that v = n. Lemma 3.11 implies that, with
a suitable ordering of all submaximal circuits of Cn,d containing v, say e1 , . . . , em , we
have e1 ∈ Simp (Cn,d ) and ej ∈ Simp (Cn,d \ e1 \ · · · \ ej−1 ), for 2 ≤ j ≤ m. Since v ∈
V (Cn,d ) \ V (D), we have e1 ∈ Simp (C) and ej ∈ Simp (C \ e1 \ · · · \ ej−1 ) for 2 ≤ j ≤ m.
Clearly, C \ e1 \ · · · \ em = D ∪Ci,d C(n−1),d which is E-chordal. Induction, now completes
the proof.

Example 3.14. The class of d-uniform E-chordal clutters are strictly contained in Cd . To
see this, consider the following 3-uniform clutter C:
C = {123, 124, 134, 235, 245, 345, 125, 135, 145} .
Then, one may check that C is not E-chordal, while C ∈ C3 . Also, it is worth to say that,
the class of E-chordal and W-chordal are not contained in each other (see [24, Example
4.8]).
3.3. Other known chordalities. Another notion of chordality, has been defined by Van
Tuyl and Villarreal in [23]. They called a clutter C (not necessarily d-uniform) chordal,
if every minor of C has a free vertex, that is, a vertex appearing in exactly one circuit of
C. Note that a free vertex is obviously W-simplicial and hence a clutter with free vertex

REDUCTION AND CHORDALITY

15

property, is W-chordal. Let us denote the class of chordal clutters in the sense of Van
Tuyl and Villarreal, by VTV-chordal. It is worth to note that C is a VTV-chordal if and
only if C = F(∆), where ∆ is the clique complex of a chordal graph ([24, Example 4.5]).
Hence this class is a small subclass of W-chordal clutters.
Another notion of chordality can be found in [3], where the authors defined the concept
of ‘resolution l-chordal’ for a simplicial complex. Due to [3, Section 3], a simplicial complex
∆ is resolution l-chordal, if H̃l (∆W ; K) = 0, for every subset W of vertices of ∆. Now,
let ∆ be a simplicial complex such that I∆ is generated by elements of degree d. It is
well-known and immediately concluded from Hochster’s formula [16, Theorem 5.1] that
I∆ has a d-linear resolution, if and only if H̃i (∆W ; K) = 0, for every subset W of vertices
of ∆ and for all i 6= d − 2. With the notion as in [3], this is equivalent to saying that
∆ is resolution l-chordal for all l 6= d − 2. In [3, Theorem 5.1], the authors refined this
condition with saying that ∆ is resolution l-chordal for all integers l ∈ [d − 1, 2d − 3].
Hence, chordality in [3] may be viewed as a refinement of the Hochster’s formula.
Most of the attempts to generalize Fröberg’s theorem have been intended to extend the
notion of chordal graphs to higher dimensions and to show that, with a new definition,
the associated ideal has a linear resolution but not vice versa. But, in the work of Connon
and Faridi [4], the direction is in a different way. Indeed, the authors defined the concept
of ‘chorded complexes’ and showed that, if I∆ has a linear resolution over any field K,
then ∆ is chorded [4, Corollary 6.2]. Let us denote the chorded class as defined by Connon
and Faridi, by CF-chordal. There are examples of CF-chordal complexes, whose associated
ideals do not have linear resolution (see e.g. [4, Example 7.2]), and obviously such examples
do not belong to Cd , by Theorem 3.3.
3.4. Conclusion. Let us denote the class of d-uniform clutters whose circuit ideals have
a linear resolution over any field by LinRes. By the discussions in this section, we obtain
the following diagram:

VTV-chordal ( W-chordal
( Cd ⊆ LinRes ( CF-chordal
E-chordal
A C++ program has been prepared to check whether a d-uniform clutter belongs to
the class Cd . Using this program, we checked some strange examples which have linear
resolution over any field and we found that all are in the class Cd . Some of these examples
are [12, Examples 5 and 7] and [6, Theorem 3.5]. The source code of this program and the
details of computations can be found in [1]. Motivated by the above diagram and these
evidences, we propose the following question:

Question 1. Does there exist any d-uniform clutter C such that the ideal I C¯ has a linear
resolution over any field, but C is not in the class Cd ?

3.5. Linear quotients. Let C =
6 Cn,d be a d-uniform clutter and I = I C¯ . If C ∈ Cd ,
then by Theorem 3.3, we know that I has a d-linear resolution over any field. On the
other hand, ideals with linear quotients which are generated in a same degree, have also
linear resolutions over any field. So it is natural to ask, whether the ideal associated to
a chordal clutter has linear quotients. In the following example we show that the ideals
associated to chordal clutters are not contained in the class of ideals with linear quotients.
However, it is known that, if G is a chordal graph, then I Ḡ (and all of its powers) has
linear quotients [13, Corollary 3.2].

16

M. BIGDELI, A. A. YAZDAN POUR, R. ZAARE-NAHANDI

Example 3.15. Let ∆ be a triangulation of the dunce hat with 8 vertices as shown in
Figure 4, which is originally introduced by Zeeman [25]. Let C be the 5-uniform clutter
¯ , where ∆
¯ = h[8] \ F : F ∈ F (∆)i.
C = C8,5 \ F ∆
1

3

3
6
2

5

7
4

1

2

8

3

2

1

Figure 4. A triangulation of the dunce hat

Then C contains 39 circuits and I C¯ = I∆∨ , the Stanley-Reisner ideal ofthe Alexander
dual of ∆. Since ∆ is not shellable [22, Section III, p. 84], the ideal I := I C¯ does not have
linear quotients ([14, Prop. 8.2.5]). But with the following order on simplicial submaximal
circuits of C, we get C ∈ C5 and hence it has a linear resolution over any field.
e1
e7
e13
e19
e25
e31

= 1237
= 1246
= 1346
= 1457
= 2345
= 3457

e2
e8
e14
e20
e26
e32

= 1234
= 1245
= 1345
= 1567
= 2347
= 3467

e3
e9
e15
e21
e27
e33

= 1235
= 1247
= 1347
= 3567
= 2346
= 4567

e4
e10
e16
e22
e28

= 1236
= 1256
= 1367
= 2356
= 2367

e5
e11
e17
e23
e29

= 1467
= 1257
= 1356
= 2578
= 2457

e6
e12
e18
e24
e30

= 1468
= 1267
= 1357
= 2357
= 2456

Question 2. Find a subclass of chordal clutters such that their associated ideal have linear
quotients.
acknowledgement
The authors would like to express their deepest gratitude to Jürgen Herzog, for lots of
valuable discussions during writing this manuscript. The source code of the program [1]
has been prepared by Iman Kiarazm. The authors also would like to thank him for
spending a plenty of time for writing the codes.
References
[1] A Program for Detecting Chordality. available at: www.iasbs.ac.ir/∼yazdan/chordality.html
[2] K. A. Adiprasoto, Higher chordality II: Toric chordality via the McMullen–Weil Lefschetz Map,
preprint, (2015). arXiv:1503.06640
[3] K. A. Adiprasoto E. Nevo, and J. A. Samperhigher, Higher chordality I. From graphs to complexes,
preprint, (2015). arXiv:1503.05620
[4] E. Connon and S. Faridi, Chorded complexes and a necessary condition for a monomial ideal to have
a linear resolution, J. Combin. Theory Ser. A, 120, no. 7, pp. 1714–1731, (2013).
[5] G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 38, pp. 71–76, (1961).
[6] A. M. Duval, B. Goeckner, C. J. Klivans and J. L. Martin, A non-partitionable Cohen-Macaulay
simplicial complex, preprint, (2015). arXiv:1504.04279

REDUCTION AND CHORDALITY

17

[7] E. Emtander, A class of hypergraphs that generalizes chordal graphs, Math. Scand. 106, no. 1, pp.
50–66, (2010).
[8] E. Emtander, F. Mohammadi, and S. Moradi, Some algebraic properties of hypergraphs, Czechoslovak
Mathematical Journal, vol 61, no. 3, pp. 577–607, (2011).
[9] J. A. Eagon and V. Reiner, Resolutions of Stanley-Reisner rings and Alexander duality, J. Pure and
Applied Algebra 130, pp. 265–275, (1998).
[10] R. Fröberg, On Stanley–Reisner rings, in: Topics in algebra, Banach Center Publications, 26 Part 2,
pp. 57–70, (1990).
[11] H. T. Hà and A. Van Tuyl, Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers,
J. Algebraic Combin. 27 (2), pp 215–245, (2008).
[12] M. Hachimori, Decompositions of two-dimensional simplicial complexes, Discrete Mathematics, 308,
Issue 11, pp. 2307–2312, (2008).
[13] J. Herzog and T. Hibi, The depth of powers of an ideal, J. Algebra, 291, pp. 534–550, (2005).
[14] J. Herzog and T. Hibi, Monomial Ideals, in: GTM 260, Springer, London, (2011).
[15] J. Herzog and T. Hibi and X. Zheng, Monomial ideals whose powers have a linear resolution, Math.
Scand. 95 , pp. 23–32, (2004).
[16] M. Hochster, Cohen-Macaulay rings, combinatorics, and simplicial complexes, in: Ring Theory, II,
Proc. Second Conf., Univ. Oklahoma, Norman, Okla., 1975, in: Lecture Notes in Pure and Appl.
Math., vol. 26, Dekker, New York, 1977, pp. 171–223.
[17] M. Katzman, Characteristic-independence of Betti numbers of graph ideals, Journal of Combinatorial
Theory, Series A, vol. 113 (3), pp 435–454, (2006).
[18] M. Morales, A. Nasrollah Nejad, A. A. Yazdan Pour and R. Zaare-Nahandi, Monomial ideals with
3-linear resolutions, Annales de la Faculté des Sciences de Toulouse, Sér. 6, 23: (4), pp 877–891,
(2014). arXiv:1207.1790v1
[19] M. Morales, A. A. Yazdan Pour and R. Zaare-Nahandi, The regularity of edge ideals of graphs, J. Pure
and Applied Algebra, vol. 216, issue 12, pp. 2714–2719 (2012).
[20] M. Morales, A. A. Yazdan Pour and R. Zaare-Nahandi, Regularity and Free Resolution of Ideals which
are Minimal to d-linearity, to appear in Math, Scand. (2012). arXiv:1207.1789v1
[21] B. Sturmfels, Four counterexamples in combinatorial algebraic geometry, J. Algebra 230, 282–294,
(2000).
[22] R.P. Stanley, Combinatorics and Commutative Algebra, second ed., Birkhäuser, Boston, (1996).
[23] A. Van Tuyl and R. H. Villarreal, Shellable graphs and sequentially Cohen-Macaulay bipartite graphs.
J. Combin. Theory Ser. A, 115(5): pp 799–814, (2008).
[24] R. Woodroofe, Chordal and sequentially Cohen-Macaulay clutters, Electron. J. Combin. 18, no. 1,
Paper 208, 20 pages, (2011). arXiv:0911.4697v4
[25] E. C. Zeeman, On the dunce hat, Topology 2, 341–358, (1963).
department of mathematics, institute for advanced studies in basic sciences (IASBS),
p.o.box 45195-1159, zanjan, iran
E-mail address: m.bigdelie@iasbs.ac.ir, yazdan@iasbs.ac.ir, rashidzn@iasbs.ac.ir

