arXiv:1705.06426v1 [] 18 May 2017

REGULARITY OF POWERS OF COVER IDEALS OF
UNIMODULAR HYPERGRAPHS
NGUYEN THU HANG AND TRAN NAM TRUNG
Dedicated to Professor Le Tuan Hoa on his 60th birthday
Abstract. Let H be a unimodular hypergraph over the vertex set [n] and let J(H)
be the cover ideal of H in the polynomial ring R
 =
 K[x1 , . . . , xn ]. We show that
reg J(H)s is a linear function in s for all s > r n2 + 1 where r is the rank of H.
Moreover for every i, ai (R/J(H)s ) is also a linear function in s for s > n2 .

Introduction
Let R := K[x1 , . . . , xn ] be a polynomial ring over a field K and m := (x1 , . . . , xn )
the maximal homogeneous ideal of R. Let M be a finitely generated graded R-module.
For each i = 0, . . . , dim M we define the ai -invariant of M by
ai (M) := max{t | Hmi (M)t 6= 0},

where Hmi (M) is the i-th local cohomology module of M with support in m (with the
convention max ∅ = −∞); and the Castelnuovo-Mumford regularity (or regularity for
short) of M is defined by
reg(M) := max{ai (M) + i | i = 0, . . . , dim M}.

Let I be a homogeneous ideal in R. It is well-known that reg I s is a linear function
in s for s big enough (see [9, 20, 26]). More precisely, there are non-negative integers
d, e and s0 such that
reg I s = ds + e for all s > s0 .
While d can be determined in terms of generators of I (see [20]), there are no good
interpretations for e and s0 . Two natural questions arise from this result (see [11]):
(1) What is the nature of the number e?
(2) What is a reasonable bound for s0 ?
These problems are continue to attract us (see [1, 2, 4, 5, 6, 10, 11, 12, 13, 19, 23]).
When I is generated by forms of the same degree, there is a geometric interpretation
for e (see [6, 10, 12]). Effective bounds of s0 are known only for a few special classes of
ideals I, such as edge ideals of forests and unicyclic graphs (see [1, 5, 19]), m-primary
ideals (see [4, 7]).
1991 Mathematics Subject Classification. 13A15, 13C13.
Key words and phrases. Regularity, cover ideals, powers of ideals.
1

Notice that
reg I s = 1 + reg R/I s = 1 + max{ai (R/I s ) + i | i = 0, . . . , dim R/I},
it is also natural to ask whether ai (R/I s ) is asymptotically linear in s or not. However,
reg Ies
there is an example such that lims→∞
is an irrational number (see [8]), so that
s
s
ai (R/I ) need not to be linear when s large. If we assume furthermore that I is a
monomial ideal then ai (R/I s ) is a quasi-linear function in s due to [17], but we still
do not know whether ai (R/I s ) is asymptotically linear in s or not.
In this paper when I is the cover ideal of a unimodular hypergraph, we will prove
that ai (R/I s ) is actually asymptotically linear in s. Using this result we are able to
give a reasonable bound of s0 for which reg I s is a linear function in s for all s > s0 .
Before stating our result we recall some terminology from graph theory (see [3] for
more detail). Let V = [n] := {1, . . . , n}, and let E be a family of distinct nonempty
subsets of V. The pair H = (V, E) is called a hypergraph with vertex set V and edge
set E. The rank of H, denoted by rank(H), is the maximum cardinality of any of the
edges in H. Notice that a hypergraph generalizes the classical notion of a graph; a
graph is a hypergraph of rank at most 2. One may also define a hypergraph by its
incidence matrix A(H) = (aij ), with columns representing the edges E1 , E2 , . . . , Em
and rows representing the vertices 1, 2, . . . , n where aij = 0 if i ∈
/ Ej and aij = 1
if i ∈ Ej . A hypergraph H is said to be unimodular if its incident matrix is totally
unimodular, i.e., every square submatrix of A(H) has determinant equal to 0, 1 or −1.
A vertex cover of H is a subset of V which meets every edge of H; a vertex cover is
minimal if none of its proper subsets is itself a cover. For a subset τ = {i1 , . . . , it } of
V, set xτ := xi1 · · · xit . The cover ideal of H is then defined by
J(H) := (xτ | τ is a minimal vertex cover of H).
It is well-known that there is one-to-one correspondence between squarefree monomial ideals of R and cover ideals of hypergraphs on the vertex set V.
The first main result of this paper is the following theorem.
Theorem 3.2 For any i, we have either ai (R/J(H)s ) = −∞ for all s > 1 or there are
positive integers d and e with d 6 e such that ai (R/J(H)s ) = ds − e for all s > n2 .
We next address the question of bounding s0 for which reg I s is a linear function
in s whenever s > s0 . Let d(J(H)) be the maximal degree of minimal monomial
generators of J(H). Then, the main result of the paper is the following theorem.
Theorem 3.3 Let H be a unimodular hypergraph with n vertices and rank r. Then
s
there is a non-negative integer
 n  e 6 dim R/J(H) − d(J(H)) + 1 such that reg J(H) =
d(J(H))s + e for all s > r 2 + 1.

When H is a bipartite graph G with n vertices, it is unimodular by [3, Theorem 5].
The theorem 3.3 now says that reg(J(G)s ) is a linear function in s for all s > n + 2.
2

Our approach is based on a generalized Hochster’s formula for computing local cohomology modules of arbitrary monomial ideals formulated by Takayama [25]. Using
this formula we are able to investigate the ai -invariants of powers of monomial ideals
via the integer solutions of certain systems of linear inequalities. This allows us to use
the theory of integer programming as the key role in this paper (see e.g. [14, 16, 17]
for this approach).
The paper is organized as follows. In Section 1, we set up some basic notation and
terminology for simplicial complex, the relationship between simplicial complexes and
cover ideals of hypergraphs; and give a generalization of Hochster’s formula for computing local cohomology modules. In Section 2, we investigate the integer solutions of
systems of linear inequalities with totally unimodular matrices. In Section 3, we prove
that ai (R/J(H)s ) is an asymptotically linear function in s, and settle the problems
when reg J(H)s becomes a linear function in s, where H is a unimodular hypergraph.
1. Preliminary
Let K be a field and let R := K[x1 , · · · , xn ] be a polynomial ring over n variables.
We first recall a relationship between cover ideals of hypergraphs and simplicial complexes. A simplicial complex on V = {1, . . . , n} is a collection of subsets of V such
that if σ ∈ ∆ and τ ⊆ σ then τ ∈ ∆.
Definition 1.1. The Stanley-Reisner ideal associated to a simplicial complex ∆ is
the squarefree monomial ideal
I∆ := (xτ | τ ∈
/ ∆) ⊆ R.
Note that if I is a squarefree monomial ideal, then it is a Stanley-Reisner ideal of
the simplicial complex ∆(I) := {τ ⊆ V | xτ ∈
/ I}. If I is a monomial ideal (maybe
not squarefree) we also use ∆(I)
√ to denote the simplicial complex corresponding to
the squarefree monomial ideal I.
Let F (∆) be the set of facets of ∆. If F (∆) = {F1 , . . . , Fm }, we write ∆ =
hF1 , . . . , Fm i. Then, I∆ has the primary-decomposition (see [22, Theorem 1.7]):
\
I∆ =
(xi | i ∈
/ F ).
F ∈F (∆)

For n > 1, the n-th symbolic power of I∆ is
\
(n)
I∆ =
(xi | i ∈
/ F )n .
F ∈F (∆)

Let H = (V, E) be a hypergraph. Then, the cover ideal of H can be written as
\
(1)
J(H) =
(xi | i ∈ E).
E∈E

3

By this formula, when considering J(H) without loss of generality we may assume
that H is simple , i.e., whenever Ei , Ej ∈ E and Ei ⊆ Ej , then Ei = Ej . In this case,
J(H) is a Stanley-Reisner ideal with
∆(J(H)) = hV \ E | E ∈ Ei .

(2)

Let I be a non-zero monomial ideal. Since R/I is an Nn − graded algebra, Hmi (R/I)
is an Zn -graded module over R/I for every i. For each degree α = (α1 , . . . , αn ) ∈
Zn , in order to compute dimK Hmi (R/I)α we use a formula given by Takayama [25,
Theorem 2.2] which is a generalization of Hochster’s formula for the case I is squarefree
[18, Theorem 4.1].
Set Gα := {i | αi < 0}. For a subset F ⊆ V, we let RF := R[x−1
| i ∈ F ∪ Gα ].
i
Define the simplicial complex ∆α (I) by
∆α (I) := {F ⊆ V \ Gα | xα ∈
/ IRF }.

(3)

e i−|Gα|−1 (∆α (I); K).
Lemma 1.2. [25, Theorem 2.2] dimK Hmi (R/I)α = dimK H

If H is unimodular, the cover ideal J(H) is normally torsion-free, i.e. J(H)(s) =
J(H)s for all s > 1 by [15, Theorem 1.1]. Combining with [21, Lemma 1.3] we obtain:
Lemma 1.3. Let H = (V, E) be a unimodular hypergraph with V = {1, . . . , n}, and
α = (α1 , . . . , αn ) ∈ Nn . Then, for every s > 1 we have
*
+
X
∆α (J(H)s ) = V \ E | E ∈ E and
αi 6 s − 1 .
i∈E

2. Integer polytopes
For a vector α = (α1 , . . . , αn ) ∈ Rn , we set |α| := α1 + · · · + αn and for a nonempty
bounded closed subset S of Rn we set
δ(S) := max{|α| | α ∈ S}.

Let H = (V, E) be a unimodular hypergraph on the vertex set V = {1, . . . , n}.
Assume that
Hmp (R/J(H)q )β 6= 0
for some p > 0, q > 1 and β = (β1 , . . . , βn ) ∈ Nn .
By Lemma 1.2 we have
e p−1 (∆β (J(H)q ); K) = dimK H p (R/J(H)q )β 6= 0.
(4)
dimK H
m

q

In particular, ∆β (J(H) ) is not acyclic.
Suppose that E = {E1 , . . . , Em } where m > 1. Then, by Equation (2)
∆(J(H)) = hV \ E1 , . . . , V \ Em i .

Since ∆β (J(H)q ) is not acyclic, by Lemma 1.3 we may assume that
where 1 6 k 6 m.

∆β (J(H)q ) = hV \ E1 , . . . , V \ Ek i
4

For each integer t > 1, let Pt be the set of solutions in Rn of the following system:
P

for j = 1, . . . , k,
Pi∈Ej xi 6 t − 1
(5)
for j = k + 1, . . . , m,
i∈Ej xi > t


x1 > 0, . . . , xn > 0.
Then, β ∈ Pq . Moreover, by Lemma 1.3 one has

∆α (J(H)t ) = hV \ E1 , . . . , V \ Ek i = ∆β (J(H)q ) whenever α ∈ Pt ∩ Nn .

In order to investigate the set Pt we consider Ct to be the set of solutions in Rn of
the following system:
P

for j = 1, . . . , k,
Pi∈Ej xi 6 t
(6)
for j = k + 1, . . . , m,
i∈Ej xi > t


x1 > 0, . . . , xn > 0.
Since H is unimodular, we have both Pt and Ct are integer convex polyhedra by
[24, Theorem 19.1], i.e. all their vertices have integer coordinates.
Lemma 2.1. [14, Lemma 2.1] C1 is a polytope with dim C1 = n.
Remark 2.2. Since Ct = tC1 is also a polytope, it is bounded. Thus, for every
i = 1, . . . , n, from the system (6) we imply that i ∈ Ej for some 1 6 j 6 k.
Observe that Pt ⊆ Ct , so Pt is a polytope as well.
Lemma 2.3. Pn 6= ∅.
Proof. From the system (5), Pn is the set of solutions of the following system:
P

for j = 1, . . . , k,
Pi∈Ej xi 6 n − 1
(7)
for j = k + 1, . . . , m,
i∈Ej xi > n


x1 > 0, . . . , xn > 0.

If k = m, then the zero vector of Rn is in Pn , and then Pn 6= ∅. P
Assume that k < m. From the system (6) we conclude that i∈Em xi = 1 is a
supporting hyperplane of C1 . Let F be the facet of C1 determined by this hyperplane.
Now take n vertices of C1 lying in F , say α1 , . . . , αn , such that they are affinely
independent. Let α := (α1 + · · · + αn )/n ∈ C1 . Then, α is a relative interior point of
F , so that it does not belong to any another facet of C1 . Thus, α is a solution of the
following system:
P

for j = 1, . . . , k,
Pi∈Ej xi < 1
(8)
x >1
for j = k + 1, . . . , m,
 i∈Ej i

x1 > 0, . . . , xn > 0.
5

Therefore, nα is a solution of the following system
P

for j = 1, . . . , k,
Pi∈Ej xi < n
(9)
for j = k + 1, . . . , m,
i∈Ej xi > n


x1 > 0, . . . , xn > 0.

Together with the fact that nα ∈ Nn , it yields nα ∈ Pn , and thus Pn 6= ∅.



Since C1 is a polytope, there is a vertex γ = (γ1 , . . . , γn ) of C1 such that
δ(C1 ) = |γ| = γ1 + · · · + γn .
Let d := |γ|. Note that tγ is also a vertex of Ct and δ(Ct ) = dt. Since Pt ⊆ Ct , we
have δ(Pt ) 6 dt, so we can write
δ(Pt ) = dt − et for some integer et > 0.
Remark 2.4. Since C1 is a polytope of dimension n, we have d > 1.
Lemma 2.5. If Pt 6= ∅, then Pt+1 6= ∅ and et > et+1 .
Proof. Let α = (α1 , . . . , αn ) ∈ Pt such that δ(Pt ) = |α|. Since α is a solution of the
system (5), and γ is a solution of the system (6) with 1 in place of t, we deduce that
(P
(αi + γi ) 6 t
for j = 1, . . . , k,
Pi∈Ej
for j = k + 1, . . . , m.
i∈Ej (αi + γi ) > t + 1

In other words, α + γ ∈ Pt+1 . Therefore, Pt+1 6= ∅ and δ(Pt+1 ) > |α| + |γ|. Since
δ(Pt+1 ) = d(t + 1) − et+1 and |α| + |γ| = d(t + 1) − et , we have et > et+1 .

For a real number x we denote by ⌈x⌉ the least integer > x. The following lemma
plays a key role in the paper. It says that δ(Pt ) is a linear function in t for t big
enough.
Lemma 2.6. There are non-negative integers d and e with e 6 n2 such that
lnm
+1
δ(Pt ) = dt − e for t > r
2

where r = rank(H).

Proof. By Lemmas 2.3 and 2.5 we have en > en+1 > · · · > 0. It follows that there is
t0 > n such that et = et0 for t > t0 . Let e := et0 . Then,
δ(Pt ) = dt − e, for all t > t0 .
By Lemma 2.5 we have
(10)

δ(Pt ) 6 dt − e whenever Pt 6= ∅.
6

Let s be an integer such that s > max{n2 +e+1, t0}. Then, δ(Ps ) = ds−e. Because
Ps is a polytope, we have δ(Ps ) = |α| for some vertex α of Ps . By the system (5),
the polytope Ps is defined by

(11)

P

Pi∈Ej xi 6 s − 1
i∈Ej xi > s


x1 > 0, . . . , xn > 0.

for j = 1, . . . , k,
for j = k + 1, . . . , m,

By [24, Formula 23 in Page 104] we can represent α as the unique solution of a system
of linear equations of the form

(12)

P

Pi∈Ej xi = s − 1
i∈Ej xi = s


xj = 0,

for j ∈ S1 ,
for j ∈ S2 ,
for j ∈ S3 ,

where S1 ⊆ [k], S2 ⊆ {k + 1, . . . , m} and S3 ⊆ [n] such that |S1 | + |S2 | + |S3 | = n.
Let A be the matrix of the system (12) and write α = (α1 , . . . , αn ). For each i,
let Ai be the matrix obtained from A by replacing the i-th column by: the first |S1 |
entries are s − 1, the next |S2 | consecutive entries are s, and the last |S3 | entries are
zeroes. Then, by Cramer’s rule we have
αi =

det(Ai )
for i = 1, . . . , n.
det(A)

Since H is unimodular, A is totally unimodular, and so det(A) = ±1. Without loss
of generality, we may assume that det(A) = 1. Thus, αi = det(Ai ), for i = 1, . . . , n.
Write the matrix Ai in the form

∗
 ..
.

∗

∗
.
Ai = 
 ..
∗

∗

 ..
.
∗

∗ ··· s−1 ···
..
..
.
···
. ···
∗ ··· s−1 ···
∗ ···
s
···
..
..
. ···
.
···
∗ ···
s
···
∗ ···
0
···
..
..
. ···
.
···
∗ ···
0
···
7


∗
.. 
.

∗

∗
.. 
.
,
∗

∗

.. 
.
∗

and let

(13)


∗
 ..
.

∗

∗
.
Di = 
 ..
∗

∗

 ..
.
∗

∗ ···
..
. ···
∗ ···
∗ ···
..
. ···
∗ ···
∗ ···
..
. ···
∗ ···

1 ···
..
. ···
1 ···
1 ···
..
. ···
1 ···
0 ···
..
. ···
0 ···



∗ ∗
∗
 .. ..
.. 
. .
.


∗ ∗

∗


∗ ∗
∗
. .
.. 

.
 and Ci =  .. ..
∗ ∗

∗

∗ ∗
∗


 .. ..

..
. .
.
∗ ∗
∗

··· 1 ···
.
· · · .. · · ·
··· 1 ···
··· 0 ···
.
· · · .. · · ·
··· 0 ···
··· 0 ···
.
· · · .. · · ·
··· 0 ···


∗
.. 
.

∗

∗
.. 
.
.
∗

∗

.. 
.
∗

Then, det(Ai ) = det(Di )s − det(Ci ). Let di := det(Di ) and ci := det(Ci ) so that
αi = di s − ci , for i = 1, . . . , n.

When deleting the i-th column from Ci we get a totally unimodular matrix. Therefore, by expanding the determinant of Ci along the i-th column we obtain
|ci | 6 |S1 | , for i = 1, . . . , n.

(14)

Let d′ := d1 + · · · + dn and c′ := c1 + · · · + cn . Then, we have |α| = d′ s − c′
and |c′ | 6 n|S1 | 6 n2 . Since δ(Ps ) = ds − e, we have ds − e = d′ s − c′ . Thus,
(d − d′ )s = e − c′ . Note that |e − c′ | 6 e + n2 < s. It follows that d − d′ = 0 and
e − c′ = 0, i.e. d = d′ and e = c′ . In particular, e 6 n2 .
As α = (d1 s − c1 , . . . , dn s − cn ) ∈ Nn and |ci | 6 |S1 | 6 n < s, for every i we have

(15)

di > 0, and di > 1 if ci > 0.

Since α ∈ Ps , from the system (11) we have


X
X

di  s −
ci 6 s − 1 for j = 1, . . . , k.

Together with
(16)

P

i∈Ej

i∈Ej

i∈Ej

|ci | 6 |Ej |n 6 rn for every j and s > rn + 1, it follows that
(
P
X
0 if
i∈Ej ci 6 0,
di =
1 otherwise.
i∈E
j

for j = 1, . . . , k.
Similarly, we also have
X
X
X
(17)
di > 1, and
di > 2 if
ci > 0
i∈Ej

i∈Ej

i∈Ej

for j = k + 1, . . . , m.
We first claim that
(18)

di 6 1 for every i = 1, . . . , n.
8

Indeed, by Remark 2.2, we have i ∈ Ej for some j ∈ [k] , and hence by (16) we have
X
(19)
di 6
du 6 1.
u∈Ej

We next claim that
|ci | 6

(20)

lnm
2

for every i = 1, . . . , n.

 
Indeed, if |S1 | 6 n2 , then the claim follows
 n  from (14). We now verify the claim
n
for the case |S1 | > 2 , so that |S2 | < 2 . Let Ei be the maxtrix obtained by
replacing the i-th column of Ai by the first |S1 | entries are zeroes, the next |S2 |
consecutive entries are 1, and the last |S3 | entries are zeroes. Then, by expanding |Ei |
along the i-th column we get |det(Ei )| 6 |S2 |. On the other hand, by (13) we have
det(Di ) = det(Ci ) + det(Ei ). Thus, |ci | 6 |di | +|det(E
 i )| 6 |di | + |S2 |. Together with
n
Claims (15) and (19) it yields |ci | 6 1 + |S2 | 6 2 , as claimed.
 
We now turn to prove the lemma by showing that δ(Pt ) = dt−e for all t > r n2 +1.
Indeed, let t be such an integer, and define
α(t) := (d1 t − c1 , . . . , dn t − cn ) ∈ Zn .
 
We prove that α(t) satisfies the system (5). Firstly, since n2 < t, by (15) and (20)
we have α(t)i > 0 for i = 1, . . . , n.
Next, P
for j = 1, . . . , k, by (16) we have two possible cases:
Case 1: i∈Ej di = 0. Together with (20) we obtain


lnm
X
X
X
X
6 t − 1.
α(t)i = 
di  t −
ci = −
ci 6 r
2
i∈E
i∈E
i∈E
i∈E
j

Case 2:

P

i∈Ej

j

di = 1 and

j

j

P

ci > 1. Then,

X
X
X
X
α(t)i = 
di  t −
ci = t −
ci 6 t − 1.
i∈Ej



i∈Ej

i∈Ej

i∈Ej

i∈Ej

P

In both cases we have i∈Ej α(t)i 6 t − 1.
Further,
. , m, by (17) we also have two possible cases:
P for j = k + 1, . .P
Case 1: i∈Ej di = 1 and i∈Ej ci 6 0. In this case,


X
X
X
X
α(t)i = 
di  t −
ci = t −
ci > t.
i∈Ej

i∈Ej

i∈Ej

i∈Ej

P
Case 2:
i∈Ej di > 2. Let ρ := |{i ∈ Ej | di = 1}|. By (15) and Claim (19) we have
P
ρ = i∈Ej di > 2. Note that if di = 0 then ci 6 0 since α ∈ Nn . Together with Claim
9

(20), it gives
X

i∈Ej



α(t)i = 

X

i∈Ej

> ρt −



di  t −
X

i∈Ej :di =1

X

i∈Ej

ci = ρt −

ci > ρt − ρ

X

i∈Ej :di =1

lnm
2

ci −

X

ci

i∈Ej :di =0

.

On the other hand r = rank H > |Ej | > ρ, so that
 lnm

 lnm

lnm
(ρ − 1)t > (ρ − 1) r
+ 1 > (ρ − 1) ρ
+1 >ρ
.
2
2
2
It follows that
lnm
lnm
X
= t + (ρ − 1)t − ρ
> t.
α(t)i > ρt − ρ
2
2
i∈Ej
P
Hence, i∈Ej α(t)i > t in both cases. Thus, α(t) is a solution of the system (5),
and thus α(t) ∈ Pt . In particular,
δ(Pt ) > |α(t)| = (d1 + · · · + dn )t − (c1 + · · · + cn ) = d′ t − c′ = dt − e.

Together with (10) we conclude that δ(Pt ) = dt − e, and the lemma follows.



Lemma 2.7. Assume that δ(Pt ) = dt − e for all t ≫ 0. Then, d 6 e.
Proof. Observe that δ(Pt ) is the optimal value of the linear programming problem
subject to

max(x1 + · · · + xn )

P

for j = 1, . . . , k,
Pi∈Ej xi 6 t − 1
for j = k + 1, . . . , m,
i∈Ej −xi 6 −t


x1 > 0, . . . , xn > 0.
Let A be the matrix of the first k inequalities of this system and B the matrix of
the next q := m − k inequalities. Then, the dual problem is
subject to
(21)

min((y1 + · · · + yk − z1 − · · · − zq )t − (y1 + · · · + yk ))
(
(y1 , . . . , yk )A + (z1 , . . . , zq )B > 1Tn ,
y1 > 0, . . . , yk > 0, z1 > 0, . . . , zq > 0,

where 1n = (1, . . . , 1) ∈ Rn .
Since (21) defines a pointed convex polyhedron in Rm , say Q, we deduce that there
is a vertex (u1 , . . . , uk , v1 , . . . , vq ) of Q such that in this convex polyhedron
min((y1 + · · · + yk − z1 − · · · − zq )t − (y1 + · · · + yk )) = at − b for t ≫ 0,
10

where a = u1 + · · · + uk − (v1 + · · · + vq ) and b = u1 + · · · + uk . Since ui > 0 and
vj > 0 for every i and j, we have a 6 b.
By the Duality theorem of linear programing (see e.g. [24, Corollary 7.1g]) we have
max{x1 + · · · + xn | (x1 , . . . , xn ) ∈ Pt } = at − b for t ≫ 0.

Therefore, δ(Pt ) = dt − e = at − b for t ≫ 0. It follows that d = a and e = b.
Consequently, d 6 e, as required.

3. Regularity of powers of ideals
Let H = (V, E) be a unimodular hypergraph on the vertex set V = {1, . . . , n}.
Without loss of generality we may assume that E =
6 ∅ and thus J(H) 6= 0. Let
r := rank(H). In this section we will prove that ai (R/J(H)s ) is asymptotically linear
in s; and then settle the problem on bounding s0 such that reg J(H)s is a linear
function for s > s0 .
Lemma 3.1. Assume that ap (R/J(H)s ) 6= −∞ for some p > 0 and s > 1. Then,
there are positive integers d and e such that
(1) d 6 e 6 n2 ;
n
t
(2) ap (R/J(H)
)
>
dt
−
e
for
all
t
>
r
+ 1; and
2
n
s
(3) If s > r 2 + 1, then ap (R/J(H) ) = ds − e.
Proof. Since ap (R/J(H)s ) 6= −∞, there is β ′ = (β1 , . . . , βn ) ∈ Zn such that
Hmp (R/J(H)s )β′ 6= 0 and ap (R/J(H)s ) = |β ′ |.

By Lemma 1.2 we have
e p−|G
(22)
dimK H

β′ |−1

(∆β′ (J(H)s ); K) = dimK Hmp (R/J(H)s )β′ 6= 0.

In particular, ∆β′ (J(H)s ) is not acyclic.
If Gβ′ = [n], then ∆β′ (J(H)s ) is either {∅} or a void complex. Since it is not
acyclic, ∆β′ (J(H)s ) = {∅}. But then by (3) we would have J(H) = 0, a contradiction.
Therefore, Gβ′ 6= [n].
We may assume that Gβ′ = {m + 1, . . . , n} for some 1 6 m 6 n. Set S :=
K[x1 , . . . , xm ]. Let H′ be the hypergraph on the vertex set V ′ = {1, . . . , m} with the
edge set E ′ = {E ∈ E | E ⊆ V ′ }. Since A(H′ ) is a submatrix of A(H), we have H′ is
also a unimodular hypergraph. Moreover, by (1) we obtain:
(23)

J(H)RGβ′ ∩ S = J(H′ ).

Let β := (β1 , . . . , βm ) ∈ Nm . By using Formulas (3) and (23) we get

(24)

∆β (J(H′ )t ) = ∆β′ (J(H)t ) for any t > 1.

e p−|G ′ |−1(∆β (J(H′ )s ); K) 6= 0. By Lemma 1.2 we get
Together with (22), it gives H
β
p−|Gβ′ |

Hn

(S/J(H′ )s )β 6= 0,

where n = (x1 , . . . , xm ) is the homogeneous maximal ideal of S.
11

Suppose that E ′ = {E1 , . . . , Ek } where k > 1. Then, by Equation (2)
∆(J(H′ )) = hV ′ \ E1 , . . . , V ′ \ Ek i .

By Lemma 1.3 we may assume that

∆β (J(H′ )s ) = hV ′ \ E1 , . . . , V ′ \ Eq i

where 1 6 q 6 k.
For each integer t > 1, let Pt be the set of solutions in Rm of the following system:
P

for j = 1, . . . , q,
Pi∈Ej xi 6 t − 1
(25)
for j = q + 1, . . . , k,
i∈Ej xi > t


x1 > 0, . . . , xm > 0.

Then, β ∈ Ps . From (25) and Lemma 1.3 one has

(26)

∆α (J(H′ )t ) = hV \ E1 , . . . , V \ Eq i = ∆β (J(H′ )s ) whenever α ∈ Pt ∩ Nm .

Together Lemmas 2.6 and 2.7 with Remark 2.4, there are positive integers d and f
with d 6 f 6 m2 such that
lmm
δ(Pt ) = dt − f , for all t > r
+ 1.
2
 
For any t > r n2 + 1, we also have δ(Pt ) = dt − f . Let α = (α1 , . . . , αm ) be a
vertex of Pt such that δ(Pt ) = |α|. Since A(H′ ) is totally unimodular, α ∈ Nm .
Let α′ = (α1 , . . . , αm , −1, . . . , −1) ∈ Zn . Then, Gα′ = Gβ′ , and by (24) and (26)
we obtain
∆α′ (J(H)t ) = ∆α (J(H′ )t ) = ∆β (J(H′ )s ) = ∆β′ (J(H)s ).
By Lemma 1.2 we have
e i−|G ′ |−1 (∆α′ (J(H)t ); K)
dimK Hmp (R/J(H)t )α′ = dimK H
α
e
= dimK Hi−|G ′ |−1 (∆β′ (J(H)s ); K) 6= 0.
β

Consequently,

Hmp (R/J(H)t )α′

6= 0, and so

ap (R/J(H)t ) > |α′ | = |α| − (n − m) = dt − (f + n − m) = dt − e,

where we set e := f + n − m. Note that d 6 f 6 e 6 m2 + (n − m) 6 n2 .
′
This argument
 n  shows that β = (β1 , . . . , βm , −1, . . . , −1) and |β| = δ(Ps ). Therefore, if s > r 2 + 1 then |β| = δ(Ps ) = ds − f and
ap (R/J(H)s ) = |β′ | = |β| − (n − m) = ds − (f + n − m) = ds − e,

and the lemma follows.



We now prove that ai (R/J(H)s ) is asymptotically linear in s.
Theorem 3.2. For any i, we have either ai (R/J(H)s ) = −∞ for all s > 1 or there
are positive integers d and e with d 6 e such that ai (R/J(H)s ) = ds − e for all s > n2 .
12

Proof. If n = 1, then R = K[x1 ] and J(H) = (x1 ), and then the theorem holds for
this case. We therefore may assume that n > 2.
Assume that ai (R/J(H)k ) 6= −∞
  for some k > 1. By Lemma 3.1 we have
ai (R/J(H)t ) 6= −∞ for every t > r n2 + 1.
 
Let s0 be an integer such that s0 > n2 . Note that r n2 + 1 6 n2 as n > 2,
so ai (R/J(H)s0 ) 6= −∞. By Lemma 3.1, there are positive integers d and e with
d 6 e 6 n2 such that
(a) ai (R/J(H)s0 ) = ds0 − e; and
 
(b) ai (R/J(H)t ) > dt − e for all t > r n2 + 1.
We will prove that ai (R/J(H)s ) = ds − e for all s > n2 . Indeed, for any s > n2 , by
Lemma 3.1 again, there are positive integers a and b with a 6 b 6 n2 such that
(c) ai (R/J(H)s ) = as − b; and
 
(d) ai (R/J(H)t ) > at − b for all t > r n2 + 1.
From (b) and (c) we have as − b > ds − e, or equivalently,
(a − d)s > b − e.

(27)

Note that 1 6 b, e 6 n2 , so |b − e| = max{b − e, e − b} 6 n2 − 1 < s. Together with
the inequality (27), this fact forces a > d.
Similarly, by using (a) and (d) we obtain d > a and
(d − a)s0 > e − b.

(28)

Thus, a = d. Together this fact with Inequalities (27) and (28), respectively, we
get e > b and b > e, respectively. Hence, b = e. Then,
and the proof is complete.

ai (R/J(H)s ) = as − b = ds − e,



The following theorem is the main result of this paper.
Theorem 3.3. Let H be a unimodular hypergraph with n vertices and rank r. Then
s
there is a non-negative integer
 n  e 6 dim R/J(H) − d(J(H)) + 1 such that reg J(H) =
d(J(H))s + e for all s > r 2 + 1.

Proof. If n = 1 or r = 1, then J(H) is a principal ideal, and the theorem holds for
these cases. Hence we may assume that n > 2 and r > 2.
Let δ := dim R/J(H). Then, δ < n as J(H) 6= 0. Since
reg R/J(H)t ) = max{ai (R/J(H)t ) + i | i = 0, . . . , δ} for t > 1,

by Theorem 3.2 we imply that there are integers t0 , d and e with e 6 δ − d such that
(29)

reg R/J(H)t = dt + e for all t > t0 .

Note that reg J(H)t = reg R/J(H)t + 1, so when comparing with [20, Theorem 5]
we deduce that d = d(J(H)) and e > −1. Consequently, e 6 δ − d(J(H)).
Let k be an integer such that k > max{t0 , 2n2 }. Assume that reg R/J(H)k =
ai (R/J(H)k ) + i, for some 0 6 i 6 δ. By Lemma 3.1, there are non-negative integers
13

a and b′ with a6 b′ 6 n2 such that ai (R/J(H)k ) = ak − b′ and ai (R/J(H)t ) > at − b′
for all t > r n2 + 1.
Let b := −b′ + i. Then, −n2 6 b 6 i − a 6 δ − a, reg R/J(H)k = ak + b and
lnm
+ 1.
(30)
reg R/J(H)t > at + b for all t > r
2
As reg R/J(H)k = ak + b = dk + e, we have (d − a)k = b − e. Together with the
fact |b − e| 6 |b| + e 6 n2 + δ + 1 6 n2 + n < 2n2 6 k, it forces d = a, and so b = e.
Thus, (30) becomes
lnm
t
(31)
reg R/J(H) > dt + e for all t > r
+ 1.
2
We next prove that these inequalities are in fact equalities and therefore the theorem
follows because reg J(H)t = reg R/J(H)t + 1 for t > 1.
 
In order to prove this, let s be an integer such that s > r n2 + 1. By the argument
above, there are integers c and f with f 6 δ − c such that reg R/J(H)s = cs + f and
lnm
+ 1.
(32)
reg R/J(H)t > ct + f for all t > r
2
From (29) and (32) we get c 6 d. Since reg R/J(H)s = cs + f , by (31) we have
cs + f > ds + e, so (d − c)s 6 f − e. As c 6 d, it follows that f > e. In particular,
f > −1. Observe that n 6 s as r > 2, so that
f − e 6 (δ − c) + 1 6 δ < n 6 s.

Together with (d − c)s 6 f − e and c 6 d, this fact forces d − c = 0, i.e. d = c.
Combining this equality with (29) and (32) we get e > f , and therefore e = f .
Finally, because d = c and e = f , we have reg R/J(H)s = cs + f = ds + e, and the
proof of the theorem is complete.

Corollary 3.4. Let G be a bipartite graph with n vertices. Then, reg J(G)s is a linear
function in s for all s > n + 2.
Acknowledgment. This work is partially supported by NAFOSTED (Vietnam) under the grant number 101.04-2015.02. The first author is also partially supported by
Thai Nguyen university of Science under the grant number D̄H2016-TN06-03.
References
[1] A. Alilooee, S. Beyarslan and S. Selvaraja, Regularity of Powers of Unicyclic Graphs,
arXiv:1702.00916.
[2] A. Banerjee, The regularity of powers of edge ideals, J. Algebr. Comb. 41(2015), no. 2, 303 –
321.
[3] C. Berge, Hypergraphs: combinatorics of finite sets. North-Holland, New York, 1989.
[4] D. Berlekamp, Regularity defect stabilization of powers of an ideal. Math. Res. Lett. 19 (2012),
no. 1, 109 – 119.
[5] S. Beyarslan, Hà H.T. and T. N. Trung. Regularity of powers of forests and cycles, J. Algebraic
Combin., 42 (2015), no. 4, 1077 – 1095.
14

[6] M. Chardin, Powers of ideals and the cohomology of stalks and fibers of morphisms, Algebra
Number Theory 7 (2013), no. 1, 1 – 18.
[7] M. Chardin, Regularity stabilization for the powers of graded M-primary ideals. Proc. Amer.
Math. Soc. 143 (2015), no. 8, 3343–3349.
[8] S. Cutkosky, Irrational asymptotic behaviour of Castelnuovo-Mumford regularity, J. Reine
Angew. Math. 522 (2000), 93 – 103.
[9] D. Cutkosky, J. Herzog and N. V. Trung, Asymptotic behavior of the Castelnuovo-Mumford
regularity, Compositio Math. 118 (1999), 243 – 261.
[10] D. Eisenbud and J. Harris, Powers of ideals and fibers of morphisms, Math. Res. Lett. 17 (2010),
no. 2, 267 – 273.
[11] D. Eisenbud and B. Ulrich, Notes on regularity stabilization, Proc. Amer. Math. Soc. 140 (2012),
no. 4, 1221 – 1232.
[12] H. T. Hà, Asymptotic linearity of regularity and a∗ -invariant of powers of ideals, Math. Res.
Lett. 18 (2011), no. 1, 1–9.
[13] H. T. Hà, N. V. Trung and T. N. Trung, Depth and regularity of powers of sums of ideals, Math.
Z. 282 (2016), no. 3-4, 819–838.
[14] N. T. Hang and T. N. Trung, The behavior of depth functions of powers of cover ideals of
unimodular hypergraphs, Ark. Math. (preprint 2016 to appear).
[15] J. Herzog, T. Hibi and N. V. Trung, Vertex cover algebras of unimodular hypergraphs, Proc.
Amer. Math. Soc. 137 (2009), 409–414.
[16] L. T. Hoa, K. Kimura, N. Terai and T. N. Trung, Stability of depths of symbolic powers of
Stanley-Reisner ideals, J. Algebra 473 (2017), 307–323.
[17] L. T. Hoa and T. N. Trung, Partial Castelnuovo-Mumford regularities of sums and intersections
of powers of monomial ideals, Math. Proc. Cambridge Philos Soc. 149 (2010), 1–18.
[18] M. Hochster, Cohen-Macaulay rings, combinatorics, and simplicial complexes, in B. R. McDonald and R. A. Morris (eds.), Ring theory II, Lect. Notes in Pure and Appl. Math. 26, M.
Dekker, 1977, 171–223.
[19] A. V. Jayanthan, N. Narayanan and S. Selvaraja, Regularity of Powers of Bipartite Graphs,
arXiv:1609.01402.
[20] V. Kodiyalam, Asymptotic behaviour of Castelnuovo-Mumford regularity, Proc. Amer. Math.
Soc. 128 (2000), 407 – 411.
[21] N. C. Minh and N. V. Trung, Cohen-Macaulayness of powers of two-dimensional squarefree
monomial ideals, J. Algebra 322 (2009), 4219–4227.
[22] E. Miller and B. Sturmfels, Combinatorial commutative algebra. Springer, 2005.
[23] N. C. Minh and T. N. Trung, Regularity of symbolic powers and Arboricity of matroids,
arXiv:1702.04491.
[24] A. Schrijver, Theory of linear and integer programming, John Wiley & Sons, 1998.
[25] Y. Takayama, Combinatorial characterizations of generalized Cohen-Macaulay monomial ideals,
Bull. Math. Soc. Sci. Math. Roumanie (N.S.) 48 (2005), 327–344.
[26] N. V. Trung and H. Wang, On the asymptotic linearity of Castelnuovo-Mumford regularity, J.
Pure Appl. Algebra 201(2005), no. 1–3, 42–48 .
Thai Nguyen College of Sciences, Thai Nguyen University, Thai Nguyen, Vietnam
E-mail address: nguyenthuhang0508@gmail.com
Institute of Mathematics, VAST, 18 Hoang Quoc Viet, Hanoi, Viet Nam
E-mail address: tntrung@math.ac.vn

15

