arXiv:1601.01456v1 [math.AC] 7 Jan 2016

MATCHINGS IN HYPERGRAPHS AND
CASTELNUOVO-MUMFORD REGULARITY
FAHIMEH KHOSH-AHANG∗ AND SOMAYEH MORADI
Abstract. In this paper, we introduce and generalize some combinatorial
invariants of graphs such as matching number and induced matching number to
hypergraphs. Then we compare them together and present some upper bounds
for the regularity of Stanley-Reisner ring of ∆H for certain hypergraphs H in
terms of the introduced matching numbers.

Introduction
There is a natural correspondence between simplicial complexes and hypergraphs
in the way that for a hypergraph H, the faces of the simplicial complex associated
to it are the independent sets of vertices of H, i.e. the sets which do not contain
any edge of H. This simplicial complex is called the independence complex
of H and is denoted by ∆H . Squarefree monomial ideals can be studied using
these combinatorial ideas. Recently, edge ideals of graphs, as the easiest class of
squarefree monomial ideals, has been studied by many researchers and some nice
characterizations of the algebraic invariants, in terms of data from graphs, have
been proved (cf. [9], [10], [11], [13], [16] and [19]). Extending the concepts in
graphs to hypergraphs and finding more general results in hypergraphs, which will
cover all squarefree monomial ideals, are of great interest and in some senses there
are generalizations, see for example [5], [7], [8], [14] and [17]. The matchings are
some graph invariants which are studied extensively (cf. [12]). In this paper we are
going to extend some of them to hypergraphs.
The Castelnuovo-Mumford regularity (or simply regularity) of an R-module
M is defined as
reg (M ) := max{j − i| βi,j (M ) 6= 0},
where βi,j (M ) is the (i, j)th Betti number of M . Explaining the CastelnuovoMumford regularity of R/I∆H in terms of invariants of H has been studied extensively by many authors, where I∆H is the Stanley-Reisner ideal of the independence
complex of the hypergraph H. In the case that H is a graph, in certain circumstances, reg(R/I∆H ) is characterized precisely. For instance, in [7], [11] and [16],
respectively for chordal graph, C5 -free vertex decomposable graph and sequentially
Cohen-Macaulay bipartite graph G, it was shown that reg (R/I(G)) = cG , where
I(G) is the edge ideal of G and cG is the induced matching number of G. Furthermore, combinatorial characterizations of the Castelnuovo-Mumford regularity
of the edge ideal of hypergraphs has been subject of many works. Indeed, in [8], the
2000 Mathematics Subject Classification. Primary 13D02, 13P10; Secondary 16E05.
Key words and phrases. edge ideal, hypergraph, matching number, regularity, vertex decomposable.
∗Corresponding author.
1

2

F. KHOSH-AHANG AND S. MORADI

authors introduced the concept of 2-collage in a simple hypergraph as a generalization of the matching number in graph and proved that the Castelnuovo-Mumford
regularity of the edge ideal of a simple hypergraph is bounded above in terms of
2-collages. Also, Morey and Villarreal, in [14], gave a lower bound for the regularity of the edge ideal of any simple hypergraph in terms of an induced matching of
the hypergraph. Moreover, in [7], for d-uniform properly-connected hypergraphs a
lower bound for the regularity is given. For more results see [3, 4, 6, 15, 18].
In this paper, we also study the regularity of the Stanley-Reisner ring of ∆H
for some families of hypergraphs and relate it to some combinatorial concepts and
generalize or improve some results, which had been gained for graphs, such as [7,
Theorem 6.7] and [11, Theorem 2.4].
The paper proceeds as follows. After reviewing some hypergraph terminologies
in the first section, in Section 2, we define an induced matching, a semi induced
matching and matching number for a hypergraph H, which we denote by cH , c′H
and mH , respectively and compare them together under different conditions. Also,
we present a class of hypergraphs H, consisting simple graphs, so that cH = c′H .
In the light of [14, Corollary 3.9(a)], cH is a lower bound for reg (R/I∆H ), when
H is a hypergraph. In Section 3, we are going to obtain some upper bounds for
reg (R/I∆H ) for a hypergraph H. As another class of hypergraphs, vertex decomposable hypergraphs has been studied and in Theorem 3.6, it is proved that if
a vertex decomposable hypergraph H is (C2 , C5 )-free, then reg (R/I∆H ) ≤ c′H ≤
dim ∆H + 1. This improves a result on graphs proved in [11], which states that for
a C5 -free vertex decomposable graph G, reg (R/I(G)) = cG .
1. Review of hypergraph terminology
In this section, we present some preliminaries in the context of hypergraphs from
[1] and [2].
Definition 1.1. A hypergraph is a pair (V, E, I), where V is a finite set of vertices,
and E = {Ei : i ∈ I, ∅ =
6 Ei ⊆ V } is a collection of edges (or hyperedges). We will
often abuse notation and refer to (V, E) as a hypergraph, with an understanding
that the edges are indexed by some set I. A hypergraph is called d-uniform if
all of its edges have the same cardinality d. So, every simple graph is a 2-uniform
hypergraph.
Throughout this paper, we assume that H = (V (H), E(H)) is a simple hypergraph. That means that no element of E(H) contains another. A vertex of H is
called isolated if it is not contained in any edge of H.
Definition 1.2. Assume that H is a hypergraph. For any vertex x ∈ V (H), H \ x
is a hypergraph with vertex set V (H) \ {x} and edge set {E ∈ E(H) : x ∈
/ E}.
Moreover H/x is a hypergraph with vertex set V (H) \ {x} whose edges are the nonempty minimal elements (with respect to inclusion) of the set {E\{x} : E ∈ E(H)}.
It is clear that H\x and H/x are two simple hypergraphs. They are called deletion
and contraction of H by x, respectively.
Note that for a vertex x ∈ V (H), del ∆H (x) = ∆H\x and lk ∆H (x) = ∆H/x .
Definition 1.3. Given a hypergraph H, there are some notions of induced subgraph. Although we need just two of them, but for completeness of the context we
bring all of them here. Given a subset A of vertices, a subhypergraph on A is

MATCHINGS IN HYPERGRAPHS AND CASTELNUOVO-MUMFORD REGULARITY

3

the hypergraph
HA = (A, {Ei ∩ A : Ei ∩ A 6= ∅}).
Note that the new index set for edges is {i ∈ I|Ei ∩ A 6= ∅}. A vertex section
hypergraph on A is the hypergraph
H × A = (A, {Ei : Ei ⊆ A}).
Given a subset J ⊆ I, let EJ = {Ej : j ∈ J}, we let HJ = (V, EJ ) denote the
partial hypergraph and the edge section S
hypergraph H × J is a hypergraph
which has the edge set EJ and the vertex set j∈J Ej .
Example 1.4. Let V = {1, 2, 3, 4}, and consider a hypergraph H with edges E1 =
{1, 2, 3} and E2 = {2, 4}. Then the subhypergraph of H induced by the vertex set
A = {2, 3, 4} has edges E1 ∩ A = {2, 3} and E2 = {2, 4}, while the vertex section
hypergraph H × A only has the edge E2 = {2, 4}.
Consider the hypergraph H′ on V with edges E1′ = {1, 2}, E2′ = {2, 3} and
′
E3 = {3, 4}. Then the partial hypergraph of H′ induced by E1′ , E2′ has the vertex
set V , while the edge section hypergraph of H′ induced by E1′ , E2′ has the vertex
set {1, 2, 3}.
Definition 1.5. A chain in H is a sequence v0 , E1 , v1 , . . . , Ek , vk , where vi ∈ Ei
for 1 ≤ i ≤ k, vi ∈ Ei+1 for 0 ≤ i ≤ k − 1, and E1 , . . . , Ek are edges H. For our
convenience, we denote this chain by E1 , . . . , Ek , if there is no ambiguity. If the
edges are all distinct, we obtain a path of length k. If k > 2 and v0 = vk , we call
the path a cycle of length k or a k-cycle and we denote it by Ck . We say that H
is Ck -free if it doesn’t contain any cycle Ck as an edge section hypergraph.
Definition 1.6. A d-uniform hypergraph H is called strongly connected if for
each distinct edges E and E ′ , there is a chain E = E0 , E1 , . . . , Ek−1 , Ek = E ′ of
edges of H such that for each i := 0, 1, . . . , k − 1, |Ei ∩ Ei+1 | = d − 1.
2. Matching numbers of hypergraphs
In this section, firstly, inspired by the definition of an induced matching in [14],
we introduce the concepts of induced matching number and semi induced matching
number of a hypergraph. Then we give some equalities and inequalities between
these invariants.
Definition 2.1. A set {E1 , . . . , Ek } of edges of a hypergraph H is called a semi
Sk
induced matching if the only edges contained in ℓ=1 Eℓ are E1 , . . . , Ek . A
semi induced matching which all of its elements are mutually disjoint is called an
induced matching. Also, we set
cH := max{|

k
[

Eℓ | − k : {E1 , . . . , Ek } is an induced matching in H},

ℓ=1

c′H := max{|

k
[

Eℓ | − k : {E1 , . . . , Ek } is a semi induced matching in H},

ℓ=1

and we call them induced matching number and semi induced matching
number of H, respectively.
The following theorem compares the invariants cH , c′H and dim(∆H ) for an
arbitrary hypergraph H.

4

F. KHOSH-AHANG AND S. MORADI

Theorem 2.2. For any hypergraph H, we have the following inequalities.
cH ≤ c′H ≤ dim(∆H ) + 1
Proof. It is clear that every induced matching of H is a semi induced matching.
So, we have cH ≤ c′H . To prove the last inequality, suppose that {E1 , . . . , Ek } is
Sk
a semi induced matching in H such that c′H = | ℓ=1 Eℓ | − k. Set S0 = ∅ and
for each 1 ≤ i ≤ k, if Ei ∩ Si−1 6= ∅, then set Si = Si−1 ; else, choose a vertex
Sk
xi ∈ Ei and set Si = Si−1 ∪ {xi }. Now, consider the set G = ( ℓ=1 Eℓ ) \ Sk .
We claim that G is an independent set of vertices in H. By contrary, assume that
S
E ⊆ G for some E ∈ E(H). Then E ∩ Sk = ∅ and E ⊆ kℓ=1 Eℓ . So E = Ei
for some 1 ≤ i ≤ k, since {E1 , . . . , Ek } is a semi induced matching in H. From
the choice of xi s, it is clear that xj ∈ Ei ∩ Sk for some 1 ≤ j ≤ i, which is a
contradiction. Therefore, G is contained in a facet F of ∆H . Since |Sk | ≤ k, we
have c′H ≤ |G| ≤ |F | ≤ dim(∆H ) + 1, which completes the proof.

The following example illustrates that the inequalities in Theorem 2.2 can be
strict.
Example 2.3. Let H be a hypergraph with vertex set V = {x1 , . . . , x6 } and edges
E1 = {x1 , x2 , x3 }, E2 = {x2 , x3 , x4 } and E3 = {x4 , x5 , x6 }. Then one can see that
cH = 2 and c′H = 3. So cH < c′H .
Assume that G is a star graph with vertex set V = {x1 , . . . , x4 } and edges
{x1 , x2 }, {x1 , x3 }, {x1 , x4 }. Then one can easily see that c′G = 1, but dim(∆G ) = 2.
So, even when H is a graph, the second inequality in Theorem 2.2 can be strict.
Remark 2.4. It is easily seen that when H is a graph, cH is the well-known induced
matching number of H; i.e. the maximum number of 3-disjoint edges in H. Also, it
can be easily seen that for a hypergraph H, a subset {E1 , . . . , Ek } of edges of H is
Sk
a semi induced matching if the edges of the vertex section hypergraph H × i=1 Ei
′
are exactly E1 , . . . , Ek . So cH can be defined as
max{|V (K)|−|E(K)| : K is a vertex section hypergraph of H with no isolated vertex}.
In the following proposition, we provide conditions under which cH = c′H .
Proposition 2.5. Assume that H is a d-uniform hypergraph such that for each
distinct edges E and E ′ , E ∩ E ′ 6= ∅ implies that |E ∩ E ′ | = d − 1. Then cH = c′H .
Proof. In view of Theorem 2.2, it is enough to show that c′H ≤ cH . To this end,
Sk
assume that {E1 , . . . , Ek } is a semi induced matching in H such that | ℓ=1 Eℓ | −
k = c′H . It is sufficient to show that there is a subset S of {1, . . . , k} such that
{Eℓ : ℓ ∈ S} is an induced matching in H and
|

k
[
ℓ=1

Eℓ | − k ≤ |

[

Eℓ | − |S|.

ℓ∈S

We use induction on k. The result is clear when k = 1. So assume inductively that
k > 1 and the result is true for smaller values of k. We may consider the following
cases.
Sk
Case I. Suppose that there is an integer 1 ≤ i ≤ k such that Ei ∩( ℓ=1,ℓ6=i Eℓ ) =
∅. Then by inductive hypothesis, there is a subset S of {1, . . . , i − 1, i + 1, . . . , k}

MATCHINGS IN HYPERGRAPHS AND CASTELNUOVO-MUMFORD REGULARITY

5

such that {Eℓ : ℓ ∈ S} is an induced matching in H and we have
k
[

|

Eℓ | − (k − 1) ≤ |

ℓ=1,ℓ6=i

[

Eℓ | − |S|.

ℓ∈S

Now, set S ′ = S ∪ {i}. It is obvious that {Eℓ : ℓ ∈ S ′ } is an induced matching in
H and we have
|

k
[

Eℓ | − k = |

ℓ=1

k
[

Eℓ | − (k − 1) + |Ei | − 1

ℓ=1,ℓ6=i

≤|

[

Eℓ | − |S| + |Ei | − 1

ℓ∈S

=|

[

Eℓ | − |S ′ |

ℓ∈S ′

as desired.
Case II. Suppose that there is an integer 1 ≤ i ≤ k such that 0 < |Ei ∩
Sk
( ℓ=1,ℓ6=i Eℓ )| < |Ei |. Then inductive hypothesis implies that there is a subset S of
{1, . . . , i − 1, i + 1, . . . , k} such that {Eℓ : ℓ ∈ S} is an induced matching in H and
k
[

|

Eℓ | − (k − 1) ≤ |

ℓ=1,ℓ6=i

[

Eℓ | − |S|.

ℓ∈S

Sk
On the other hand, by our assumption on H, we should have |Ei ∩ ( ℓ=1,ℓ6=i Eℓ )| =
d − 1. Now, we have
|

k
[

Eℓ | − k = |

ℓ=1

k
[

Eℓ | − (k − 1) + |Ei | − |Ei ∩ (

ℓ=1,ℓ6=i

≤|

[

k
[

Eℓ )| − 1

ℓ=1,ℓ6=i

Eℓ | − |S| + d − (d − 1) − 1

ℓ∈S

=|

[

Eℓ | − |S|

ℓ∈S

as desired.
S
Case III. Suppose that for each 1 ≤ i ≤ k, Ei ⊆ kℓ=1,ℓ6=i Eℓ . Then by inductive
hypothesis, there is a subset S of {1, . . . , k−1} such that {Eℓ : ℓ ∈ S} is an induced
matching in H and
k−1
[
[
|
Eℓ | − (k − 1) ≤ |
Eℓ | − |S|.
ℓ=1

ℓ∈S

So, we have
|

k
[

Eℓ | − k = |

ℓ=1

k−1
[

Eℓ | − (k − 1) − 1

ℓ=1

≤|

[

Eℓ | − |S| − 1

ℓ∈S

≤|

[

ℓ∈S

Eℓ | − |S|

6

F. KHOSH-AHANG AND S. MORADI

as desired.



Although by Remark 2.4, one may find out that for a graph G, cG = c′G , but
this is an immediate consequence of Proposition 2.5 as follows.
Corollary 2.6. For a simple graph G, we have cG = c′G .
The concept of matching number of a hypergraph is known as a generalization
of one in graph theory (see [1]). In fact, the maximum number of mutually disjoint
edges of a hypergraph is called the matching number. Hà and Van Tuyl in [7] showed
that when H is a graph, its matching number is an upper bound for reg(R/I∆H ).
Here, by benefitting their work, we improve the definition of matching number of a
hypergraph so that we can generalize this result to special class of hypergraphs (see
Remark 3.1). So, we present a new definition for matching number of a hypergraph
as follows.
Definition 2.7. (Compare [7, Definition 6.6].) A set of edges of a hypergraph H
is called a matching if they are pairwise disjoint. Also, we set
mH := max{|

k
[

Eℓ | − k : {E1 , . . . , Ek } is a matching in H},

ℓ=1

and we call it the matching number of H.
One can see that this definition is a natural generalization of one in graph theory,
i.e. when H is a graph, mH is the largest size of a maximal matching in H.
Furthermore, it is obvious that cH ≤ mH for any hypergraph H. Although, at one
look, no relation can be seen between c′H and mH , but Proposition 2.5 shows that
c′G ≤ mG , for special class of hypergraphs consisting simple graphs. Note that the
mentioned condition in Proposition 2.5 is different from the property of strongly
connected for hypergraphs.
3. Regularity of edge ideal of certain hypergraphs
In this section, we show that for a hypergraph H, the introduced invariants in
Section 2 give bounds for reg(R/I∆H ) and for some families of hypergraphs we give
the precise amount of reg(R/I∆H ) in terms of these numbers. We begin by the
following remark.
Remark 3.1. Morey and Villarreal in [14] showed that cH is a lower bound for
reg(R/I∆H ) for a simple hypergraph H. Hereafter, we are trying to find circumstances under which c′H or mH is an upper bound for reg(R/I∆H ). Note that in
the light of [7, Theorem 6.7], mH is an upper bound for reg(R/I∆H ), where H is a
simple graph. But we may have this result for more hypergraphs. In this regard,
recall that a subset C of the edges of a hypergraph H is called a 2-collage for H if
for each edge E of H we can delete a vertex v so that E \ {v} is contained in some
edge of C. Hence if H is a d-uniform hypergraph such that for each distinct edges
E and E ′ , E ∩ E ′ 6= ∅ implies that |E ∩ E ′ | = d − 1, one can easily see that any
maximal matching in H is a 2-collage. So, in view of [14, Corollary 3.9(a)] and [8,
Theorem 1.2], one can have
cH ≤ reg(R/I∆H ) ≤ mH .

MATCHINGS IN HYPERGRAPHS AND CASTELNUOVO-MUMFORD REGULARITY

7

As a main result of this paper, we are going to show that c′H is an upper bound
for reg(R/I∆H ) for a certain class of hypergraphs. To this end, we need to recall
the following definition.
Definition 3.2. Let ∆ be a simplicial complex on the vertex set V = {x1 , . . . , xn }.
Then ∆ is vertex decomposable if either:
1) The only facet of ∆ is {x1 , . . . , xn }, or ∆ = ∅.
2) There exists a vertex x ∈ V such that del ∆ (x) and lk ∆ (x) are vertex decomposable, and such that every facet of del ∆ (x) is a facet of ∆.
A vertex x ∈ V for which every facet of del ∆ (x) is a facet of ∆ is called a
shedding vertex of ∆. Note that this is equivalent to say that no facet of lk ∆ (x)
is a facet of del ∆ (x).
A hypergraph H is called vertex decomposable, if the independence complex
∆H is vertex decomposable and a vertex of H is called a shedding vertex if it is
a shedding vertex of ∆H . It is easily seen that if x is a shedding vertex of H and
{E1 , . . . , Ek } is the set of all edges of H containing x, then every facet of H \ x
contains Ei \ {x} for some 1 ≤ i ≤ k.
For our main result we also need to illustrate the relations between c′H , c′H\x and
c′H/x for a vertex x of H. Note that it is obvious that cH\x ≤ cH and c′H\x ≤ c′H .
Now, suppose that {E1 \ {x}, . . . , Ek \ {x}} is a semi induced matching in H/x
S
such that c′H/x = | kℓ=1 (Eℓ \ {x})| − k. The following example shows that it is not
necessarily true that {E1 , . . . , Ek } is a semi induced matching in H.
Example 3.3. Let H be a hypergraph with V (H) = {x1 , . . . , x5 } and E(H) =
{E1 = {x1 , x2 , x3 }, E2 = {x2 , x3 , x4 }, E3 = {x4 , x5 }}. Then E(H/x1 ) = {E1 \
{x1 }, E3 \ {x1 }}. It is clear that {E1 \ {x1 }, E3 \ {x1 }} is a semi induced matching
in H/x1 but {E1 , E3 } is not a semi induced matching in H.
Now, the following two lemmas provide conditions under which we can get to a
semi induced matching in H from one in H/x, for a vertex x of H.
Lemma 3.4. Assume that H is a C2 -free hypergraph, x is a vertex of H and k is the
smallest integer such that there exists a semi induced matching {E1 \ {x}, . . . , Ek \
Sk
{x}} in H/x so that c′H/x = | ℓ=1 (Eℓ \ {x})| − k. Then {E1 , . . . , Ek } is a semi
induced matching in H and so if x ∈ Ei for some 1 ≤ i ≤ k, we have c′H/x + 1 ≤ c′H .
Sk
Proof. Suppose that there is an edge E of H such that E ⊆ ℓ=1 Eℓ . Then E\{x} ⊆
Sk
ℓ=1 (Eℓ \ {x}). Now, we have three cases:
Case I. If x ∈ E, then E \ {x} = Ei \ {x}, for some 1 ≤ i ≤ k. If x 6∈ Ei , then
E strictly contains Ei which is a contradiction. So, x ∈ Ei and hence E = Ei as
desired.
Case II. If x 6∈ E and E is an edge of H/x, then E = Ei \ {x}, for some
1 ≤ i ≤ k. If x ∈ Ei , then Ei strictly contains E which is a contradiction. So,
x 6∈ Ei which implies that E = Ei as desired.
Case III. If x 6∈ E and E is not an edge of H/x, then there is an edge E ′
of H containing x such that E ′ \ {x} ⊂ E and E ′ \ {x} is an edge of H/x. So,
S
E∩E ′ = E ′ \{x}. Since H is C2 -free, |E ′ \{x}| = 1. Since E ′ \{x} ⊆ kℓ=1 (Eℓ \{x}),
then E ′ \{x} = Ei \{x} for some 1 ≤ i ≤ k. Thus |Ei \{x}| = 1. Moreover, Ei \{x} *
Sk
ℓ=1,ℓ6=i (Eℓ \ {x}), since otherwise Ei \ {x} ⊆ Ej \ {x} for some j 6= i, which is

8

F. KHOSH-AHANG AND S. MORADI

impossible. Therefore, {Eℓ \ {x}, 1 ≤ ℓ ≤ k, ℓ 6= i} is a semi inducing matching in
S
S
H/x and | kℓ=1,ℓ6=i (Eℓ \ {x})| − (k − 1) = | kℓ=1 (Eℓ \ {x})| − 1 − (k − 1) = c′H/x ,
which contradicts to our assumption on k. So this case can’t occur.
Hence, {E1 , . . . , Ek } is a semi induced matching in H. Now, if x ∈ Ei for some
1 ≤ i ≤ k, we have
c′H/x = |

k
[

(Eℓ \ {x})| − k = |

ℓ=1

k
[

Eℓ | − k − 1 ≤ c′H − 1,

ℓ=1

which completes the proof.



Lemma 3.5. Assume that H is a (C2 , C5 )-free hypergraph, x is a shedding vertex
of H and {E1 \ {x}, . . . , Ek \ {x}} is a semi induced matching in H/x such that
x 6∈ Eℓ for all 1 ≤ ℓ ≤ k. Then there is an edge F of H containing x such that
{E1 , . . . , Ek , F } is a semi induced matching in H. Moreover, c′H/x + 1 ≤ c′H .
Proof. Let {F1 , . . . , Fs } be the set of all edges containing x and suppose, in contrary,
that for each Fi , there is an edge Fi′ of H such that Fi′ 6∈ {E1 , . . . , Ek , Fi }, Fi′ ∩Fi 6= ∅
Sk
and Fi′ \ Fi ⊆ ℓ=1 Eℓ . Note that if Fi′ = Fj for some 1 ≤ j ≤ s, then Fj \ Fi ⊆
Sk
H is C2 -free, then Fi ∩ Fj = {x} and Fj \ Fi = Fj \ {x}. So
ℓ=1 Eℓ . Since
S
Fj \ {x} ⊆ kℓ=1 Eℓ . This is a contradiction, since Fj \ {x} ∈ E(H/x).
Also, note that for each distinct integers 1 ≤ i, j ≤ s, Fi′ 6= Fj′ . Because, if
we have Fi′ = Fj′ for some distinct integers 1 ≤ i, j ≤ s, then we should have
Sk
Fi′ \ (Fi ∩ Fj ) ⊆ ℓ=1 Eℓ . On the other hand, we know that x 6∈ Fi′ and since
S
H is C2 -free, Fi ∩ Fj = {x}. Hence, Fi′ ⊆ kℓ=1 Eℓ . So there exists an edge
S
k
E \ {x} ∈ E(H/x) such that E \ {x} ⊆ Fi′ ⊆ ℓ=1 Eℓ , which is a contradiction.
Moreover, note that for each distinct integers 1 ≤ i, j ≤ s, Fj ∩ Fj′ 6⊆ Fi′ \ Fi ,
Sk
because otherwise since Fi′ \ Fi and Fj′ \ Fj are contained in ℓ=1 Eℓ , we should
Sk
have Fj′ ⊆ ℓ=1 Eℓ , which is a contradiction. Hence, Eℓ ∩ Fi′ 6= Fj ∩ Fj′ for all
1 ≤ ℓ ≤ k.
Ss
Now, set S = i=1 (Fi′ \ Fi ). At first, we are going to show that S is an independent set of vertices in H/x. Suppose, in contrary, that S is not independent.
Sk
Then, since S ⊆ ℓ=1 Eℓ and {E1 , . . . , Ek } is a semi induced matching in H/x,
there should exist an Eℓ which intersects with two distinct edges Fi′ and Fj′ . So,
since H is C2 -free, Eℓ − Fi′ − Fi − Fj − Fj′ − Eℓ forms a subhypergraph C5 in H which
is a contradiction. Thus, S is an independent set of vertices in H/x. We extend S
to a facet G of ∆H/x . G is also a facet of ∆H\x ; because otherwise G is contained
in a facet K of ∆H\x . Now, since x is a shedding vertex, K contains Fi \ {x} for
some 1 ≤ i ≤ s. Hence, Fi′ ⊆ K, because Fi′ \ Fi ⊆ S ⊆ G ⊆ K and x 6∈ Fi′ . This
is a contradiction, since Fi′ ∈ E(H \ x). So we found a facet of ∆H/x , which is a
facet of ∆H\x . But this contradicts to the fact that x is a shedding vertex. So,
we proved that {E1 , . . . , Ek , Fi } is a semi induced matching in H, for some edge
Sk
Sk
Fi containing x. Now, let c′H/x = | ℓ=1 (Eℓ \ {x})| − k. Since Fi \ {x} * ℓ=1 Eℓ ,
Sk

c′H/x + 1 ≤ |( ℓ=1 Eℓ ) ∪ Fi | − (k + 1) ≤ c′H as required.
Now, we are ready to state our main result of this section.
Theorem 3.6. Let H be a (C2 , C5 )-free vertex decomposable hypergraph.Then
reg(R/I∆H ) ≤ c′H ≤ dim(∆H ) + 1.

MATCHINGS IN HYPERGRAPHS AND CASTELNUOVO-MUMFORD REGULARITY

9

Proof. In the light of Theorem 2.2 it is enough to prove reg(R/I∆H ) ≤ c′H . In this
regard, we use induction on |V (H)|. If |V (H)| = 2, the result is clear. Suppose,
inductively, that the result has been proved for smaller values of |V (H)|. Assume
that x is a shedding vertex of H. Let ∆ = ∆H , ∆1 = ∆H\x and ∆2 = ∆H/x . Then
H \ x and H/x are (C2 , C5 )-free vertex decomposable hypergraphs and no facet of
∆2 is a facet of ∆1 . By inductive hypothesis we have
reg(R/I∆1 ) ≤ c′H\x and reg(R/I∆2 ) ≤ c′H/x .
On the other hand, we have the inequality
reg(R/I∆ ) ≤ max{reg(R/I∆1 ), reg(R/I∆2 ) + 1}.
Hence
reg(R/I∆ ) ≤ max{c′H\x , c′H/x + 1}.
Now, the result immediately follows from Lemmas 3.4 and 3.5.



Example 3.7. Assume that d ≥ 3 and H is a d-uniform simple hypergraph with
vertex set
k d−1
[
[
{xi,j } ∪ {x},
V (H) =
i=1 j=1

and edge set
E(H) = {Ei = {xi,1 , . . . , xi,d−1 , x} : 1 ≤ i ≤ k}.
one may find out that the only 2-collage of H is {E1 , . . . , Ek }. So, in the light of
[8, Theorem 1.2], we have
reg(R/I∆H ) ≤ k(d − 1).
On the other hand, One can easily check that H is a (C2 , C5 )-free vertex decomposable hypergraph and {E1 , . . . , Ek } is the semi induced matching of H such that
Sk
c′H = | i=1 Ei | − k. Hence, by Theorem 3.6, we have
reg(R/I∆H ) ≤ k(d − 1) + 1 − k.
The above example illustrates that for d ≥ 3 and large enough values of k, the
upper bound on reg(R/I∆H ) presented in [8, Theorem 1.2] in this special case is
much larger than the actual value of reg(R/I∆H ), and our upper bound in Theorem
3.6 is better than one given in [8, Theorem 1.2]. Of course note that the proof of
Lemma 3.4 in [8] has some flaws, and so the proof of Theorem 1.2 in [8] will be
uncertain. The following example shows this defect.
Example 3.8. Assume that H is a hypergraph with vertex set V = {a, b, c, d, e, f }
and edge set {{a, b}, {a, c}, {d, f }, {e, f }, {b, c, d, e}}. With the notations in [8],
for each edge E of H, let HE be the hypergraph whose edge set consists of the
minimal (under inclusions) members of {E ∪ E ′ : E ′ 6= E is an edge of H}. So,
by considering E = {a, b}, the edge set of HE is {{a, b, c}, {a, b, d, f }, {a, b, e, f }}.
Now, one can easily see that {E0 = {b, c, d, e}} is a 2-collage for H but {E ∪ E0 } is
not even an edge of HE and it doesn’t contain any 2-collage of HE . Also, for each
choice of E 6= E0 , the above assertion holds. This shows the mentioned defect of
the proof of [8, Lemma 3.4].

10

F. KHOSH-AHANG AND S. MORADI

Since cH = c′H , in conjunction with Theorem 3.6 and [14, Corollary 3.9(a)],
can characterize the regularity of the Stanley-Reisner ring R/I∆H precisely, this
question arises that when the equality cH = c′H holds? In the light of Remark 3.1,
the similar question can be asked about the equality cH = mH . With this point of
view, [14, Corollary 3.9(a)], Proposition 2.5, Remark 3.1 and Theorems 2.2 and 3.6
imply the next corollary.
Corollary 3.9. (Compare [11, Theorem 1.9].)
(i) Assume that H is a (C2 , C5 )-free vertex decomposable hypergraph such that
cH = dim(∆H ) + 1. Then
reg(R/I∆H ) = cH = c′H = dim(∆H ) + 1.
(ii) If H is a (C2 , C5 )-free vertex decomposable hypergraph such that cH = c′H ,
then
reg(R/I∆H ) = cH .
(iii) In particular, if G is a simple C5 -free vertex decomposable graph, then
reg(R/I∆G ) = cG .
(iv) Assume that H is a d-uniform hypergraph such that cH = mH and for each
distinct edges E and E ′ , E ∩ E ′ 6= ∅ implies that |E ∩ E ′ | = d − 1. Then
reg(R/I∆H ) = cH = c′H = mH .
References
1. C. Berge, Hypergraphs. Combinatorics of finite sets. Translated from the French. NorthHolland Mathematical Library, 45. North-Holland Publishing Co., Amsterdam, 1989.
2. C. Berge, Graphs and hypergraphs. Translated from the French by Edward Minieka. NorthHolland Mathematical Library, Vol. 6. North-Holland Publishing Co., Amsterdam-London;
American Elsevier Publishing Co., Inc., New York, 1973. xiv+528 pp.
3. D. Cook II, The uniform face ideals of a simplicial complex, arXiv:1308.1299.
4. H. Dao; C. Huneke; J. Schweig, Bounds on the regularity and projective dimension of ideals
associated to graphs, J. Algebraic Combin. 38 (2013), no. 1, 37–55.
5. E. Emtander, A class of hypergraphs that generalizes chordal graphs, Math. Scand. 106
(2010), no. 1, 50–66.
6. C. A. Francisco; H. T. Hà; and A. Tuyl, Splittings of monomial ideals, Proc. Amer. Math.
Soc. 137 (2009), no. 10, 3271–3282.
7. H. T. Hà; A. Van Tuyl, Monomial ideals, edge ideals of hypergraphs, and their graded Betti
numbers, J. Algebraic Combin. 27 (2008), no. 2, 215–245.
8. H. T. Hà; R. Woodroofe, Results on the regularity of square-free monomial ideals, Adv. in
Appl. Math. 58 (2014), 21–36.
9. J. Herzog; T. Hibi; X. Zheng, Dirac’s theorem on chordal graphs and Alexander duality,
European J. Combin. 25 (2004), no. 7, 949–960.
10. K. Kimura, Non-vanishingness of Betti numbers of edge ideals, Harmony of Grbner bases
and the modern industrial society, 153–168, World Sci. Publ., Hackensack, NJ, 2012.
11. F. Khosh-Ahang; S. Moradi, Regularity and projective dimension of edge ideal of C5 -free
vertex decomposable graphs, Proc. Amer. Math. Soc. 142 (2014), no. 5, 1567–1576.
12. L. Lovàsz; M. D. Plummer, Matching theory. North-Holland Mathematics Studies, 121.
Annals of Discrete Mathematics, 29. North-Holland Publishing Co., Amsterdam; Akadèmiai
Kiadò (Publishing House of the Hungarian Academy of Sciences), Budapest, 1986.
13. S. Moradi; D. Kiani, Bounds for the regularity of edge ideal of vertex decomposable and
shellable graphs, Bull. Iranian Math. Soc. 36 (2010), no. 2, 267–277.
14. S. Morey; R. H. Villarreal, Edge ideals: algebraic and combinatorial properties, 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.

MATCHINGS IN HYPERGRAPHS AND CASTELNUOVO-MUMFORD REGULARITY

11

15. E. Nevo, Regularity of edge ideals of C4 -free graphs via the topology of the lcm-lattice, J.
Combin. Theory Ser. A 118 (2011), no. 2, 491–501.
16. A. Van Tuyl, Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and
regularity, Arch. Math. (Basel) 93 (2009), no. 5, 451–459.
17. R. Woodroofe, Chordal and sequentially Cohen-Macaulay clutters, Electron. J. Combin. 18
(2011), no. 1, Paper 208, 20 pp.
18. R. Woodroofe, Matchings, coverings, and Castelnuovo-Mumford regularity, J. Commut.
Algebra 6 (2014), no. 2, 287–304.
19. X. Zheng, Resolutions of facet ideals, Comm. Algebra 32 (2004), no. 6, 2301–2324.
Fahimeh Khosh-Ahang, Department of Mathematics, Ilam University, P.O.Box 69315516, Ilam, Iran.
E-mail address: fahime− khosh@yahoo.com
Somayeh Moradi, Department of Mathematics, Ilam University, P.O.Box 69315-516,
Ilam, Iran and School of Mathematics, Institute for Research in Fundamental Sciences
(IPM), P.O.Box: 19395-5746, Tehran, Iran.
E-mail address: somayeh.moradi1@gmail.com

