arXiv:1708.07372v1 [] 24 Aug 2017

Chordality of Clutters with Vertex Decomposable Dual and
Ascent of Clutters
Ashkan Nikseresht
Department of Mathematics, Institute for Advanced Studies in Basic Sciences,
P.O. Box 45195-1159, Zanjan, Iran.
E-mail: ashkan nikseresht@yahoo.com

Abstract
In this paper, we consider the generalization of chordal graphs to clutters proposed by Bigdeli, et al in J. Combin. Theory, Series A (2017). Assume that C is
a d-dimensional uniform clutter. It is known that if C is chordal, then I(C) has a
linear resolution over all fields. The converse has recently been rejected, but the
following question which poses a weaker version of the converse is still open: “if I(C)
has linear quotients, is C necessarily chordal?”. Here, by introducing the concept of
the ascent of a clutter, we split this question into two simpler questions and present
some clues in support of an affirmative answer. In particular, we show that if I(C)
is the Stanley-Resiner ideal of a simplicial complex with a vertex decomposable
Alexander dual, then C is chordal.

Keywords and Phrases: chordal clutter, linear resolution, vertex decomposable simplicial complex, ascent of a clutter, squarefree monomial ideal.
2010 Mathematical Subject Classification: 13F55, 05E40, 05C65.

1

Introduction

In this paper all rings are commutative with identity, K is a field and S = K[x1 , . . . , xn ]
is the polynomial ring in n indeterminates over K. Given an arbitrary ideal I of S,
we can get a monomial ideal by taking its initial ideal or its generic initial ideal with
respect to some monomial order. Many of the properties of I is similar or at least
related to its (generic) initial ideal, especially if I is graded (see, for example, [8, Section
3.3 & Corollary 4.3.18]). Also if I is a monomial ideal of S then its polarization is a
squarefree monomial ideal, again with algebraic properties similar to I (see [8, Section
1.6]). Therefore, if we know the algebraic properties of squarefree monomial ideals well,
then we can understand many of the algebraic properties of much larger classes of ideals.

1

On the other hand, squarefree monomial ideals have a combinatorial nature and
correspond to combinatorial objects such as simplicial complexes, graphs, clutters and
posets. Many researchers have tried to characterize algebraic properties of squarefree
monomial ideals, using their combinatorial counterparts, see for example [9] and Part
III of [8] and their references. In this regard, two important objectives are to classify
combinatorially the squarefree monomial ideals which are Cohen-Macaulay or those
which have a linear resolution (either over every field or over a fixed field). Indeed these
two tasks are equivalent under taking Alexander dual.
A well-known theorem of Fröberg states that if I is a squarefree monomial ideal
generated in degree two, then I has a linear resolution if and only if I is the edge ideal
of the complement of a choral graph. Motivated by this, many have tried to generalize
the concept of chordality to clutters or simplicial complexes in such a way that at least
one side of Fröberg’s theorem stays true in degrees > 2 (see, for instance, [2, 6, 13]). One
of the most promising such generalizations seems to be the concept of chordal clutters
presented in [2]. In [2] it is shown that many other classes of “chordal clutters” defined
by other researchers, including the class defined in [13] which we call W-chordal clutters,
is strictly contained in the class defined in [2]. They also show that if a clutter is chordal,
then the circuit ideal of its complement has a linear resolution over every field. Several
clues were presented in [1, 2] supporting the correctness of the converse (see [2, Question
1]). But recently a counterexample to the converse was presented by Eric Babson (see
Example 2.3). Despite this it is still unknown whether the following statement which is
a weaker version of the converse is true or not: “if the circuit ideal of the complement of
a clutter has linear quotients, then that clutter is chordal.” Moreover, in [1], it is shown
that many numerical invariants of the ideal corresponding to a chordal clutter can be
combinatorially read off the clutter.
Here, after presenting a brief review of the main concepts and setting the notations,
in Section 3 we prove that if the Alexander dual of the clique complex of a clutter C is
vertex decomposable, then C is chordal. As clique complexes of W-chordal clutters are
vertex decomposable, this generalizes the results of Subsection 3.1 of [2]. Then in Section
4, we define the notion of the ascent of a clutter and show how we can use this concept
to divide the question “is C chordal, given that the circuit ideal of the complement of C
has linear quotients?” into two simpler questions.

2

Preliminaries, notations and a counterexample

Algebraic background. Suppose that I is a graded ideal of S considered with the
standard grading. This grading induces a natural grading on TorSi (K, I). We denote
the degree j part of TorSi (K, I) by TorSi (K, I)j and its dimension over K is denoted
S (I) = β (I). These β ’s are called the graded Betti numbers of I. If there is a
by βij
ij
ij
2

d ≥ 0 such that βij (I) = 0 for j 6= i + d, it is said that I has a linear (or d-linear )
resolution. Also we say that I has linear quotients with respect to an ordered system of
homogenous generators f1 , . . . , ft , if for each i the ideal hf1 , . . . , fi−1 i : fi is generated
by linear forms. It is known that if I is generated in degree d and has linear quotients
with respect to some system of homogenous generators, then I has a d-linear resolution
(see [8, Proposition 8.2.1]).
Now assume that I is a squarefree monomial ideal, that is, I is generated by some
squarefree monomials. Then I has a unique smallest generating set consisting of squareQ
free monomials, say xF1 , . . . , xFt where xF = i∈F xi for F ⊆ [n] = {1, . . . , n}. In this
case, if I has linear quotients with respect to a permutation of this minimal system of
generators, we simply say that I has linear quotients. Also a specific order of minimal
generators of I, for which the aforementioned colon ideals are linear, is called an admissible order. According to [8, Corollary 8.2.4], xF1 , . . . , xFt is an admissible order for the
ideal they generate, if and only if for each i and all j < i, there is a l ∈ Fj \ Fi and a
k < i such that Fk \ Fi = {l}. For more details on these algebraic concepts see [8].
Clutters. A clutter C on the vertex set V = V(C) is a family of subsets of V which
are pairwise incomparable under inclusion. We call the elements of C circuits. For any
subset F of V we set dim F = |F | − 1. If all circuits of C have the same dimension d,
we say that C is a d-dimensional uniform clutter or a d-clutter for short. If v ∈ V(C),
then by C − v we mean the clutter on V(C) \ {v} with circuits {F ∈ C|v ∈
/ F }. For
simplicity, we write for example ab, Ex or Eab instead of {a, b}, E ∪ {x} or E ∪ {a, b}
for a, b, x ∈ V and E ⊆ V . If we assume that V = [n], then I(C) is defined as the ideal
of S generated by {xF |F ∈ C}.
From now on, we always assume that C is a d-clutter with |V(C)| = n. We call C
complete, when all d-dimensional subsets of V = V(C) are in C. A clique of C is a subset
A of V such that CA is complete, where CA = {F ∈ C|F ⊆ A} is the induced d-clutter
on the vertex set A. The complement C of C is the d-clutter with the same vertex set
as C and circuits {F ⊆ V | dim F = d, F ∈
/ C}.
The set {e ⊆ V | dim e = d − 1, ∃F ∈ C e ⊆ F } is called the set of maximal
subcircuits of C and is denoted by MS(C). For a (d − 1)-dimensional subset e of V , the
closed neighborhood NC [e] is defined as e ∪ {v ∈ V |ev ∈ C}. If e ∈ MS(C), then C − e
means the clutter on the vertex set V with circuits {F ∈ C|e 6⊆ F }.
A maximal subcircuit e of C is called a simplicial maximal subcircuit, when NC [e] is
a clique. We denote the set of all simplicial maximal subcircuits of C by SMS(C). If
for each 1 ≤ i < t there is an ei ∈ SMS(Ci−1 ), where C0 = C and Ci = Ci−1 − ei , such
that Ct has no circuits, then C is called chordal (see [2, Section 3]). In the case that
d = 1 (that is, C is graph) this notion coincides with the usual notion of chordal graphs.
Theorem 3.3 of [2] states that if C is chordal and not complete, then I(C) has a linear
3

resolution over every field. There is an example showing that the converse is not true,
that is, there is a non-chordal clutter C with I(C) having a linear resolution over every
field (see Example 2.3). But it is still unknown whether there is a non-chordal clutter C
with I(C) having linear quotients. For further reference, we label this statement:
(A) If I(C) has linear quotients, then C is chordal.
Simplicial complexes. A simplicial complex ∆ on the vertex set V = V(∆) is a
family of subsets of V (called faces of ∆) such that if A ⊆ B ∈ ∆, then A ∈ ∆. The
dimension of ∆ is defined as dim ∆ = maxF ∈∆ dim F . The set of maximal faces of ∆
which are called facets is denoted by Facets(∆). If |Facets(∆)| = 1, then ∆ is called a
simplex.
If all facets of ∆ have the same dimension we say that ∆ is pure. In this case
Facets(∆) is a d-dimensional uniform clutter. Also if D is a clutter, then hDi denotes
the simplicial complex ∆ with Facets(∆) = D. It should be clear that hFacets(∆)i = ∆
and Facets(hDi) = D, for any simplicial complex ∆ and any (not necessarily uniform)
clutter D. Another simplicial complex associated to a d-clutter C is the clique complex
∆(C) of C defined as the family of all subsets L of V(C) with the property that L is a
clique in C. Note that all subsets of V(C) with size ≤ d are cliques by assumption.
For a face F of ∆, we define link∆ F = {G \ F |F ⊆ G ∈ ∆}, which is a simplicial
complex on the vertex set V \ F . Also if v ∈ V , ∆ − v is the simplicial complex on the
vertex set V \ {v} with faces {F ∈ ∆|v ∈
/ F }.
Assuming that V(∆) = [n], the ideal of S generated by {xF |F is a minimal non-face
of ∆} is called the Stanley-Reisner ideal of ∆ and is denoted by I∆ . When IS∆ is a
Cohen-Macaulay ring, ∆ is said to be Cohen-Macaulay over K.
ed (∆) = C
ed (∆, A) the
Let A be a commutative ring with identity and denote by C
free A-module whose basis is the set of all d-dimensional faces of ∆. Consider the
ed (∆) → C
ed−1 (∆) defined by
A-homomorphism ∂d : C
d
X
∂d ({v0 , . . . , vd }) =
(−1)i {v0 , . . . , vi−1 , vi+1 , . . . , vd },
i=0

e• , ∂• ) is a complex of
where v0 < · · · < vd for a fixed total order < on V(∆). Then (C
free A-modules and A-homomorphisms called the augmented oriented chain complex of
e i (∆; A).
∆ over A. We denote the i-th homology of this complex by H
By the Alexander dual of a simplicial complex ∆ we mean ∆∨ = {V(∆) \ F |F ⊆
V(∆), F ∈
/ ∆} and also we set C∨ = {V(C) \ F F ∈ C}. Then it follows from the
Eagon-Reiner theorem ([8, Theorem 8.1.9]) and the lemma below that I(C) has a linear
resolution over K, if and only if hC∨ i is Cohen-Macaulay over K. For more details on
simplicial complexes and related algebraic concepts the reader is referred to [8]. We
frequently use the following lemma in the sequel without any further mention.
4

Lemma 2.1 ([9, Lemma 1.1]). Let C be a d-clutter. Then
(i) I(C) = I∆(C) ;
(ii) hC∨ i = (∆(C))∨ .
Recall that ∆W = {F ∈ ∆|F ⊆ W } where W ⊆ V .
Theorem 2.2 (Fröberg [7]). The ideal I∆ has a t-linear resolution over K, if and only
e i (∆W ; K) = 0 for all W ⊆ V(∆) and i 6= t − 2.
if H
Note that in the case that ∆ = ∆(C), then since all possible faces of dimension less
e i (∆W ; K) = 0 for all W ⊆ V and i < d − 1. Hence I(C)
than d are in ∆, it follows that H
e i (∆W ; K) = 0 for all W ⊆ V(∆)
has a (d + 1)-linear resolution over K, if and only if H
and i ≥ d. Using this we can state an example of a non-chordal clutter C with I(C)
having a linear resolution over every field. This example is due to Eric Babson who
visited IASBS as a lecturer in the first RSCAAG.
Example 2.3 (Babson). Let C be the 2-clutter shown in Fig. 1A triangulation of the
dunce hat; the circuits are the trianglesfigure.1 which is a triangulation of the dunce
hat. Then ∆ = ∆(C) is obtained by adding the missing edges (1-dimensional subsets
of vertices) to ∆0 = hCi, since C has no cliques on more that 3 vertices. Therefore,
e t (∆; K) = H
e t (∆0 ; K) for every t ≥ 2. It is known that the dunce hat is a contractible
H
e t (∆0 ; K) for all t ≥ 2. Also it is easy to verify that for any W ( [8],
space and hence 0 = H
CW is chordal (indeed, any proper subclutter of C has an edge which is contained in
exactly one triangle and hence is simplicial) and thus has a linear resolution over every
e t (∆W ; K) = H
e t (∆(CW ); K) = 0 for all t ≥ 2. Consequently, by
field. Therefore, H
Föberg’s theorem I∆ = I(C) has a linear resolution over every field.
1
3

2

3

6

5

7
2

4
8

1
3

1
2

Figure 1: A triangulation of the dunce hat; the circuits are the triangles

3

Clutters with vertex decomposable dual are chordal

A vertex v of a nonempty simplicial complex ∆ is called a shedding vertex, when no face
(or equivalently facet) of link∆ (v) is a facet of ∆ − v. When ∆ is pure, one can readily
5

check that v is a shedding vertex if and only if ∆ − v is pure with dim(∆ − v) = dim(∆).
Recall that a nonempty simplicial complex ∆ is called vertex decomposable, when either
it is a simplex or there is a shedding vertex v ∈ V (∆) such that both link∆ v and ∆ − v
are vertex decomposable. This concept was first introduced in [10] in connection with
the Hirsch conjecture which has applications in the analysis of the simplex method in
linear programming.
It is well-known that if ∆ is pure and vertex decomposable, then it is shellable and
Cohen-Macullay, hence I∆∨ has a linear resolution and in fact linear quotients. So if C
is the clutter with I(C) = I∆∨ and if statement A is true, C should be chordal. In this
section, we prove that this is indeed the case. By 2.1, in the above situation we have
∆ = (∆(C))∨ = hC∨ i. First we need some lemmas. In the sequel, we assume that C is a
d-clutter and |V(C)| = n.
Lemma 3.1. Suppose that ∆ = hCi and Γ = hC∨ i. Also assume that v ∈ V(Γ) (= V(∆))
and Γ − v is pure of dimension = dim(Γ) (that is, v a shedding vertex of Γ) and set
D = Facets(link∆ (v)). Then D = (Facets(Γ − v))∨ . Moreover, e ∈ SMS(D) if and only
if ev ∈ SMS(C).
Proof. Suppose that F ∈ (Facets(Γ − v))∨ . Thus |F | = (n − 1) − dim(Γ − v) − 1 =
n − 2 − dim(Γ) = n − 2 − (n − d − 2) = d and A = V(Γ − v) \ F ∈
/ Facets(Γ − v). Hence
∨
A∈
/ Facets(Γ) = C and as dim A = dim(Γ), we see that F v = V(∆) \ A ∈ C, that is,
F ∈ Facets(link∆ (v)) = D. So (Facets(Γ − v))∨ ⊆ D. The proof of the reverse inclusion
is similar.
Now assume that e ∈ MS(D). Then for x ∈ V(D) \ e we have ex ∈ D ⇔ exv ∈
Facets(∆) = C. Therefore, ND [e] = NC [ev] \ {v}. If ev ∈ SMS(C) and A ⊆ ND [e], then
Av ⊆ NC [ev] which is a clique and hence Av ∈ C, that is, A ∈ D. So ND [e] is a clique
and e ∈ SMS(C).
Conversely, assume that e ∈ SMS(D) and A ⊆ NC [ev]. We must show A ∈ C. If
v ∈ A, then A \ {v} ⊆ ND [e] and hence A \ {v} ∈ D, which means A ∈ C. Thus suppose
v∈
/ A. If A ∈
/ C, then v ∈ B = V(C)\A ∈ C∨ = Facets(Γ). Consequently, B \{v} ∈ Γ−v
and there is a F ∈ Facets(Γ − v) = D∨ containing B \ {v}. So A0 = V(D) \ F ∈
/ D.
Since dim(Γ − v) = dim Γ = n − d − 2 = |F | − 1 and V(D) = V(C) \ {v}, we see that
|A0 | = d. Also A0 ⊆ A ⊆ NC [ev] \ {v} = ND [e], and as e is simplicial, we get A0 ∈ D, a
contradiction from which the result follows.
Lemma 3.2. Assume that ∆ = hCi and Γ = hC∨ i. Let v be a shedding vertex of Γ and
v ∈ e ∈ MS(Γ). Then v is a shedding vertex of h(C − e)∨ i = ∆(C − e). Furthermore, if
∆0 = hC − ei, then Facets(link∆0 v) = Facets(link∆ v) − e0 , where e0 = e \ {v}.
Proof. Let Γ0 = h(C − e)∨ i and suppose that F ∈ Facets(linkΓ0 v). We have to show
that F is not a facet of Γ0 − v. Note that C∨ ⊆ (C − e)∨ and hence Γ − v ⊆ Γ0 − v.
6

Therefore, it suffices to show that there is a G ∈ Facets(Γ) = C∨ with v ∈
/ G such
0
∨
that F ( G. We know that F v ∈ Facets(Γ ) = (C − e) , so V \ F v ∈
/ C − e where
V = V(C − e) = V(C). As v ∈ e, e 6⊆ V \ F v and thus V \ F v ∈
/ C. It follows that
F v ∈ Γ, that is, F ∈ linkΓ v. No face of linkΓ v is a facet of Γ − v, because v is a shedding
vertex of Γ. Consequently, F is strictly contained in the facet G of Γ − v, as claimed.
The proof of the “furthermore” statement, which follows from definitions, is left to the
reader.
Suppose that v ∈ V(C) has not appeared in any circuit of C. Then chordality (and
many other properties) of C and C − v are equivalent, although V(C) =
6 V(C − v). In
this case, we misuse the notation and write C = C − v.
Lemma 3.3. Assume that ∆ = hCi, v is a shedding vertex of Γ = hC∨ i and D =
Facets(link∆ v). If D is chordal, then there is a sequence e1 , . . . , et with ei ∈ SMS(Ci−1 ),
where C0 = C and Ci = Ci−1 − ei , such that Ct = C − v.
Proof. We prove the statement by induction on |C|. If D = ∅, then C = C − v and the
claim holds trivially. So assume D 6= ∅ and e0 ∈ SMS(D) be such that D − e is chordal.
By 3.1, e = e0 v ∈ SMS(C). Let ∆0 = hC − ei and D0 = Facets(link∆0 v), then according
to 3.2, D0 = D − e0 is chordal and v is a shedding vertex of h(C − e)∨ i. Thus by applying
the induction hypothesis on C − e, the assertion follows.
Lemma 3.4. Suppose that C is obtained from a complete clutter by deleting exactly one
circuit. Then C is chordal.
Proof. Let C = C0 − F , where C0 is a complete clutter and F ∈ C0 . By [2, Corollary
3.11], C0 is chordal and there is a sequence of simplicial maximal subcircuits e1 , . . . , et
which sends C0 to the empty clutter. By symmetry of C0 , e1 can be any maximal
subcircuit of C0 and we can assume e1 ⊆ F . Hence C − e = C0 − e is chordal and it is
easy to see that e ∈ SMS(C), that is, C is also chordal.
Now we are ready to state the main result of this section.
Theorem 3.5. Assume that C is a d-clutter and hC∨ i is vertex decomposable. Then C
is chordal.
Proof. We use induction on the number of vertices of C. Let ∆ = C and Γ = hC∨ i. If
Γ is a simplex, then C is obtained from a complete clutter by deleting one circuit and by
3.4 is chordal. Thus assume that Γ is not a simplex. So there is a shedding vertex v of Γ
such that both Γ−v and linkΓ v are vertex decomposable. Setting D = Facets(link∆ v), it
follows from 3.1 that hD∨ i = Γ − v and is vertex decomposable. Therefore, D is chordal
by induction hypothesis and by 3.3, there is a sequence e1 , . . . , et with ei ∈ SMS(Ci−1 ),
7

where C0 = C and Ci = Ci−1 − ei , such that Ct = C − v. Consequently, we just need to
show that C − v is chordal. For this we show that h(C − v)∨ i = linkΓ v, which is vertex
decomposable and the result follows by the induction hypothesis:
F ∈ Facets(linkΓ v) ⇔ F v ∈ Facets(Γ) = C∨ ⇔ V \ F v ∈
/C
⇔ (V \ {v}) \ F ∈
/ C − v ⇔ F ∈ (C − v)∨ .

In [13], a vertex of a not necessarily uniform clutter, D is called a simplicial vertex if
for every e1 , e2 ∈ D with v ∈ e1 , e2 , there is an e3 ∈ D such that e3 ⊆ (e1 ∪e2 )\{v}. Also
the contraction D/v is defined as the clutter of minimal sets of {e \ {v}|e ∈ D}. Now if
every clutter obtained from D by a sequence of deletions or contractions of vertices has
a simplicial vertex, then Woodroofe in [13] calls D chordal and we call it W-chordal. In
[2, Corollary 3.7] it is proved that every W-chordal clutter which is uniform is chordal.
As a corollary of the above theorem, we can get the following slightly stronger version
of Corollary 3.7 of [2].
Corollary 3.6. Suppose that D is a (not necessarily uniform) W-chordal clutter, d =


min |F | F ∈ D and C = F ∈ D |F | = d . Then C is chordal.
Proof. Theorem 6.9 of [13] states that the Alexander dual of the independence complex
of C (for the definition of independence complex, see [13, p. 3]) is vertex decomposable.
But independence complex of C is exactly ∆(C) and hence the result follows from Theorem 3.5prop.3.5.

4

Chordality and ascent of clutters

In [6] the concept of a d-chorded simplicial complex is defined and it is proved that if I∆
has a (d + 1)-linear resolution over a field of characteristic 2, then ∆ is d-chorded. Then
in [5, Theorem 18], the same authors show that I∆ has a (d + 1)-linear resolution over a
field of characteristic 2, if and only if ∆ is d-chorded, and moreover ∆[m] is m-chorded for
all m > d (∆[m] is the pure m-skeleton of ∆, that is, the simplicial complex whose facets
are faces of ∆ with dimension m). Now if I∆ = I(C) for a d-clutter C, then ∆ = ∆(C)
and hence Facets(∆[m] ) is just the set of cliques of C with dimension m. Therefore, the
aforementioned results show that to study when I(C) has a linear resolution, it may be
useful to consider the higher dimensional clutters Facets(∆(C)[m] ). Motivated by this
observation, we define the ascent of a clutter as follows.
Definition 4.1. Let C be a d-clutter. We call the family of all (d + 1)-dimensional
cliques of C (that is, cliques on d + 2 vertices), the ascent of C and denote it by C+ . In

other words, C+ = Facets ∆(C)[d+1] .
8

Our first result, considers how the property of having a linear resolution behaves
under ascension. Recall that throughout the paper, we assume that C is a d-clutter on
vertex set V with |V | = n.
Proposition 4.2. Let ∆ = ∆(C). Then I(C) has a linear resolution over K, if and
e d (∆W ; K) = 0 for all W ⊆ V .
only if I(C+ ) has a linear resolution over K and H
Proof. Note that if ∆0 = ∆(C+ ), then ∆0W and ∆W differ only in d-dimensional faces
e t (∆0 ; K) = H
e t (∆W ; K) for each t > d and W ⊆ V . Thus the result follows
and hence H
W
directly form Fröberg’s theorem 2.2.
As the following result shows, similar to having a linear resolution, chordality is also
preserved under ascension.
Theorem 4.3. If C is chordal, then so is C+ .
Proof. We use induction on |C|. The result is clear for |C| = 0, 1, where C+ = ∅. Choose
e ∈ SMS(C) such that C − e is chordal. If e is contained in only one circuit, then it is
not contained in any clique on more than d + 1 vertices. Thus C+ = (C − e)+ and the
claim follows the induction hypothesis. So we assume that NC [e] is a clique on at least
d + 2 vertices. Let F be any d + 1 subset of NC [e] with e ⊆ F . If v ∈ NC+ [F ] \ F , then F v
is a clique in C and hence ev ∈ C. This shows that NC+ [F ] ⊆ NC [e]. Let {v1 , . . . , vt } =
+
NC [e] \ e, Fi = evi and Ci = C − F1 − · · · − Fi . Note that C+
i = C − F1 − · · · − Fi . We
+
show that Fi ∈ SMS(C+
i−1 ), if Fi ∈ MS(Ci−1 ). Then as Ct = C − e is chordal it follows
+
by the induction hypothesis that C+
t and hence C are chordal.
Suppose that G ⊆ NC+ [Fi ] and |G| = d+2. Then by the above argument G ⊆ NC [e]
i−1

and hence G ∈ C+ . If vj ∈ G for some j < i, then Fi vj ∈ C+
i−1 . But Fj = evj ⊆ Fi vj
and Fj ∈
/ Ci−1 , a contradiction. Therefore, no vj ∈ G for j < i and hence no Fj ⊆ G for
+
such a j. Thus G is a clique in Ci−1 , that is, G ∈ C+
i−1 and hence Fi ∈ SMS(Ci−1 ).
Next we sate a theorem that shows some connections between deleting elements of
SMS(C+ ) and having a linear resolution.
Theorem 4.4. Suppose that C+ 6= ∅. Then, considering the following statements, we
have i ⇒ ii ⇒ iii.
(i) There is a F ∈ SMS(C+ ) such that I(C − F ) has a linear resolution over K and
also I(C+ ) and I(C − v) have linear resolutions over K for each v ∈ V .
(ii) I(C) has a linear resolution over K.
(iii) For all F ∈ SMS(C+ ), I(C − F ) has a linear resolution over K and also I(C+ )
and I(C − v) have linear resolutions over K for each v ∈ V .
9

e d (∆W ; K) = 0
Proof. i ⇒ ii: Set ∆ = ∆(C). According to 4.2, we have to show that H
for all W ⊆ V . If W ( V , say v ∈ V \ W , then ∆W = ∆(CW ) = ∆((C − v)W ).
Thus by Fröberg’s theorem, as I(C − v) has a linear resolution over K, it follows that
e d (∆W ; K) = 0. Consequently it remains to show that H
e d (∆; K) = 0.
H
Pl
ed (∆; K) with ∂d (x) = 0 where 0 6= ai ∈ K and Fi ∈
Assume that x = i=1 ai Fi ∈ C
C. We have to show that x ∈ Im ∂d+1 . Let F ∈ SMS(C+ ) be such that I(C − F ) has a
linear resolution over K. Assume that for some i, we have Fi = F . As F ∈ MS(C+ ),
there is a G ∈ C+ such that F ⊆ G. Now y = ∂d+1 (ai G) has a term ±ai Fi . Hence in
z = x ∓ y, the coefficient of F is zero. Also ∂d (z) = ∂d (x) ∓ ∂d (y) = 0. Thus we can
ed (∆(C − F ); K) and as I(C − F ) has a linear
assume that for no i, Fi = F . Then x ∈ C
e
resolution, Hd (∆(C − F ); K) = 0. So there are Gi ’s in (C − F )+ ⊆ C+ and bj ’s in K
P
such that x = ∂d+1 ( bj Gj ) ∈ Im ∂d+1 .
ii ⇒ iii: As ∆(C − v)W = ∆(C)W \{v} and by Fröberg’s theorem, I(C − v) has a linear
resolution over K for each v ∈ V . According to 4.2, I(C+ ) also has a linear resolution
over K. Now let F ∈ SMS(C+ ) and also assume that V = [n]. Let L = hxF i and
I = I(C). We have to show I(C − F ) = I + L has a linear resolution over K.
First we compute the minimal generating set of I ∩ L. Suppose that u is one of the
minimal generators of the squarefree monomial ideal I ∩ L. Then as xF |u, we should
have u = xF ∪A for some A ⊆ [n]\F . Since u ∈ I, there is a G0 ∈ C such that G0 ⊆ F ∪A.
Assume |A| > 1 and v ∈ A. Then for no G ∈ C we have G ⊆ F v, else xF v ∈ I ∩ L
which contradicts u being a minimal generator. This means that F v is a clique of C
and hence v ∈ NC+ [F ]. Since v ∈ A was arbitrary, we have F ∪ A ⊆ NC+ [F ] which
is a clique, because F is simplicial. But this contradicts G0 ⊆ F ∪ A and it follows
that |A| = 1, say A = {a}. As G0 ⊆ F a, we get a ∈
/ NC+ [F ]. On the other hand, for
an arbitrary a ∈ B = [n] \ NC+ [F ], it is easy to see that xF a ∈ I ∩ L. Consequently,
I ∩ L = hxF a |a ∈ Bi = xF hxa |a ∈ Bi.
Since multiplying in xF is an S-isomorphism of degree d + 1 from hxa |a ∈ Bi to I ∩ L
and by [8, Corollary 7.4.2], I ∩ L has a (d + 2)-linear resolution over K. Also I and L
have (d + 1)-linear resolutions over K. Now consider the exact sequence
0 → I ∩ L → I ⊕ L → I + L → 0.
Writing the (i + j)-th degree part of the long exact sequence of TorS (K, −) applied on
the above sequence, we get the exact sequence
· · · → TorSi (K, I ⊕ L)i+j → TorSi (K, I + L)i+j → TorSi−1 (K, I ∩ L)i−1+(j+1) → · · · .
If j 6= d + 1 then both flanking terms are zero and hence the middle term is also zero.
This means that I + L has a (d + 1)-linear resolution, as required.
Note that 4.4i does not necessarily follows 4.4iii, since we may have a clutter C satisfying
10

4.4iii, but with SMS(C+ ) = ∅. Although, it should be mentioned that the author could
not find such an example. Thus we raise the following question.
Question 4.5. Is the three statements of 4.4 equivalent for a d-clutter C with a nonempty ascent?
Also as the following remark shows, we have proved a little more than the statement
of 4.4.
Remark 4.6. If in 4.4i, we replace “F ∈ SMS(C+ )” with “F ∈ MS(C+ )”, the same
proof shows that still the theorem is valid. In fact, in the proof of i ⇒ ii, we proved that
if there exists F ∈ MS(C+ ) such that I(C − F ) has a linear resolution over K, then
e d (∆(C); K) = 0.
H
P
The following is also a corollary to the proof of 4.4. Recall that βi (I) = j βij (I).
Corollary 4.7. Suppose that I = I(C) has a linear resolution over K, F ∈ SMS(C+ )
and J = I(C − F ). Then J has a linear resolution over K with Betti numbers βi (J) =

βi (I) + ti , where t = n − |NC+ [F ]|.
Proof. Suppose that L and B are as in the proof of ii ⇒ iii. So t = |B| and if
L0 = hxa |a ∈ Bi, then I ∩ L = xF L0 and βi (I ∩ L) = βi (L0 ) which by [8, Corollary 7.4.2]

 Pt−1 k
P
= k=i i = ti . Also β0 (L) = 1 and βi (L) = 0 for all i > 0.
is equal to tk=1 k−1
i
Thus by taking dimK of the long exact sequence of TorSi (K, −) in the proof of 4.4, we
get βi (J) = βi (I + L) = βi (I) + βi (L) + βi−1 (I ∩ L), where the last term is assumed to
be zero if i = 0.
In the rest of the paper, we study if we can get some results similar to 4.4 for having
linear quotients or being chordal instead of having a linear resolution. For having linear
quotients we have:
Theorem 4.8. Suppose that I(C) has linear quotients. Then I(C+ ), I(C − F ) and
I(C − v) have linear quotients for each F ∈ SMS(C+ ) and v ∈ V(C).
Proof. If we denote the ideal generated by all squarefree monomials in I with degree
t by I[t] , then it is easy to see that I(C+ ) = I(C)[d+2] . Hence the fact that I(C+ )
has linear quotients follows from [12, Corollary 2.11]. But for the convenience of the
readers, we present a direct shorter proof for this. Assume that xF1 , . . . , xFt is an
admissible order of I(C). Then C+ = {Fi v|v ∈ V \ Fi , 1 ≤ i ≤ t}. For each 1 ≤ i ≤ t, let
Ci = {Fi v|v ∈ V \ Fi } \ (∪j<i Cj ) and suppose that Ci = {Fi1 , . . . , Firi }. We prove that
F11 , . . . , F1r1 , . . . , Ft1 , . . . , Ftrt corresponds to an admissible order for I(C+ ).
Consider two circuits Fij , Fi0 j 0 of C+ with i ≤ i0 . If i = i0 , then |Fij \ Fi0 j 0 | = 1
and hence the admissibility condition holds trivially for them. Thus we assume i < i0 .
11

Therefore by assumption there is a l ∈ Fi \ Fi0 and a k < i0 such that Fk \ Fi0 = {l}.
Let Fi0 j 0 \ Fi0 = {v}. Note that as Fi0 j 0 ∈ Ci0 , there is no j < i0 with Fi0 j 0 ∈ Cj by the
definition of Ci ’s. So v 6= l, else Fi0 j 0 = Fk ∪ (Fi0 \ Fk ) and as |Fi0 \ Fk | = 1, we have
Fi0 j 0 ∈ Cj for some j ≤ k, a contradiction. Consequently, v ∈
/ Fk and Fk v which is a
+
circuit of C , should appear in some Cj with j ≤ k. Noting that Fk v \ Fi0 j 0 = {l}, the
proof is concluded.
Now assume that F ∈ SMS(C+ ). We show that if we add xF to an admissible order
of I(C), we get an admissible order of I(C − F ) = I(C) + hxF i. We just need to show
if G ∈ C, then there is a G0 ∈ C and an l ∈ G such that G \ F = {l}. Since NC+ [F ]
is a clique of C, G 6⊆ NC+ [F ], say l ∈ G \ NC+ [F ]. Then F l ∈
/ C+ and hence there is a
G0 ⊆ F l with G0 ∈ C. So G0 \ F = {l}, as required.
Finally, note that if xF1 , . . . , xFt is an admissible order for I(C), then by deleting xFi ’s
with v ∈ Fi , we get an admissible order for I(C − v) and I(C − v) has linear quotients.
We do not know whether the converse of the above theorem is correct or if a statement
similar to i ⇒ ii of 4.4 holds for having linear quotients.
Next consider the “chordal version” of 4.4, that is, consider the statements obtained
by replacing “I(D) has a linear resolution over K” with “D is chordal” in the three parts
of 4.4, where the replacement occurs for all clutters D appearing in these assertions.
Then clearly iii ⇒ i for the chordal version. Also 4.3 shows that part of ii ⇒ iii is true
for chordality. We will also show that if C is chordal and F ∈ SMS(C+ ), then C − F is
“d-chorded”, which is condition weaker than being chordal. But before proving this, we
utilize 4.8 to show that if the chordal version of iii ⇒ ii (or i ⇒ ii) holds, then we can
reduce proving statement A to verifying it only for clutters with empty ascent.
In what follows, by a free maximal subcircuit of C, we mean a maximal subcircuit
which is contained in exactly one circuit of C. In the particular case that dim C = 1,
that is C is a graph, free maximal subcircuits are exactly leaves (or free vertices) of the
graph. Also a simplicial complex ∆ is called extendably shellable, if any shelling of a
subcomplex of ∆ could be continued to a shelling of ∆. To see a brief literature review
of this concept and some related results consult [3, Section 3] or [4].
Corollary 4.9. Consider the following statements and also statement A of Section 2
on a uniform clutter C.
(B) If ∅ =
6 C+ is chordal and C − F and C − v are chordal for each F ∈ SMS(C+ ) and
v ∈ V(C), then SMS(C) 6= ∅.
(C) If C+ = ∅ and I(C) has linear quotients, then C has a free maximal subcircuit.
(D) Simon’s Conjecture ([11, Conjecture 4.2.1]): Every d-skeleton of a simplex is extendably shellable.
12

Then: B + C ⇒ A ⇒ C + D.
Proof. Assume that B and C hold. We claim that if I(C) has linear quotients, then
SMS(C) 6= ∅. Then it follows from [9, Theorem 2.1] that A is correct. To prove the
claim, we use induction on (n − d, |C|) considered with lexicographical order. If C+ = ∅,
then as every free maximal subcircuit is simplicial, the claim holds by C. If C+ 6= ∅, then
applying 4.8 and using the induction hypothesis, we see that C+ , C − F and C − v are
chordal for every F ∈ SMS(C+ ) and v ∈ V(C). Consequently, the claim follows from
B.
Now suppose that statement A is correct. If C+ = ∅, then |NC [e]| = d + 1 for
every e ∈ SMS(C) and hence every simplicial maximal subcircuit of C is a free maximal
subcircuit. Therefore, C holds as a special case of A. Finally D follows from [9, Theorem
2.1] by taking Alexander dual or more directly, it follows from [3, Corollary 3.6].
The “chordal version” of ii ⇒ iii, partly states that if C is chordal, then for every
F ∈ SMS(C+ ), C − F should be chordal. The author could neither prove nor reject
this in the general case, but we prove a weaker result. In particular, we will show in
the case that dim C = 1, this is true. For this we need another generalization of chordal
graphs to simplicial complexes presented in [6]. Since the definitions are long, we do
not state the definitions here and refer the reader to [6]. Here we call D ⊆ C a CF-cycle
(resp. face-minimal CF-cycle) of C, if hDi is a d-dimensional cycle (resp. face-minimal
d-dimensional cycle) in the sense of [6, Definition 3.2] (resp. [6, Definition 3.4]). Also
we say that C is d-chorded if the simplicial complex hCi is so as defined in [6, Definition
4.2]. So in the case that dim C = 1, C is 1-chorded if and only if it is a chordal graph.
Moreover, if C is chordal, then by [6, Theorem 6.1], C is d-chorded. We need the following
lemma which presents an equivalent condition for being d-chorded.
Lemma 4.10. The clutter C is d-chorded if and only if every CF-cycle D of C is the
symmetric difference of a family of complete subclutters of C, each on a (d + 2)-subset
of V(D).
Proof. (⇒): By induction on |V(D)|. Since each CF-cycle is a disjoint union of faceminimal CF-cycles, we can assume that D is face-minimal. If D is complete, then
by face-minimality |V(D)| = d + 2 and we are done. Thus we assume that D is not
complete, so that hDi has a chord set ([6, Definition 4.1]). Suppose that Ωi ’s are as in
[6, Definition 4.1] for Ω = hDi. If Di = Facets(Ωi ), then D = D1 ⊕ · · · ⊕ Dk , where ⊕
denotes symmetric difference, and each Di is a CF-cycle on an smaller number of vertices
in V(D). Thus by applying the induction hypothesis on Di ’s we get a decomposition of
D as the symmetric difference of a set of complete subclutters of C on (d + 2)-subsets of
V(D).

13

(⇐): Suppose that D is a face-minimal cycle of C. Then D = D1 ⊕ · · · ⊕ Dt where
Di ’s are complete subclutters of C with size d + 2 and V(Di ) ⊆ V(D). If we set Ω = hDi,
Ωi = hDi i and C = ∪ti=1 Di \ D, then Ω, Ωi ’s and C clearly satisfy the conditions of a
chord set ([6, Definition 4.1]). This means that C is d-chorded.
Theorem 4.11. Suppose that C is a d-chorded clutter (for example, if C is chordal) and
F ∈ SMS(C+ ). Then C − F is d-chorded.
Proof. Suppose that D is a CF-cycle of C − F . Since C is d-chorded and according
to 4.10, there are complete subclutters D1 , . . . , Dt of C on (d + 2)-subsets of V(D) such
that D = ⊕ti=1 Di . We choose Di ’s in a way that m = |{i|F ∈ Di }| is minimum possible.
Assume that m ≥ 1. Because F 6∈ D, m is at least 2. Thus there are two Di , say
D1 , D2 , containing F . Therefore there exist v1 6= v2 ∈ V(D) such that V(Di ) = F vi for
i = 1, 2. Let W = F v1 v2 and C0 = CW . Then since F ∈ SMS(C+ ) and W ⊆ NC+ (F ),
C0 is complete. Now D0 = D1 ⊕ D2 is a CF-cycle in C0 − F . By 3.4, C0 − F is chordal
and hence has a linear resolution over every field. Thus by [6, Theorem 6.1] C0 − F is
d-chorded. Consequently according to 4.10, D0 = D01 ⊕· · ·⊕D0t0 , where D0i ’s are complete
subclutters of C0 − F (and hence C) on (d + 2)-subsets of V(D0 ) ⊆ V(D). By replacing
0
⊕ti=1 D0i instead of D1 ⊕ D2 in the decomposition of D, we get a decomposition with less
terms containing F . This contradicts the choice of the decomposition of D and hence
m = 0. Therefore, the decomposition D = ⊕ti=1 Di is in C − F and the result follows by
4.10.
If C is a graph, we call a F ∈ SMS(C+ ) a simplicial edge of C.
Corollary 4.12. Suppose that C is a chordal graph and F is a simplicial edge of C. Then
C − F is chordal. Hence there is an ordering F1 , . . . , Ft , Ft+1 , . . . , Fm of edges of C such
that for 1 ≤ i ≤ t, Fi is a simplicial edge of the chordal graph Ci = C − F1 − · · · − Fi−1
and for t < i ≤ m, Ci is a tree and Fi is a leaf edge of Ci .
Proof. The first statement is just 4.11 in the case that dim C = 1. Now if C is chordal
and C+ 6= ∅, then SMS(C+ ) 6= ∅ by 4.3. So starting with C, we can delete simplicial
edges until we reach a chordal graph C0 with (C0 )+ = ∅. But a chordal graph without
any cliques on more than two vertices is a tree and hence we can delete leaf edges from
C0 until there is no more edges and the statement is established.
Let C be the graph in Fig. 2A non-chordal graphfigure.2. Then C+ and C − F are
chordal and also I(C+ ) and I(C − F ) have linear quotients for each F ∈ SMS(C+ ).
Despite this C is not chordal, since C − e is a cycle of length 5. Thus the converses of
4.11 and 4.3 do not hold. Also edges of C can be ordered as in 4.12, so the converse
of 4.12 is not true, either. It also should be mentioned that an example of a d-chorded
clutter C with C+ not (d + 1)-chorded, is presented in [5, Example 16].
14

Figure 2: A non-chordal graph
Clearly C holds when dim C = 1. Using the concept of CF-cycles, we show that C
holds when dim C∨ ≤ 1 or equivalently, if n − d ≤ 3. As in [9], by a CF-tree we mean a
clutter C without any CF-cycle.
Proposition 4.13. Assume that C is a d-clutter on n vertices with n ≤ d + 3. If
C+ = ∅ and I(C) has a linear resolution over every field, then C is chordal. In particular,
statement C of 4.9 holds for C.
Proof. Suppose that C+ = ∅ and I(C) has linear resolution over every field. According
to [6, Theorem 6.1], C is d-chorded. But since C has no cliques of size d + 2, it follows
from 4.10 that C has no CF-cycles, that is, C is a CF-tree. Now the result follows from
[9, Corollary 3.7].
The proof of Corollary 3.7 of [9] uses Alexander dual. We end this paper mentioning
that more generally, one can get a statement equivalent to C by passing to the Alexander
dual of hCi. Indeed, by arguments quite similar to [9, Theorem 3.6] one can see that
C holds for all d-clutters on n vertices, if and only if statement (ii) of [9, Theorem 3.6]
holds, when we replace “Cohen-Macaulay over Z2 ” in that statement with “shellable”.
Acknowledgement The author would like to thank Rashid Zaare-Nahandi and Ali
Akbar Yazdan Pour for their helpful discussions and comments.

References
[1] M. Bigdeli, J. Herzog, A. A. Yazdan Pour and R. Zaare-Nahandi, Simplicial orders
and chordality, J. Algebraic Combin., 45(4), 1021–1039, 2017.
[2] M. Bigdeli, A. A. Yazdan Pour and R. Zaare-Nahandi, Stability of betti numbers
under reduction processes: towards chordality of clutters, J. Combin. Theory Ser.
A, 145, 129–149, 2017.
[3] —, Clutters with linear quotients, preprint.
[4] A. Björner and K. Eriksson, Extendable shellability for rank 3 matroid complexes,
Discrete Math. 132, 373–376, (1994).
15

[5] E. Connon and S. Faridi, A criterion for a monomial ideal to have a linear resolution
in characteristic 2, Elec. J. Combin. 22(1), #P1.63, 2015.
[6] —, Chorded complexes and a necessary codition for a monomial ideal to have a
linear resolution, J. Combin. Theory Ser. A 120, 1714–1731, 2013.
[7] R. Fröberg, Rings with monomial relations having linear resolutions, J. Pure Appl.
Algebra 38, 235–241, 1985.
[8] J. Herzog and T. Hibi, Monomial Ideals, Springer-Verlag, London ,2011.
[9] A. Nikseresht and R. Zaare-Nahandi, On generalization of cycles and chordality
to clutters from an algebraic viewpoint, Algebra Colloq., accepted for publication,
preprint: arXiv:1601.03207.
[10] J. Provan and A. Billera, Decompositions of simplicail complexes related to the
diameters of convex polyhedra, Math. Oper. Res. 5(4), 576–594, 1980.
[11] R. S. Simon, Combinatorial properties of cleanness, J. Algebra 167, 361–388,
(1994).
[12] A. Soleyman Jahan and X. Zheng, Ideals with linear quotients, J. Combin. Theory
Ser. A 117, 104–110, 2010.
[13] R. Woodroofe, Chordal and sequentially Cohen-Macaulay clutters, Elec. J. Combin.
18(1), #P208, 2011.

16

