RESOLUTION AND REGULARITY OF COVER IDEALS OF CERTAIN
MULTIPARTITE GRAPHS

arXiv:1709.05055v1 [math.AC] 15 Sep 2017

A. V. JAYANTHAN AND NEERAJ KUMAR
Abstract. Let G be a finite simple graph on n vertices. Let JG ⊂ K[x1 , . . . , xn ] be the cover ideal
of G. In this article, we obtain the graded minimal free resolution and the Castelnuovo-Mumford
s
regularity of JG
for all s ≥ 1 for certain multipartite graphs G.

1. Introduction
Recently there have been a lot of research on various properties of powers of homogeneous ideals.
In particular, there have been a lot of interest on Castelnuovo-Mumford regularity of powers of
ideals. It was shown by Kodiyalam [19] and independently by Cutkosky, Herzog and Trung [5]
that if I is a homogeneous ideal in a polynomial ring, then there exist non-negative integers d, e
and s0 such that reg(I s ) = ds + e for all s ≥ s0 , where reg(−) denote the Castelnuovo-Mumford
regularity. Kodiyalam proved that d ≤ deg(I), where deg(I) denotes the largest degree of a
homogeneous minimal generator of I. In general, the stability index s0 and the constant term e are
hard to compute. There have been discrete attempts in identifying s0 and e for certain classes of
ideals. Given a finite simple graph, one can identify the vertices with indeterminates and associate
ideals in a polynomial ring, for example, edge ideals and cover ideals (see Section 2 for definition)
corresponding to the given graph. For edge ideals of various classes of graphs, e and s0 have been
computed, see for example [1, 6, 7, 10, 15, 17, 18, 20, 21, 23, 28, 29, 30, 31]. In the case of edge
ideals, d = 2 and in the known cases, e is connected to combinatorial invariants associated with
the graph G. Not much is known about the regularity of powers of cover ideals. Since cover ideal
is the Alexander dual of the edge ideal, its regularity is equal to the projective dimension of the
edge ideal, [25]. In [24], Seyed Fakhari studied certain homological properties of symbolic powers
of cover ideals of very well-covered and bipartite graphs. For a finite simple graph G on the vertex
set {x1 , . . . , xn }, let JG ⊂ R = K[x1 , . . . , xn ], where K is a field, denote the cover ideal of G. It
(s)
was shown that if G is a very well-covered graph and JG has a linear resolution, then JG has a
linear resolution for all s ≥ 1. Furthermore, it was proved that if G is a bipartite graph with n
vertices, then for s ≥ 1,
s
reg(JG
) ≤ s deg(JG ) + reg(JG ) + 1.
Hang and Trung, in [26], studied unimodular hypergraphs and proved that if H is a unimodular
hypergraph on n vertices and rank r and JH is the cover ideal of H, then there exists a non-negative
integer e ≤ dim(R/JH ) − deg(JH ) + 1 such that
s
regJH
= deg(JH )s + e

for all s ≥ rn
2 + 1. Since bipartite graphs are unimodular, their results hold true in the case of
bipartite graphs as well. While the first result gives an upper bound for the constant term, the
later result gives the upper bound for both the stability index and the constant term.
The Betti numbers and regularity are classical invariants associated to a module which can be
computed from the resolution. However, one may be able to compute them without completely
describing the resolution. To compute the syzygies explicitly is a challenging task. In this article,
s
we obtain the complete description of the minimal free resolution, including the syzygies, of JG
1

s ). The
for some classes of multipartite graphs, thereby obtaining a precise expression for reg(JG
paper is organized as follows. In Section 2, we collect the preliminaries required for the rest of the
paper. We study the resolution of powers of cover ideals of certain bipartite graphs in Section 3. If
G is a complete bipartite graph, then JG is a regular sequence and hence the minimal graded free
s can be obtained from [9, Theorem 2.1]. It can be seen that, in this case the index
resolution of JG
of stability, s0 = 1 and the constant term is one less than the size of the minimum vertex cover.
We then move on to study some classes of bipartite graphs which are not complete. We obtain the
resolution and precise expressions for the regularity of powers of cover ideals of certain bipartite
graphs.
Section 4 is devoted to the study of resolution and regularity of powers of cover ideals of certain
complete multipartite graphs. When G is the cycle of length three or the complete graph on 4
s for all s ≥ 1. This allow us to
vertices, we describe the graded minimal free resolution of JG
s for all s ≥ 1. As a consequence,
compute the Betti numbers, Hilbert series and the regularity of JG
for cover ideals of complete tripartite and 4-partite graphs, we obtain precise expressions for the
s . We conclude our article with a conjecture on the resolution
Betti numbers and the regularity of JG
s for all s ≥ 1, where G is a complete multipartite graph.
of JG

Acknowledgements: Part of the work was done while the second author was visiting Indian
Institute of Technology Madras. He would like to thank IIT Madras for their hospitality during
the visit. All our computations were done using Macaulay 2, [8].
2. Preliminaries
In this section, we set the notation for the rest of the paper. All the graphs that we consider
in this article are finite, simple and without isolated vertices. For a graph G, V (G) denotes the
set of all vertices of G and E(G) denotes the set of all edges of G. A graph G is said to be a
complete multipartite graph if V (G) can be partitioned into sets V1 , . . . , Vk for some k ≥ 2 such
that {x, y} ∈ E(G) if and only if x ∈ Vi and y ∈ Vj for i 6= j. When k = 2, the graph is called
a complete bipartite graph. If k = 2 with |V1 | = m and |V2 | = n, we denote the corresponding
complete bipartite graph by Km,n or by KV1 ,V2 . If G and H are graphs, then G ∪ H denote the
graph on the vertex set V (G) ∪ V (H) with E(G ∪ H) = E(G) ∪ E(H). A graph G is called a
bipartite graph if V (G) = V1 ⊔ V2 such that {x, y} ∈ E(G) only if x ∈ V1 and y ∈ V2 . A subset
w = {xi1 , . . . , xir } of V (G) is said to be a vertex cover of G if w ∩ e 6= ∅ for every e ∈ E(G). A
vertex cover is said to be minimal if it is minimal with respect to inclusion.
Let G be a graph with V (G) = {x1 , . . . , xn }. Let K be a field and R = K[x1 , . . . , xn ]. The
ideal I(G) = h{xi xj : {xi , xj } ∈ E(G)}i ⊂ S is called the edge ideal of G and the ideal JG =
h{xi1 · · · xir : {xi1 , . . . , xir } is a vertex cover of G}i is called the cover ideal of G. It can also be
seen that JG is the Alexander dual of I(G).
Let S = R/I, where R is a polynomial ring over K and I a homogeneous ideal of R. For a
finitely generated graded S-module M = ⊕Mi , set
tSi (M ) = max{j : TorSi (M, K)j 6= 0},
with tSi (M ) = −∞ if TorSi (M, K) = 0. The Castelnuovo-Mumford regularity, denoted by regS (M ),
of an S-module M is defined to be
regS M = max{tSi (M ) − i : i ≥ 0}.
3. Bipartite Graphs
In this section, we study the regularity of powers of cover ideals of certain bipartite graphs. We
begin with a simple observation concerning the vertex covers of a bipartite graph.
2

Proposition 3.1. Let G be a bipartite graph on n + m vertices. Then G is a complete bipartite
graph if and only if JG is generated by a regular sequence.
Proof. Let V (G) = X ⊔ Y be the partition of the vertex set of G with X = {x1 , . . . , xn } and
Y = {yn+1 , . . . , yn+m }. First note that JG is generated by a regular sequence if and only if for any
two minimal vertex covers w, w′ , w ∩ w′ = ∅. If G = Kn,m , then JG = (x1 · · · xn , yn+1 · · · yn+m )
which is a regular sequence.
Q Conversely,
Q suppose G is not a complete bipartite graph. Since G is a
bipartite graph, note that xi ∈X xi , yj ∈Y yj ∈ JG are minimal generators of JG . Therefore, there
exist xi0 ∈ X and yi0 ∈ Y such that {xi0 , yi0 } ∈
/ E(G). Then w = {xi , yj : i 6= i0 and yj ∈ NG (xi0 )}
is a minimal vertex cover of G that intersects X as well as Y non-trivially. Therefore JG is not a
complete intersection.

First we discuss the regularity of powers of cover ideals of complete bipartite graphs. Since the
cover ideal of a complete bipartite graph is a complete intersection, the result is a consequence of
[9, Theorem 2.1].
Theorem 3.2. Let J = JKm,n be the cover ideal of the complete bipartite graph Km,n , m ≤ n.
Then reg(J s ) = sn + m − 1 for all s ≥ 1.
Proof. Consider the ideal I = (T1 , T2 ) ⊂ R = K[T1 , T2 ] with deg T1 = m and deg T2 = n. It follows
from [9, Theorem 2.1] that the resolution of I s is
M
M
0→
R(−a1 m − a2 n) →
R(−a1 m − a2 n) → I s → 0.
(1)
a1 +a2 =s+1
ai ≥1

a1 +a2 =s

Note that J = (x1 · · · xm , ym+1 · · · ym+n ). Set x1 · · · xm = T1 and ym+1 · · · ym+n = T2 . Then J s
has the minimal free resolution as in (1). If m ≤ n, then reg(J s ) = sn + m − 1.

It follows from Theorem 3.2 that in the case of the complete bipartite graph Km,n , the stability
index is 1 and the constant term is τ − 1, where τ is the size of a minimum vertex cover.
We now move on to study the cover ideals of bipartite graphs that are not complete. Since this
is a huge class, we do not expect that a single expression may represent the regularity of powers
of their cover ideals. Therefore, we restrict our attention to some of the structured subclasses of
bipartite graphs.
We begin our investigation by describing certain properties of the cover ideals of a certain class
of Cohen-Macaulay bipartite graphs.
Theorem 3.3. Let G be the graph with V (G) = {x1 , . . . , xn , y1 , . . . , yn } and E(G) = {{x1 , yj }, {xi , yi } :
1 ≤ j ≤ n, 2 ≤ i ≤ n}. Let JG ⊂ R = K[x1 , . . . , xn , y1 , . . . , yn ] be the cover ideal of G. Then
(1) µ(JG ) = 2n−1 + 1;
(2) JG is generated in degree n and has a linear quotient;
(3) JG has an n-linear resolution and hence reg JG = n;
s has a ns-linear resolution and hence reg J s = ns;
(4) JG
G
(5) pdim R/JG = n.
Proof. (1): Let w denote a minimal vertex cover of G. If x1 ∈ w, then one and only one of {xi , yi }
is in w. And, if x1 ∈
/ w, then w = {y1 , . . . , yn }. Therefore, JG is minimally generated by elements
of the form y1 · · · yn and x1 xi1 · · · xij yij+1 · · · yin−1 , where 0 ≤ j ≤ n − 1 and 2 ≤ ik ≤ n for all k.
Pn−1 n−1
Therefore, µ(JG ) = 1 + j=0
= 2n−1 + 1.
j
(2): Clearly a minimal vertex cover has n elements so that JG is generated in degree n. Write
JG = (f1 , . . . , f2n−1 +1 ), where f1 < f2 < · · · f2n−1 +1 written in the graded reverse lexicographic
ordering induced by x1 > · · · > xn > y1 > · · · > yn . We prove that JG has linear quotients. Note
that it is enough to prove that for an i and j < i, there exists k < i such that fk : fi = ut and ut |fj ,
3

Q
Q
where ut = xt or yt , [16]. For fi , let Ai = {ij ∈ [n] : degxi fi = 1}. Then fi = r∈A xr s∈Ac ys .
j
Let fj < fi be given. Let r ∈ Ai \ Aj . Let fk = xyrr fi . Then fk < fi and fk : fi = yr . Since r ∈
/ Aj ,
yr |fj . Hence JG has linear quotients.
s has a linear resolution for all s ≥ 1. Since J s is
(3)&(4): Since JG has linear quotients, JG
G
s
generated in degree ns, reg(JG ) = ns.
(5): It follows from [12, Theorem 3.4] that G is a Cohen-Macaulay bipartite graph. Therefore,
reg(I(G)) = ν(G) + 1, where ν(G) denotes the independence matching number of G, [20]. It is easy
to see that ν(G) = n − 1. Therefore, reg(I(G)) = 2n − (n − 1) − 1 = n. Since JG = I(G)∨ , by [25]
pdim(R/JG ) = n.

In a personal communication, we have been informed that Seyed Fakhari has proved that if G is
a bipartite graph, then for all s ≥ 1,
s
s deg(JG ) ≤ reg(JG
) ≤ (s − 1) deg(JG ) + |V (G)| − 1.

We note that the class of bipartite graphs discussed in Theorem 3.3 attain the lower bound.
Let U1 , . . . , Un and V1 , . . . , Vn be sets of vertices. Set U = U1 ∪ · · · ∪ Un and V = V1 ∪ · · · ∪ Vn . Let
G = KU1 ,V ∪KU2 ,V2 ∪· · ·∪KUn ,Vn . For 1 ≤ i, j ≤ n, set Ui = {xi1 , . . . , xini } and Vj = {yj1 , . . . , yjmj }.
Let JG denote the cover idealQ
of G. Then JG can be
Qidentified with the cover ideal described in
Theorem 3.3 by taking xi = xir ∈Ui xir and yj = yjs ∈Vj yjs . But in this case, since deg xi is
not necessarily one, the resolution need not be linear and hence the computation of regularity is
non-trivial. We now study the resolution and the regularity for n = 2.
Theorem 3.4. Let U = U1 ⊔ U2 and V = V1 ⊔ V2 be a collection of vertices with |U | = n, |Ui | =
ni , |V | = m, |Vi | = mi and 1 ≤ ni , mi for i = 1, 2. Let G be the bipartite graph KU1 ,V ∪ KU2 ,V2 . Let
R = K[x1 , . . . , xn , y1 , . . . , ym ]. Let JG ⊂ R denote the cover ideal of G. Then the graded minimal
free resolution of R/JG is of the form:
0 −→ R(−n − m2 ) ⊕ R(−m − n1 ) −→ R(−(n1 + m2 )) ⊕ R(−m) ⊕ R(−n) −→ R −→ 0.
In particular,
reg(JG ) = max{n + m2 − 1, m + n1 − 1}
Proof. It can easily be seen that the cover ideal JG is generated by g1 = x1 · · · xn , g2 = y1 · · · ym ,
and g3 = x1 · · · xn1 ym1 +1 · · · ym . Set X1 = x1 · · · xn1 ; X2 = xn1 +1 · · · xn ; Y1 = y1 · · · ym1 and
Y2 = ym1 +1 · · · ym . Then we can write g1 = X1 X2 , g2 = Y1 Y2 and g3 = X1 Y2 .
Consider the minimal graded free resolution of R/JG over R:
∂

∂

2
1
· · · −→ F −→
R(−n) ⊕ R(−m) ⊕ R(−(n1 + m2 )) −→
R −→ 0,

where ∂1 (e1 ) = g1 , ∂1 (e2 ) = g2 , and ∂1 (e3 ) = g3 .
Let ae1 + be2 + ce3 ∈ ker ∂1 . Then aX1 X2 + bY1 Y2 + cX1 Y2 = 0. Solving the above equation, it
can be seen that,
ker ∂1 = SpanR {Y2 e1 − X2 e3 , X1 e2 − Y1 e3 }.
Also, it is easily verified that these two generators are R-linearly independent. Hence ker ∂1 ∼
= R2 .
Note that deg(Y1 e1 − X2 e3 ) = n + m1 and deg(X1 e2 − Y1 e3 ) = n1 + m. Therefore, we get the
minimal free resolution of R/JG as:
∂

∂

2
1
0 −→ R(−n − m2 ) ⊕ R(−m − n1 ) −→
R(−(n1 + m2 )) ⊕ R(−m) ⊕ R(−n) −→
R −→ 0,

where ∂2 (a, b) = a(Y1 e1 − X2 e3 ) + b(X1 e2 − Y1 e3 ). The regularity assertion follows immediately
from the resolution.

4

s , where J is the cover ideal disNow, our aim is to compute the resolution and regularity of JG
G
cussed in Theorem 3.4. For this, we first study the resolution of powers of the ideal (X1 X2 , X1 Y2 , Y1 Y2 )
and obtain the resolution and regularity of the cover ideal as a consequence.

Theorem 3.5. Let R = K[X1 , X2 , Y1 , Y2 ] and J = (X1 X2 , X1 Y2 , Y1 Y2 ) be an ideal of R. Then, for
s ≥ 2, the minimal free resolution of R/J s is of the form
s+1
2

s

0 −→ R(2) −→ R2(

) −→ R(s+2
2 ) −→ R −→ 0,

and reg(J s ) = 2s.
Proof. Denote the generators of J by g1 = X1 X2 , g2 = X1 Y2 , and g3 = Y1 Y2 . Note that J is the
edge ideal of P4 , the path graph on the vertices {X1 , X2 , Y1 , Y2 }. Since P4 is chordal, it follows that
R/J s has a linear resolution for all s ≥ 1, [14]. Now we compute the Betti number of the R/J s .
Write
(g1 , g2 , g3 )s = (g1s , g1s−1 (g2 , g3 ), g1s−2 (g2 , g3 )2 , . . . , g1 (g2 , g3 )s−1 , (g2 , g3 )s )
where
(g2 , g3 )t = (g2t , g2t−1 g3 , g2t−2 g32 , . . . , g2 g3t−1 , g3t ).
.
For i ≥ j, set Mi,j = g1s−i g2i−j g3j = (X1 X2 )s−i Y2i Y1j X1i−j . It follows that µ(J s ) = (s+1)(s+2)
2
(s+1)(s+2)
. Let {ep,q | 0 ≤ p ≤ s; 0 ≤ q ≤ p} denote the standard basis for Rβ1 . Let
Set β1 =
2
β
∂1 : R 1 −→ R be the map ∂1 (ep,q ) = Mp,q . Since gi ’s are monomials, the kernel is generated by
binomials of the form mi,j Mi,j − mk,l Mk,l , where mp,q ’s are monomials in R. Since the resolution
of R/J s is linear, it is enough to find the linear syzygy relations among the generators of ker(∂1 ).
Mi,j
X
To find these linear syzygies, we need to find conditions on i, j, k, l such that Mk,l
is equal to Yqp
Yq
Xp

for some p, q. First of all, note that for such linear syzygies, |i − k|, |j − l| ≤ 1. If i = k and
g3
Y1
Mi,j
=
=
. We get the same relation if i = k and j = l − 1. If i = k + 1
j = l + 1, then
Mi,j+1
g2
X1
Mi,j
g2
Y2
and j = l, then
=
=
. As before, i = k − 1 yields the same relation. Therefore, the
Mi−1,j
g1
X2
kernel is minimally generated by
or

{Y1 ei,j − X1 ei,j+1 , X2 ei,j − Y2 ei−1,j | 0 ≤ j < i ≤ s} .

2(s+1
2 ) as
Hence, µ(ker ∂1 ) = 2 s+1
2 . Write the basis elements of R
{e1,i,p , e2,i,q | 1 ≤ i ≤ s, 0 ≤ p < i and 0 ≤ q < i}

s+1
2

and define ∂2 : R2(

) −→ Rβ1 by
∂2 (e1,i,p ) = Y1 ei,p − X1 ei,p+1
∂2 (e2,i,q ) = X2 ei,q − Y2 ei−1,q .

By [22, Proposition 3.2], pdim(R/J s ) = 3 for all s ≥ 2. Hence we conclude that the minimal
graded free resolution of R/J s is of the form
s+1
2

0 −→ Rβ3 −→ R2(

s+2
∂2
∂1
) −→
R( 2 ) −→
R −→ 0.

Therefore,

 

s+1
s+2
β3 − 2
+
− 1 = 0,
2
2

so that β3 = 2s . Now we compute the generators of the second syzygy. Again, since the resolution
is linear, it is enough to compute linear generators. First, note that
B = {Y2 e1,i,j − X2 e1,i+1,j + Y1 e2,i+1,j − X1 e2,i+1,j+1 | 0 ≤ j < i < s} ⊆ ker ∂2 .
5


It can easily be verified that B is R-linearly independent. Since µ(ker ∂2 ) = 2s , B generates ker ∂2 .
s
s
Let {E | 0 ≤ j < i < s} denote the standard basis for R(2) . Define ∂ : R(2) → Rs(s+1) by
3

i,j

∂3 (Ei,j ) = Y2 e1,i,j − X2 e1,i+1,j + X1 e2,i+1,j − Y1 e2,i+1,j+1 .
Therefore, we get the minimal free resolution of R/J s as
s

3
0 → R(2) −→
R2(

∂

s+1
2

s+2
∂2
∂1
)−
→ R( 2 ) −→
R −→ 0.

Since the resolution is linear, reg J s = 2s.



It is to be noted that the resolution and the projective dimension of the powers of the edge ideals
of path graphs are known in the literature. In Theorem 3.5, we obtain the syzygies and the Betti
numbers explicitly. The knowledge of syzygies is crucial in obtaining the regularity of powers of
edge ideals of certain bipartite graphs as seen below:
Theorem 3.6. Let U = U1 ⊔ U2 and V = V1 ⊔ V2 be a collection of vertices with |U | = n, |Ui | =
ni , |V | = m, |Vi | = mi and 1 ≤ ni , mi for i = 1, 2. Let G be the bipartite graph KU1 ,V ∪ KU2 ,V2 .
Let R = K[x1 , . . . , xn , y1 , . . . , ym ]. Let JG ⊂ R denote the cover ideal of G. Then the minimal free
s is of the form:
resolution of R/JG
s

s+1
2

0 −→ R(2) −→ R2(

) −→ R(s+2
2 ) −→ R −→ 0.

Moreover,

(s − j)n1 + (s − i)n2 + jm1 + im2



(s
− j)n1 + (s − i)n2 + (j + 1)m1 + im2 − 1
s
reg JG
= max
(s
−
j)n1 + (s − i + 1)n2 + jm1 + im2 − 1



(s − j)n1 + (s − i)n2 + (j + 1)m1 + (i + 1)m2 − 2

for
for
for
for

0≤j
0≤j
0≤j
0≤j

≤i≤s
<i≤s
.
<i≤s
<i<s

Proof. Let R = K[x1 , . . . , xn , y1 , . . . , ym ]. Then JG = (x1 · · · xn , y1 · · · ym , x1 · · · xn1 ym1 +1 · · · ym ).
Set X1 = x1 · · · xn1 , X2 = xn1 +1 · · · xn , Y1 = y1 · · · ym1 and Y2 = ym1 +1 · · · ym . Then JG =
s has the given minimal free
(X1 X2 , Y1 Y2 , X1 Y2 ). Therefore, it follows from Theorem 3.4 that JG
resolution.
To compute the regularity, we need to obtain the degrees of the syzygies. These shifts are given
by the degrees of the minimal generators of the syzygies. Following the notation in the proof of
Theorem 3.4, we can see that
deg ei,j
deg e1,i,j
deg e2,i,j
deg Ei,j

=
=
=
=

(s − j)n1 + (s − i)n2 + jm1 + im2 ,
(s − j)n1 + (s − i)n2 + (j + 1)m1 + im2 ,
(s − j)n1 + (s − i + 1)n2 + jm1 + im2 ,
(s − j)n1 + (s − i)n2 + (j + 1)m1 + (i + 1)m2 .

Therefore, the assertion on the regularity follows.



3.1. Discussion. It has been proved by Hang and Trung, [27], that if G is a bipartite graph on
n vertices and JG is the cover ideal of G, then there exists a non-negative integer e such that
s ) = deg(J )s + e, where deg(J ) denote the maximal degree of minimal
for s ≥ n + 2, reg(JG
G
G
monomial generators of JG . It follows from Theorem 3.2 that if G = Kn,m with n ≥ m, then
e = m − 1 and the index of stability is 1. If the graph is not a complete bipartite graph, then
e does not uniformly represent a combinatorial invariant associated to the graph as can be seen
s ) for some classes of bipartite
in the computations below. We compute the polynomial reg(JG
graphs that are considered in Corollary 3.6. We see that e depends on the relation between the
s ), we need to identify which of those
integers n1 , n2 , m1 and m2 . To find the polynomial reg(JG
relations give rise to the regularity. If we assume that all those integers are at least one, then
6

deg ei,j will not play a role in deciding the regularity. Note that deg e1,i,j − deg e2,i,j = m1 − n2 and
deg e2,i,j − deg Ei,j = n2 − (m1 + m2 ). Therefore, depending on the relation between these integers,
s . We first deal with two simple cases. The
one can decide the expression for the regularity of JG
first case shows that the constant term can as well be zero.
(1) If m1 = m2 = 1, then it can be seen that for s ≥ 2,
s
reg(JG
) = max{(s − j)n1 + (s − i + 1)n2 + jm1 + im2 − 1 : 0 ≤ j < i ≤ s}.

Since (s − j)n1 + (s − i + 1)n2 + jm1 + im2 − 1 = s(n1 + n2 ) + j(1 − n1 ) + i(1 − n2 ) + n2 − 1
and n1 ≥ 1, n2 ≥ 1, this expression attains maximum when i and j attain minimum, i.e.,
s ) = ns. Thus, in this case, e = 0. It can also be noted
if j = 0 and i = 1. Therefore, reg(JG
that, since n ≥ 2, it follows from Theorem 3.4 that reg(JG ) = n. Therefore, in this case,
the stability index is also equal to 1.
(2) If n1 = n2 = m1 = m2 = ℓ > 1, then for s ≥ 2,
s
reg(JG
) = max{(s − j)n1 + (s − i)n2 + (j + 1)m1 + (i + 1)m2 − 2 : 0 ≤ j < i ≤ s}.
s ) = 2ℓs + (2ℓ − 2) and hence e = 2ℓ − 2. Note that in this case, the
Therefore, reg(JG
stability index is 2.
s ), s ≥ 2. Assume that
Now we discuss some more cases and compute the polynomial reg(JG
n 2 = m1 .

(1) n1 ≥ m2 ≥ n2 = m1 : Note that, in this case, deg(JG ) = n1 + m2 . We have
s
reg(JG
) = max{(s − j)n1 + (s − i)n2 + (j + 1)m1 + (i + 1)m2 − 2 : 0 ≤ j < i < s}.

Since (s − j)n1 + (s − i)n2 + (j + 1)m1 + (i+ 1)m2 − 2 = s(n1 + n2 )+ j(m1 − n1 )+ i(m2 − n2 )+
m1 + m2 − 2. Since n1 ≥ m1 and m2 ≥ n2 , the above expression attains the maximum when
i attains the maximum and j attains the minimum, i.e., if i = s − 1 and j = 0. Therefore,
s ) = (n + m )s + (n + m − 2) and hence e = n + m − 2.
reg(JG
1
2
2
1
2
1
(2) n1 ≥ n2 = m1 ≥ m2 : In this case, deg(JG ) = n and
s
reg(JG
) = max{(s − j)n1 + (s − i)n2 + (j + 1)m1 + (i + 1)m2 − 2 : 0 ≤ j < i < s}.

As in the previous case, one can conclude that the maximum is attained when i = 1 and
s ) = ns + (2m − 2). Thus e = 2m − 2.
j = 0. Therefore, reg(JG
2
2
(3) n2 = m1 ≥ n1 ≥ m2 : As done earlier, one can conclude that reg(JG )s = ns + (2m2 − 2)
and hence e = 2m2 − 2.
(4) Similarly analyzing the relation between these integers, one can obtain the regularity expressions as follows:
n2 = m1
reg(JsG ), s ≥ 2
n2 = m1 ≤ n1 ≤ m2 (n1 + m2 )s + (m1 + n2 − 2)
n1 ≤ n2 = m1 ≤ m2 (m1 + m2 )s + (n1 + m2 − 2)
n1 ≤ m2 ≤ n2 = m1 (m1 + m2 )s + (n1 + m2 − 2)
It can be noted that in the case n2 = m1 , the stability index is 2.
Remark 3.7. If G = KU1 ,V ∪ KU2 ,V2 ∪ KU3 ,V3 , for some set of vertices Ui , Vi , then one can still
s using a similar approach. However, the
describe the complete resolution and the regularity of JG
resulting syzygies are not so easy to describe though the generating sets are similar. Therefore, we
restrict ourselves to the above discussion.
7

4. Complete Multipartite Graphs
In this section our goal is to understand the resolution and regularity of the powers of cover
ideals of complete m-partite graphs. Let G be a complete m-partite graph and let JG be the cover
ideal of G. The main idea in constructing the resolution of JG is to identify JG with the cover ideal
of the complete graph Km on m vertices. Then one replaces the variables by the product of a set
of variables from each partitions of m-partite graphs to get the cover ideal JG .
Let R = K[x1 , . . . , xm ]. It is known that the cover ideal JG of complete graph G = Km is generated by all squarefree monomials x1 x2 · · · x̂i · · · xm of degree m − 1. Moreover one can also identify
this cover ideal with the squarefree Veronese ideal I = Im,m−1 , and hence it is a polymatroidal
ideal, [11].
Let I ⊂ R be an ideal of R. The ideal I is said to have linear quotients if there exists an ordered
system of homogeneous generators f1 , . . . , fℓ of I such that for all j = 1, . . . , ℓ the colon ideals
(f1 , . . . , fj−1 ) : fj are generated by a subset of {x1 , . . . , xn }. It was proved by Conca and Herzog
that a polymatroidal ideal has linear quotients with respect to the reverse lexicographical order
of the generators [4, Proposition 5.2]. Herzog and Hibi proved that if I is generated in degree
d and has linear quotients, then I has a d-linear resolution, [13, Proposition 8.2.1]. Furthermore
product of polymatroidal monomial ideals are polymatroidal [4, Theorem 5.3]. Hence powers of
polymatroidal monomial ideals are polymatroidal. Therefore we have the following:
Remark 4.1. The cover ideal JG of complete graph G = Km has linear quotients and hence has
s has linear resolution for all s ≥ 1.
linear resolution. Moreover JG
If I is an ideal of R all of whose powers have linear resolution, then depth R/I k is a non-increasing
function of k and depth R/I k is constant for all k ≫ 0, [11, Proposition 2.1]. Further, we have:
Remark 4.2. [11, Corollary 3.4] Let R = K[x1 , · · · , xm ] and JG be the cover ideal of G = Km .
Then
s
depth R/JG
= max{0, m − s − 1}.
s = 0 for all s ≥ m − 1.
In particular, depth R/JG

We begin our investigation by studying the resolution of powers of cover ideal of K3 .
4.1. Complete tripartite: It has been shown by Beyarslan et al., [2, Theorem 5.2], that reg(I(C3 )s ) =
2s for all s ≥ 2. We first describe the graded minimal free resolution of I(C3 )s for all s ≥ 1. We
also obtain the Hilbert series of the powers.
Theorem 4.3. Let R = K[x1 , x2 , x3 ] and I = (x1 x2 , x1 x3 , x2 x3 ). Then the graded minimal free
resolution of R/I is of the form:
0 → R(−3)2 → R(−2)3 → R → 0.
For s ≥ 2, the graded minimal free resolution of R/I s is of the form:
s+1
s+2
s
0 → R(−2s − 2)(2) → R(−2s − 1)2( 2 ) → R(−2s)( 2 ) → R → 0

so that regR (I s ) = 2s. Moreover, the Hilbert series of R/I s is given by


− 2s − 1 t2s
1 + 2t + 3t2 + · · · + 2st2s−1 − s+2
s
2
.
H(R/I , t) =
(1 − t)
Proof. It is clear that the resolution of I is as given in the assertion of the theorem. Therefore
reg(R/I) = 1. It follows from [14], that I s has a linear minimal free resolution for all s ≥ 1.
8

Note that by [3, Lemma 3.1], depth R/I s = 0 for all s ≥ 2 so that pdim R/I s = 3 for all s ≥ 2.
Hence, the minimal free resolution of R/I s is of the form:
∂

∂

∂

3
2
1
0 → R(−2s − 2)β3 −→
R(−2s − 1)β2 −→
R(−2s)β1 −→
R→0

Now we describe completely the minimal free resolution of R/I s for s ≥ 2. Let g1 = x1 x2 , g2 = x1 x3
and g3 = x2 x3 . Write I s = (g1s , g1s−1 (g2 , g3 ), . . . , g1 (g2 , g3 )s−1 , (g2 , g3 )s ). The generators of I s are of
the form g1ℓ1 g2ℓ2 g3ℓ3 , where 0 ≤ ℓ1 , ℓ2 , ℓ3 ≤ s and ℓ1 + ℓ2 + ℓ3 = s. Denote by fℓ1 ,ℓ2 ,ℓ3 = g1ℓ1 g2ℓ2 g3ℓ3 .

3 s−ℓ2 s−ℓ1
Then fℓ1 ,ℓ2 ,ℓ3 = xs−ℓ
x2 x3 . It is easy to see that µ(I s ) = s+2
1
2 , since the minimal number of
generating elements of the monomial ideal I s is same as the total number of non-negative integral
solution of ℓ1 + ℓ2 + ℓ3 = s, which is s+2
2 .
s+2
Let {e
: 0 ≤ ℓ , ℓ , ℓ ≤ s; ℓ + ℓ + ℓ = s} denote the standard basis for R( 2 )
1

ℓ1 ,ℓ2 ,ℓ3

2

3

1

2

3

s+2
and consider the map ∂1 : R( 2 ) → R defined by ∂1 (eℓ1 ,ℓ2 ,ℓ3 ) = fℓ1 ,ℓ2 ,ℓ3 . We find the minimal
generators for ker ∂1 . Since fℓ1 ,ℓ2 ,ℓ3 ’s are monomials, the kernel is generated by binomials of the
form mℓ1 ,ℓ2 ,ℓ3 fℓ1 ,ℓ2 ,ℓ3 − mt1 ,t2 ,t3 ft1 ,t2 ,t3 , where mi,j,k ’s are monomials in R. Also, since the minimal
fℓ ,ℓ ,ℓ
free resolution is linear, the kernel is generated in degree 1. Note that 1 2 3 = x1t3 −ℓ3 x2t2 −ℓ2 x3t1 −ℓ1 .
ft1 ,t2 ,t3
fℓ1 ,ℓ2 ,ℓ3
to be a linear fraction, |ti − ℓi | ≤ 1 for i = 1, 2, 3.
Hence, for
ft1 ,t2 ,t3
Let t3 = ℓ3 , t2 = ℓ2 + 1 and t1 = ℓ1 − 1. The corresponding linear syzygy relation is

x3 · fℓ1 ,ℓ2 ,ℓ3 − x2 · fℓ1 −1,ℓ2 +1,ℓ3 = 0,

(2)

where 1 ≤ ℓ1 ≤ s, and 0 ≤ ℓ2 , ℓ3 ≤ s − 1. Note that the number
of such relations is equal to the

number of integral solution to (ℓ1 − 1) + ℓ2 + ℓ3 = s, i.e., s+1
.
Similarly,
if t3 = ℓ3 + 1, t2 = ℓ2 − 1
2
and t1 = ℓ1 , then we get the corresponding linear syzygy relation as
x2 · fℓ1 ,ℓ2 ,ℓ3 − x1 · fℓ1 ,ℓ2 −1,ℓ3 +1 = 0,

(3)

where 0 ≤ ℓ1 , ℓ3 ≤ s − 1, and 1 ≤ ℓ2 ≤ s. Note that the linear syzygy relation obtained by fixing
ℓ2 and taking |ℓi − ti | = 1 for i = 1, 2
x3 · fℓ1 ,ℓ2 ,ℓ3 − x1 · fℓ1 −1,ℓ2 ,ℓ3 +1 = 0
can be obtained from Equations (2), (3) by setting the ℓi ’s appropriately. Therefore,
ker ∂1 = hx3 ·eℓ1 ,ℓ2 ,ℓ3 −x2 ·eℓ1 −1,ℓ2 +1,ℓ3 , x2 ·eℓ1 −1,ℓ2 +1,ℓ3 −x1 ·eℓ1 −1,ℓ2 ,ℓ3 +1 : 1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s−1i.


Since there are s+1
minimal generators of each type in the list above, µ(ker ∂1 ) = β2 = 2 s+1
2
2 .
s+1
Write the standard basis of R2( 2 ) as


e1,(ℓ2 +1,ℓ3 ),ℓ1 −1
: 1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s − 1
B2 =
e2,(ℓ1 ,ℓ2 ),ℓ3
s+1
2

and define ∂2 : R2(

) → R(s+2
2 ) by

∂2 (e1,(ℓ2 +1,ℓ3 ),ℓ1 −1 ) = x2 · eℓ1 −1,ℓ2 +1,ℓ3 − x1 · eℓ1 −1,ℓ2 ,ℓ3 +1 ,
∂2 (e2,(ℓ1 ,ℓ2 ),ℓ3 ) = x3 · eℓ1 ,ℓ2 ,ℓ3 − x2 · eℓ1 −1,ℓ2 +1,ℓ3 .



From the equation, β3 − 2(s+1)
+ s+2
− 1 = 0, it follows that β3 = 2s . Now, we describe ker ∂2 .
2
2
For 2 ≤ ℓ1 ≤ s and 0 ≤ ℓ2 , ℓ3 ≤ s − 2, set
Eℓ1 ,ℓ2 ,ℓ3 = −x3 · e2,(ℓ1 −1,ℓ2 ),ℓ3 +1 + x2 · e2,(ℓ1 −1,ℓ2 +1),ℓ3 + x2 · e1,(ℓ2 +2,ℓ3 ),ℓ1 −2 − x3 · e1,(ℓ2 +1,ℓ3 ),ℓ1 −1 .
Note that
B3 = {Eℓ1 ,ℓ2 ,ℓ3 : 2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s − 2} ⊂ ker ∂2 .
9

s
2


, ker ∂2 = hB3 i. Let {Hℓ1 ,ℓ2 ,ℓ3 : 2 ≤ ℓ1 ≤ s, 0 ≤
s
s
2(s+1)
(
)
ℓ2 , ℓ3 ≤ s − 2} denote the standard basis of R 2 . Define ∂3 : R(2) → R( 2 ) by ∂3 (Hℓ1 ,ℓ2 ,ℓ3 ) =
Eℓ1 ,ℓ2 ,ℓ3 which completes the description of the resolution.
It can also be seen that deg eℓ1 ,ℓ2 ,ℓ3 = 2s, deg e1,(ℓ2 +1,ℓ3 ),ℓ1 −1 = deg e2,(ℓ1 ,ℓ2 ),ℓ3 = 2s + 1 and
deg Hℓ1 ,ℓ2 ,ℓ3 = 2s + 2. Therefore we get the minimal graded free resolution of R/I s as

Since B3 is R-linearly independent and |B3 | =

s
2(s+1)
s+2
∂1
∂3
∂2
0 → R(−2s − 2)(2) −→
R(−2s − 1)( 2 ) −→
R(−2s)( 2 ) −→
R → 0.

Therefore, the Hilbert series of R/I s is given by
 2s

s+1 2s+1
1 − s+2
− 2s t2s+2
s
2 t +2 2 t
H(R/I , t) =
(1 − t)3


s+2 2s
s+1 2s+1
−
−2 (1 −
2 t +2 2 t
= (1 − t)
(1 − t)

s
2



t2s+2 )

.

By expanding (1 − t)−2 in the power series form and multiplying with the numerator, we get the
required expression.

We now proceed to compute the minimal graded free resolution of powers of complete tripartite
graphs.
Notation 4.4. Let G denote a complete tripartite graph with V (G) = V1 ⊔ V2 ⊔ V3 and E(G) =
{{a, b} : b ∈ Vi , b ∈ Vj , i 6= j}. Set V1 = {x1 , . . . , xℓ }, V2 = {y1 , . . . , ym } and V3 = {z1 , . . . , zn }.
Q
Qn
Q
Let JG denote the vertex cover ideal of G. Let X = ℓi=1 xi , Y = m
k=1 zi . It
j=1 yi and Z =
can be seen that JG = (XY, XZ, Y Z).
Theorem 4.5. Let R = K[x1 , . . . xm1 , y1 , . . . , ym2 , z1 , . . . , zm3 ]. Let G be a complete tripartite graph
as in Notation 4.4. Let JG ⊂ R denote the cover ideal of G. Then for all s ≥ 2, the minimal free
s is of the form:
resolution of R/JG
s
2(s+1)
s+2
∂3
∂2
∂1
0 → R(2) −→
R( 2 ) −→
R( 2 ) −→
R → 0.

Set α = (s − ℓ3 )m1 + (s − ℓ2 )m2 + (s − ℓ1 )m3 . Then for all s ≥ 2,

for 0 ≤ ℓ1 , ℓ2 , ℓ3 ≤ s,
 α,
s
α + m3 − 1,
for 1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s − 1,
reg(JG ) = max

α + 2m3 − 2, for 2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s − 2.

Proof. Taking X = x1 , Y = x2 and Z = x3 in Theorem 4.3, it follows that the minimal free
s is of the given form:
resolution of S/JG
s

3
0 → R(2) −→
R(

∂

2(s+1)
2

s+2
∂2
∂1
) −→
R( 2 ) −→
R → 0.

We now compute the degrees of the generators and hence obtain the regularity. Let deg X1 =
m1 , deg X2 = m2 , and deg X3 = m3 . Then it follows that


deg eℓ1 ,ℓ2 ,ℓ3 = deg X1s−ℓ3 X2s−ℓ3 X3s−ℓ1 = (s − ℓ3 )m1 + (s − ℓ2 )m2 + (s − ℓ1 )m3 .
We observe that
deg e1,(ℓ2 +1,ℓ3 ),ℓ1 −1 = deg e2,(ℓ1 ,ℓ2 ),ℓ3 = deg eℓ1 ,ℓ2 ,ℓ3 + deg X3 ,
deg Hℓ1 ,ℓ2 ,ℓ3 = deg eℓ1 ,ℓ2 ,ℓ3 + 2 deg X3 .
10

Therefore,

 deg eℓ1 ,ℓ2 ,ℓ3 ,
s
deg eℓ1 ,ℓ2 ,ℓ3 + deg(X3 ) − 1,
reg(JG ) = max

deg eℓ1 ,ℓ2 ,ℓ3 + 2 deg(X3 ) − 2,

for 0 ≤ ℓ1 , ℓ2 , ℓ3 ≤ s,
for 1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s − 1,
for 2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s − 2,

where ℓ1 + ℓ2 + ℓ3 = s. Let α = deg eℓ1 ,ℓ2 ,ℓ3 . Then the regularity assertion follows.



s ) is not really in the form as + b. Given a graph, one
Observe that the above expression for reg(JG
can derive this form from the above expression. Depending on the size of partitions, the leading
coefficient and the constant term will change. For example, suppose the graph is unmixed, i.e.,
s ) = 2ℓs + (2ℓ − 2) for all s ≥ 2, where
all the partitions are of same cardinality. Then reg(JG
ℓ = m1 = m2 = m3 . Note also that the stabilization index in this case is 2. As done in Discussion
s ) for different cases as well. Consider the
(3.1), one can derive various expressions for reg(JG
arithmetic progression m1 = m + 2r, m2 = m, and m3 = m + r:

Corollary 4.6. Let m, r be any two positive integers. Let m1 = m + 2r, m2 = m, and m3 = m + r
in Theorem 4.5. Then for all s ≥ 2, we have
s
reg(JG
) = s(2m + 3r) + 2m − 2.

Proof. By Theorem 4.5, α = (s − ℓ3 )m1 + (s − ℓ2 )m2 + (s − ℓ1 )m3 . Hence we get
α = s(3m + 3r) − ℓ3 (m + 2r) − ℓ2 (m) − ℓ1 (m + r).
Using Theorem 4.5, we have for all s ≥ 2,

 α,
s
α + (m + r) − 1,
reg(JG
) = max

α + 2(m + r) − 2,

for 0 ≤ ℓ1 , ℓ2 , ℓ3 ≤ s,
for 1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s − 1,
for 2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s − 2,

s ) is maximum of all the numbers, we need to maximize
where ℓ1 +ℓ2 +ℓ3 = s. Since regularity reg(JG
the value of α. For this to happen, negative terms in α should be minimum. The coefficient of ℓ3
is largest among the negative terms in α, so ℓ3 should be assigned the least value. After ℓ3 , assign
the minimum value to ℓ1 , and finally take ℓ2 = s − ℓ1 − ℓ3 . For example, to get the maximum of α
when 2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 ≤ s − 2, put ℓ3 = 0, ℓ1 = 2, and ℓ2 = s − 2. We get for all s ≥ 2

for 0 ≤ ℓ1 , ℓ2 , ℓ3 , ℓ4 ≤ s,
 s(2m + 3r),
s
s(2m + 3r) + m − 1,
for 1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 1,
reg(JG ) = max

s(2m + 3r) + 2m − 2, for 2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 2.

For all m ≥ 1, and for all s ≥ 2, we get

s
reg(JG
) = s(2m + 3r) + 2m − 2.


4.2. Complete 4-partite graphs. We now describe the resolution and regularity of powers of
cover ideals of 4-partite graphs. For this purpose, we first study the resolution of powers of cover
ideal of the complete graph K4 .
Theorem 4.7. Let R = K[x1 , x2 , x3 , x4 ] and I = (x1 x2 x3 , x1 x2 x4 , x1 x3 x4 , x2 x3 x4 ). Then, for
s ≥ 3, the minimal graded free resolution of R/I s is of the form
0 → R(−3s − 3)β4 −→R(−3s − 2)β3 −→R(−3s − 1)β2 −→R(−3s)β1 −→R → 0
where
β1 =








 
s+3
s+2
s+1
s
, β2 = 3
, β3 = 3
, and β4 =
.
3
3
3
3
11

In particular, regR (R/I s ) = 3s. Moreover the Hilbert series of R/I s is given by


1 + 2t + 3t2 + 4t3 + · · · + 3st3s−1 − s+3
− 3s − 1 t3s +
s
3
H(R/I , t) =
(1 − t)2
 3s

P3s−1
s+3
s 3s+1
i
i=0 (i + 1)t − (3s + 1 −
3 )t + 3 t
.
=
(1 − t)2

s 3s+1
3 t

Proof. By Remark 4.1, I s has linear resolution for all s ≥ 1. Moreover, by Remark 4.2, depth R/I s =
0 for all s ≥ 3 and hence pdim R/I s = 4 for all s ≥ 3. Therefore, the minimal graded free resolution
of R/I s , for s ≥ 3, is of the form
∂

∂

∂

∂

4
3
2
1
0 → R(−3s − 3)β4 −→
R(−3s − 2)β3 −→
R(−3s − 1)β2 −→
R(−3s)β1 −→
R → 0.

Let g1 = x1 x2 x3 , g2 = x1 x2 x4 , g3 = x1 x3 x4 and g4 = x2 x3 x4 . The minimal generators of I s are
of the form g1ℓ1 g2ℓ2 g3ℓ3 g4ℓ4 where 0 ≤ ℓi ≤ s for every i and ℓ1 + ℓ2 + ℓ3 + ℓ4 = s. The number of
non-negative integral solution to the linear equation ℓ1 + ℓ2 + ℓ3 + ℓ4 = s is s+3
3 . Hence we have
s+3
ℓ1 ℓ2 ℓ3 ℓ4
s−ℓ4 s−ℓ3 s−ℓ2 s−ℓ1
s
µ(J ) = β1 = 3 . Note that g1 g2 g3 g4 = x1 x2 x3 x4
with 0 ≤ ℓ1 , ℓ2 , ℓ3 , ℓ4 ≤ s. Set
s−ℓ4 s−ℓ3 s−ℓ2 s−ℓ1
fℓ1 ,ℓ2 ,ℓ3 ,ℓ4 = x1 x2 x3 x4 . Let
{eℓ1 ,ℓ2 ,ℓ3 ,ℓ4 : 0 ≤ ℓ1 , ℓ2 , ℓ3 , ℓ4 ≤ s and ℓ1 + ℓ2 + ℓ3 + ℓ4 = s}
s+3
s+3
denote the standard basis of R( 3 ) and consider the map ∂1 : R( 3 ) → R defined by ∂1 (eℓ1 ,ℓ2 ,ℓ3 ,ℓ4 ) =
fℓ1 ,ℓ2 ,ℓ3 ,ℓ4 . Now we find the minimal generators for ker ∂1 .
Let fℓ1 ,ℓ2 ,ℓ3 ,ℓ4 , ft1 ,t2 ,t3 ,t4 be any two minimal monomial generators of I s . It is known that the
kernel of ∂1 is generated by binomials of the form mℓ1 ,ℓ2 ,ℓ3 ,ℓ4 fℓ1 ,ℓ2 ,ℓ3 ,ℓ4 − mt1 ,t2 ,t3 ,t4 ft1 ,t2 ,t3 ,t4 , where
mi,j,k,l ’s are monomials in R. Since the syzygy is generated by linear binomials, we need to find

conditions on ℓ1 , ℓ2 , ℓ3 , ℓ4 such that

fℓ1 ,ℓ2 ,ℓ3 ,ℓ4
ft1 ,t2 ,t3 ,t4

is equal to

xi
xj

for some i, j. Observe that

fℓ1 ,ℓ2 ,ℓ3 ,ℓ4
= x1t4 −ℓ4 x2t3 −ℓ3 x3t2 −ℓ2 x4t1 −ℓ1 .
ft1 ,t2 ,t3 ,t4
Suppose t4 = ℓ4 + 1, t3 = ℓ3 − 1 and tj = ℓj for j = 1, 2. Then we get the linear syzygy relation
x2 fℓ1 ,ℓ2 ,ℓ3 ,ℓ4 − x1 fℓ1 ,ℓ2 ,ℓ3 −1,ℓ4 +1 = 0.

(4)

Fixing t3 and t4 , with 1 ≤ t3 + t4 ≤ s, there are as many linear syzygies are there as the
 number

s+1
of solutions of t1 + t2 = s − (t3 + t4 ). Therefore, for the pair (t3 , t4 ), there are 2 + 2s +


· · · + 22 = s+2
number of solutions. Similarly for each pair (t4 , t2 ), (t4 , t1 ), (t3 , t2 ), (t3 , t1 ) and
3
s+2
(t2 , t1 ), we get 3 linear syzygies. Note that the syzygies x4 ft1 +1,t2 −1,t3 ,t4 − x3 ft1 ,t2 ,t3 ,t4 and
x3 ft1 ,t2 ,t3 ,t4 − x2 ft1 ,t2 −1,t3 +1,t4 give rise to another linear syzygy x4 ft1 +1,t2 −1,t3 ,t4 − x2 ft1 ,t2 −1,t3 +1,t4 .
The same linear syzygy can also be obtained from a combination of linear syzygies that arise out of
the pairs (t1 , t4 ) and (t3 , t4 ). Therefore, to get a minimal generating set, we only need to consider
linear
syzygies corresponding to the pairs (t1 , t2 ), (t2 , t3 ) and (t3 , t4 ). For each such pair, we have
s+2
number of linear syzygies. Hence β2 = 3 s+2
3
3 .
3(s+2
)
3
Write the basis elements of R
as


 e(1,ℓ1 −1,ℓ2 ),ℓ3 +1,ℓ4

e(2,ℓ1 −1,ℓ4 ),ℓ2 +1,ℓ3 : 1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 1
B2 =


e(3,ℓ3 ,ℓ4 ),ℓ1 ,ℓ2
12

s+1
2

and define ∂2 : R3(

) −→ Rβ1 by

∂2 (e(1,ℓ1 −1,ℓ2 ),ℓ3 +1,ℓ4 ) = x2 eℓ1 −1,ℓ2 ,ℓ3 +1,ℓ4 − x1 eℓ1 −1,ℓ2 ,ℓ3 ,ℓ4 +1 ;
∂2 (e(2,ℓ1 −1,ℓ4 ),ℓ2 +1,ℓ3 ) = x3 eℓ1 −1,ℓ2 +1,ℓ3 ,ℓ4 − x2 eℓ1 −1,ℓ2 ,ℓ3 +1,ℓ4 ;
∂2 (e(3,ℓ3 ,ℓ4 ),ℓ1 ,ℓ2 ) = x4 eℓ1 ,ℓ2 ,ℓ3 ,ℓ4 − x3 eℓ1 −1,ℓ2 +1,ℓ3 ,ℓ4 .
Now we decipher the Betti numbers β3 and β4 to complete the resolution. The Hilbert series of
R/I s is

1 − β1 t3s + β2 t3s+1 − β3 t3s+2 + β4 t3s+3
p(t)
s
=
.
H(R/I , t) =
(1 − t)4
(1 − t)4
Since dim R/I s = 2, the polynomial p(t) has a factor (1 − t)2 . Note that (1 − t)2 is a monic
polynomial of degree 2, hence we can write p(t) = (1 − t)2 · q(t) where
q(t) = β4 t3s+1 + (2β4 − β3 )t3s + a3s−1 t3s−1 + · · · + a1 t + 1.

(5)

On the other hand, we also have

1 − β1 t3s + β2 t3s+1 − β3 t3s+2 + β4 t3s+3
=
(1 − t)2

(6)

(1 + 2t + 3t2 + 4t3 + · · · + (n + 1)tn + · · · ) 1 − β1 t3s + β2 t3s+1 − β3 t3s+2 + β4 t3s+3



= (1 + 2t + 3t2 + · · · + (3s)t3s−1 + (3s + 1 − β1 )t3s + (3s + 2 − 2β1 + β2 )t3s+1 + aj tj + · · · .
For the expressions in Equations (5) and (6) to be equal, they should agree coefficient-wise. In
particular, we should have that
β4 = 3s + 2 − 2β1 + β2 and 2β4 − β3 = 3s + 1 − β1 .


s
On substituting β1 = s+3
and β2 = 3 s+2
3
3 , we get β4 = 3 from the first equation and substituting the value in the second equation, we get β3 = 3 s+1
3 . Now we verify that aj = 0 for all
j ≥ 3s + 2. Note that for r ≥ 2, the coefficient of t3s+r in Equation (6) is
a3s+r = (3s + r + 1) + (r − 2)β4 − (r − 1)β3 + rβ2 − (r + 1)β1 .
Since, 1 − β1 + β2 − β3 + β4 = 0, this
equation
is reduced
to a3s+r = (3s + 3) − β3 + 2β2 − 3β1 .
n+1
n 
n
Applying the binomial identify r+1 = r+1 + r repeatedly, we get a3s+r = 0 for all r ≥ 2.
Hence the Hilbert series of R/I s is



1 + 2t + 3t2 + 4t3 + · · · + 3st3s−1 − s+3
− 3s − 1 t3s + 3s t3s+1
s
3
.
H(R/I , t) =
(1 − t)2
s+1
3

We now complete the description of the resolution. Write the basis elements of R3(


 E1,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 ;

E2,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 , : 2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 2 .
B3 =


E3,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 ,

3 s+2
3(s+1
3 ) −→ R ( 3 ) by
Note that |B3 | = 3 s+1
3 . Now define the map ∂3 : R

) as

∂3 (E1,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 ) = x4 e(2,ℓ1 −1,ℓ4 ),ℓ2 +1,ℓ3 + x4 e(1,ℓ1 −1,ℓ2 ),ℓ3 +1,ℓ4 − x3 e(3,ℓ3 ,ℓ4 ),ℓ1 −1,ℓ2 +1
−x3 e(2,ℓ1 −2,ℓ4 ),ℓ2 +2,ℓ3 − x3 e(1,ℓ1 −2,ℓ2 +1),ℓ3 +1,ℓ4 + x1 e(3,ℓ3 ,ℓ4 +1),ℓ1 −1,ℓ2 ;

∂3 (E2,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 ) = x4 e(1,ℓ1 −1,ℓ2 ),ℓ3 +1,ℓ4 − x3 e(1,ℓ1 −2,ℓ2 +1),ℓ3 +1,ℓ4 − x2 e(3,ℓ3 +1,ℓ4 ),ℓ1 −1,ℓ2
+x1 e(3,ℓ3 ,ℓ4 +1),ℓ1 −1,ℓ2 ;
∂3 (E3,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 ) = x3 e(1,ℓ1 −2,ℓ2 +1),ℓ3 +1,ℓ4 − x2 e(2,ℓ1 −2,ℓ4 ),ℓ2 +1,ℓ3 +1 − x2 e(1,ℓ1 −2,ℓ2 ),ℓ3 +2,ℓ4
+x1 e(2,ℓ1 −2,ℓ4 +1),ℓ2 +1,ℓ3 .
13

We now compute the kernel of ∂3 . Consider the set
A = {Hℓ1 ,ℓ2 ,ℓ3 ,ℓ4 : 3 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 3} ,
where
Hℓ1 ,ℓ2 ,ℓ3 ,ℓ4 = x4 E3,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 − x3 E2,ℓ1 −1,ℓ2 +1,ℓ3 ,ℓ4 − x3 E3,ℓ1 −1,ℓ2 +1,ℓ3 ,ℓ4 + x2 E1,ℓ1 −1,ℓ2 ,ℓ3 +1,ℓ4
−x1 E1,ℓ1 −1,ℓ2 ,ℓ3 ,ℓ4 +1 + x1 E2,ℓ1 −1,ℓ2 ,ℓ3 ,ℓ4 +1 .
One can verify that ∂3 (Hℓ1 ,ℓ2 ,ℓ3 ,ℓ4 ) = 0. Hence the set A lies in the kernel of the map ∂3 . To
say that the set A is precisely the kernel of the map ∂3 , one needs to show that µ(A) = 3s . Let
ℓ′1 = ℓ1 − 3, then one has ℓ′1 + ℓ2 + ℓ3 + ℓ4 = s − 3. The total number of non-negative integral


s
solution of this linear equation is precisely 3s , hence µ(A) = 3s . Write the basis elements of R(3)
s+1
s
as B = {G
: 3 ≤ ℓ ≤ s, 0 ≤ ℓ , ℓ , ℓ ≤ s − 3} and define the map ∂ : R(3) −→ R3( 3 )
4

ℓ1 ,ℓ2 ,ℓ3 ,ℓ4

1

2

3

4

4

by
∂4 (Gℓ1 ,ℓ2 ,ℓ3 ,ℓ4 ) = Hℓ1 ,ℓ2 ,ℓ3 ,ℓ4 .
This is an injective map and hence we get the complete resolution:
0 → R(−3s − 3)β4 −→R(−3s − 2)β3 −→R(−3s − 1)β2 −→R(−3s)β1 −→R → 0.

Note that in the above proof, we used s ≥ 3 only to conclude that pdim(R/I s ) = 4. By
Remark 4.2, depth(R/I) = 2 and hence pdim(R/I) = 2. Similarly, depth(R/I 2 ) = 1 and hence
pdim(R/I 2 ) = 3. This forces ∂2 to be injective when s = 1 and ∂3 to be injective when s = 2. The
computations of syzygies in the cases of resolution of R/I and R/I 2 remain the same as given in
the above proof. Therefore, we get resolutions truncated at Rβ2 in the case of R/I and truncated
at Rβ3 in the case of R/I 2 , with the expressions for β2 and β3 coinciding with the ones given in
the proof. Therefore, we can conclude that in this case, reg(I s ) = 3s for all s ≥ 1.
As an immediate consequence, we obtain an expression for the asymptotic regularity of cover
ideals of complete 4-partite graphs.
Theorem 4.8. Let G denote a complete 4-partite graph with V (G) = ⊔4i=1 Vi and E(G) = {{a, b} : a ∈
Vi , b ∈ Vj , i 6= j}. Set Vi = {xi1 , . . . , ximi } for i = 1, . . . , 4. Let JG ⊂ R = K[xij : 1 ≤ i ≤ 4; 1 ≤
s is of the form:
j ≤ mi ] denote the cover ideal of G. Then the minimal free resolution of R/JG
s
s+1
s+2
s+3
0 → R(3) −→R3( 3 ) −→R3( 3 ) −→R( 3 ) −→R → 0.

Set α = (s − ℓ4 )m1 + (s − ℓ3 )m2 + (s − ℓ2 )m3 + (s − ℓ1 )m4 . Furthermore, we have

α,
for 0 ≤ ℓ1 , ℓ2 , ℓ3 , ℓ4 ≤ s,



α
+
m
−
1,
for
1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 1,
4
s
reg(JG
) = max
α
+
2m
−
2,
for
2
≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 2,

4


α + 3m4 − 3, for 3 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 3,

where ℓ1 + ℓ2 + ℓ3 + ℓ4 = s.
Q i
Proof. Let Xi = m
j=1 xij . Then JG = (X1 X2 X3 , X1 X2 X4 , X1 X3 X4 , X2 X3 X4 ). Set X1 = x1 , X2 =
x2 , X3 = x3 and X4 = x4 in the previous theorem. Then it follows that the minimal free resolution
s is of the given form
of R/JG
s

s+1
3

0 → R(3) −→R3(

s+3
) −→R3(s+2
3 ) −→R( 3 ) −→R → 0.

14

s , we first need to find the degree’s of the generators of the
To compute the regularity of R/JG
syzygies. Following the notation of the previous theorem, we have


deg eℓ1 ,ℓ2 ,ℓ3 ,ℓ4 = deg X1s−ℓ4 X2s−ℓ3 X3s−ℓ2 X4s−ℓ1 = (s − ℓ4 )m1 + (s − ℓ3 )m2 + (s − ℓ2 )m3 + (s − ℓ1 )m4

and we have

deg e(1,ℓ1 −1,ℓ2 ),ℓ3 ,ℓ4 = deg e(2,ℓ1 −1,ℓ4 ),ℓ2 +1,ℓ3 = deg e(3,ℓ3 ,ℓ4 ),ℓ1 ,ℓ2 = deg eℓ1 ,ℓ2 ,ℓ3 ,ℓ4 + deg(X4 );
deg E1,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 = deg E2,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 = deg E3,ℓ1 ,ℓ2 ,ℓ3 ,ℓ4 = deg eℓ1 ,ℓ2 ,ℓ3 ,ℓ4 + 2 deg(X4 );
deg Gℓ1 ,ℓ2 ,ℓ3 ,ℓ4 = deg eℓ1 ,ℓ2 ,ℓ3 ,ℓ4 + 3 deg(X4 ).
Therefore, by setting α = deg eℓ1 ,ℓ2 ,ℓ3 ,ℓ4 , we get

α,



α
+ deg(X4 ) − 1,
s
reg(JG
) = max
α
+ 2 deg(X4 ) − 2,



α + 3 deg(X4 ) − 3,

for
for
for
for

0 ≤ ℓ1 , ℓ2 , ℓ3 , ℓ4 ≤ s,
1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 1,
,
2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 2,
3 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 3,

where ℓ1 + ℓ2 + ℓ3 + ℓ4 = s.



s ) not in the form of a linear polynomial.
Here also, we have obtained an expression for reg(JG
But, as we have demonstrated in the previous cases, this can always be derived for a given graph.
Analyzing the interplay between the cardinalities of the partitions, one can obtain the polynomial
expression. We discuss the unmixed case as an example. Let m1 = m2 = m3 = m4 = m. Then

α = (s − ℓ4 )m1 + (s − ℓ3 )m2 + (s − ℓ2 )m3 + (s − ℓ1 )m4
= (4s − (ℓ1 + ℓ2 + ℓ3 + ℓ4 ))m = 3ms.
s ) = 3ms + (3m − 3) for all s ≥ 3.
Therefore reg(JG
Let the partitions be in an arithmetic progression.

Corollary 4.9. Let m, r be any two positive integers. Consider the arithmetic progression m1 = m,
m2 = m + r, m3 = m + 2r, and m4 = m + 3r in Theorem 4.8. Then, for all s ≥ 3, we have
s
reg(JG
) = s(3m + 6r) + 3m − 3.

Proof. We have from Theorem 4.8, α = (s − ℓ4 )m1 + (s − ℓ3 )m2 + (s − ℓ2 )m3 + (s − ℓ1 )m4 . On
substituting the values of mi ’s in α, we get
α = s(4m + 6r) − mℓ4 − (m + r)ℓ3 − (m + 2r)ℓ2 − (m + 3r)ℓ1
By Theorem 4.8, we have for all s ≥ 3,

α,



α + (m + 3r) − 1,
s
reg(JG
) = max
α + 2(m + 3r) − 2,



α + 3(m + 3r) − 3,

for
for
for
for

0 ≤ ℓ1 , ℓ2 , ℓ3 , ℓ4 ≤ s,
1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 1,
2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 2,
3 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 3,

where ℓ1 + ℓ2 + ℓ3 + ℓ4 = s. To achieve the maximum value of α, negative terms in α should
be minimum. The coefficient of ℓ1 in negative terms in α is largest, so ℓ1 should be assigned the
minimum value. After assigning the minimum value to ℓ1 , assign the minimum value to ℓ2 , and
similarly minimum value to ℓ3 . Then assign ℓ4 = s − ℓ2 − ℓ3 − ℓ4 . For instance, to get the maximum
of α when 1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 1, put ℓ1 = 1, ℓ2 = 0, ℓ3 = 0, and ℓ4 = s − 1. With
appropriate substitution, we get for all s ≥ 3

s(3m + 6r),
for 0 ≤ ℓ1 , ℓ2 , ℓ3 , ℓ4 ≤ s,



s(3m
+
6r)
+
m
−
1,
for
1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 1,
s
reg(JG
) = max
s(3m
+
6r)
+
2m
−
2,
for
2
≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 2,



s(3m + 6r) + 3m − 3, for 3 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , ℓ3 , ℓ4 ≤ s − 3.
15

Clearly for all m ≥ 1, and for all s ≥ 3, we get
s
reg(JG
) = s(3m + 6r) + 3m − 3.


4.3. Complete m-partite graphs. Let G be a complete graph on m-vertices. Then the cover
ideal JG of G is generated by {x1 · · · x̂i · · · xm : 1 ≤ i ≤ m}. It follows from Remark 4.2 that
s = 0 for all s ≥ m − 1. Moreover, by Remark 4.1, we know that R/J s has linear
depth R/JG
G
s for all s ≥ m − 1 is
resolution for all s ≥ 1. Therefore, the minimal graded free resolution of R/JG
of the form
0 → R(−s(m − 1) − m + 1)βm −→ → · · · → R(−s(m − 1) − 1)β2 −→R(−s(m − 1))β1 −→R → 0.
s consists of elements
Let g1 , g2 , . . . , gm be the minimal generators JG . Then the elements in JG
ℓ1 ℓ2
ℓ
Tℓ1 ,ℓ2 ,...,ℓm , where Tℓ1 ,ℓ2 ,...,ℓm = g1 g2 . . . gmm such that ℓ1 + ℓ2 + · · · + ℓm = s and 0 ≤ ℓi ≤ s.
s is same as the total number of non-negative integral
Therefore the total number of elements in JG


s ) = s+m−1 .
solution to the linear equation ℓ1 + ℓ2 + · · · + ℓm = s which is s+m−1
. Hence µ(JG
m−1
m−1

Therefore β1 = s+m−1
m−1 .
Let {eℓ1 ,ℓ2 ,...,ℓm | 0 ≤ ℓi ≤ s; and ℓ1 + ℓ2 + · · · + ℓm = s} denote the standard basis for Rβ1 . Let
∂1 : Rβ1 −→ R be the map ∂1 (eℓ1 ,ℓ2 ,...,ℓm ) = Tℓ1 ,ℓ2 ,...,ℓm . As done in the proofs of Theorems 4.3 and
4.7, we can see that the first syzygy is given by the relations of the form

xi · Tℓ1 ,ℓ2 ,··· ,ℓi−1 ,ℓi −1,ℓi+1 +1,··· ,ℓm − xi+1 · Tℓ1 ,ℓ2 ,··· ,ℓi−1 ,ℓi ,ℓi+1 ,··· ,ℓm = 0
for each 1 ≤ i ≤ m − 1. Set ℓi − 1 = ℓ′i and ℓi+1 + 1 = ℓ′i+1 . Then it can be seen that, for
each 1 ≤ i ≤ m − 1, there exist as many such relations as the number of non-negative integer
solutions of ℓ1 +
· · · + ℓ′i + · · · ℓm = s −1. Therefore,
the total number of such linear relations is

m−1 s+m−2
s+m−2
(m − 1) m−1 . Therefore β2 =
m−1 . However it is not very difficult to realize that
1
writing down the higher syzygy relations are quite challenging. Based on Theorems 4.3 and 4.7 and
some of the experimental results using the computational commutative algebra package Macaulay
2 [8], we propose the following conjecture:
Conjecture 4.10. Let R = K[x1 , x2 , . . . , xm ] and let J be the cover ideal of the complete graph
Km . The minimal graded free resolution of R/I s for all s ≥ m − 1 is of the form
0 → R(−s(m − 1) − m + 1)βm −→ · · · −→ R(−s(m − 1) − 1)β2 −→R(−s(m − 1))β1 −→R → 0,
where
βi =



m−1
i−1




s+m−i
.
m−1

Notice that proving the above conjecture will give the Betti numbers of powers of cover ideals of
complete m-partite graphs. We conclude our article by proposing an expression for the regularity
of powers of the cover ideals of complete m-partite graphs:
Conjecture 4.11. Let G denote a complete m-partite graph with V (G) = ⊔m
i=1 Vi and E(G) =
{{a, b} : a ∈ Vi , b ∈ Vj , i 6= j}. Set Vi = {xi1 , . . . , xini } for i = 1, . . . , m. Let JG ⊂ R =
K[xij : 1 ≤ i ≤ m; 1 ≤ j ≤ ni ] denote the cover ideal of G. Let 0 ≤ ℓ1 , ℓ2 , . . . , ℓm ≤ s be integers
such that ℓ1 + ℓ2 + · · · + ℓm = s. Set
m
m
X
X
ni ℓm+1−i .
ni ) −
α =s·(
i=1

i=1

16

Then for all s ≥ m − 1, one has

α,
for




α
+
n
−
1,
for

m

s
α
+
2(n
−
1),
for
m
reg(JG ) = max

..


.


 α + (m − 1)(n − 1), for
m

0 ≤ ℓ1 , ℓ2 , · · · , ℓm ≤ s,
1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , · · · , ℓm ≤ s − 1,
2 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , · · · , ℓm ≤ s − 2,
m − 1 ≤ ℓ1 ≤ s, 0 ≤ ℓ2 , · · · , ℓm ≤ s − (m − 1).

References
[1] Arindam Banerjee. The regularity of powers of edge ideals. J. Algebraic Combin., 41(2):303–321, 2015.
[2] Selvi Beyarslan, Huy Tài Hà, and Trân Nam Trung. Regularity of powers of forests and cycles. J. Algebraic
Combin., 42(4):1077–1095, 2015.
[3] Janet Chen, Susan Morey, and Anne Sung. The stable set of associated primes of the ideal of a graph. Rocky
Mountain J. Math., 32(1):71–89, 2002.
[4] Aldo Conca and Jürgen Herzog. Castelnuovo-Mumford regularity of products of ideals. Collect. Math., 54(2):137–
152, 2003.
[5] S. Dale Cutkosky, Jürgen Herzog, and Ngô Viêt Trung. Asymptotic behaviour of the Castelnuovo-Mumford
regularity. Compositio Math., 118(3):243–261, 1999.
[6] Hailong Dao, Craig Huneke, and Jay Schweig. Bounds on the regularity and projective dimension of ideals
associated to graphs. J. Algebraic Combin., 38(1):37–55, 2013.
[7] Ralf Fröberg. On Stanley-Reisner rings. In Topics in algebra, Part 2 (Warsaw, 1988), volume 26 of Banach
Center Publ., pages 57–70. PWN, Warsaw, 1990.
[8] Daniel R. Grayson and Michael E. Stillman. Macaulay2, a software system for research in algebraic geometry.
Available at http://www.math.uiuc.edu/Macaulay2/.
[9] Elena Guardo and Adam Van Tuyl. Powers of complete intersections: graded Betti numbers and applications.
Illinois J. Math., 49(1):265–279, 2005.
[10] Huy Tài Hà and Adam Van Tuyl. Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers.
J. Algebraic Combin., 27(2):215–245, 2008.
[11] Jürgen Herzog and Takayuki Hibi. The depth of powers of an ideal. J. Algebra, 291(2):534–550, 2005.
[12] Jürgen Herzog and Takayuki Hibi. Distributive lattices, bipartite graphs and Alexander duality. J. Algebraic
Combin., 22(3):289–302, 2005.
[13] Jürgen Herzog and Takayuki Hibi. Monomial ideals, volume 260 of Graduate Texts in Mathematics. SpringerVerlag London, Ltd., London, 2011.
[14] Jürgen Herzog, Takayuki Hibi, and Xinxian Zheng. Monomial ideals whose powers have a linear resolution. Math.
Scand., 95(1):23–32, 2004.
[15] Sean Jacques. Betti numbers of graph ideals. PhD thesis, University of Sheffield, 2004.
[16] Ali Soleyman Jahan and Xinxian Zheng. Ideals with linear quotients. J. Combin. Theory Ser. A, 117(1):104–110,
2010.
[17] A. V. Jayanthan, N. Narayanan, and S. Selvaraja. Regularity of powers of bipartite graphs. J. Algebraic Comb.,
page To Appear, 2017.
[18] Fahimeh Khosh-Ahang and Somayeh Moradi. Regularity and projective dimension of the edge ideal of C5 -free
vertex decomposable graphs. Proc. Amer. Math. Soc., 142(5):1567–1576, 2014.
[19] Vijay Kodiyalam. Asymptotic behaviour of Castelnuovo-Mumford regularity. Proc. Amer. Math. Soc.,
128(2):407–411, 2000.
[20] Manoj Kummini. Regularity, depth and arithmetic rank of bipartite edge ideals. J. Algebraic Combin., 30(4):429–
445, 2009.
[21] Mohammad Mahmoudi, Amir Mousivand, Marilena Crupi, Giancarlo Rinaldo, Naoki Terai, and Siamak Yassemi.
Vertex decomposability and regularity of very well-covered graphs. J. Pure Appl. Algebra, 215(10):2473–2480,
2011.
[22] Susan Morey. Depths of powers of the edge ideal of a tree. Comm. Algebra, 38(11):4042–4055, 2010.
[23] Eran Nevo and Irena Peeva. C4 -free edge ideals. J. Algebraic Combin., 37(2):243–248, 2013.
[24] S. A. Seyed Fakhari. Symbolic powers of cover ideal of very well-covered and bipartite graphs. ArXiv e-prints,
April 2016.
[25] Naoki Terai. Alexander duality theorem and Stanley-Reisner rings. Sūrikaisekikenkyūsho Kōkyūroku, (1078):174–
184, 1999. Free resolutions of coordinate rings of projective varieties and related topics (Japanese) (Kyoto, 1998).
17

[26] N. Thu Hang and T. N. Trung. Regularity of powers of cover ideals of unimodular hypergraphs. ArXiv e-prints,
May 2017.
[27] N. Thu Hang and T. N. Trung. Regularity of powers of cover ideals of unimodular hypergraphs. ArXiv e-prints,
May 2017.
[28] Adam Van Tuyl. Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity. Arch.
Math. (Basel), 93(5):451–459, 2009.
[29] Rafael H. Villarreal. Unmixed bipartite graphs. Rev. Colombiana Mat., 41(2):393–395, 2007.
[30] Russ Woodroofe. Matchings, coverings, and Castelnuovo-Mumford regularity. J. Commut. Algebra, 6(2):287–304,
2014.
[31] Xinxian Zheng. Resolutions of facet ideals. Comm. Algebra, 32(6):2301–2324, 2004.
E-mail address: jayanav@iitm.ac.in
Department of Mathematics, Indian Institute of Technology Madras, Chennai, INDIA - 60036
E-mail address: neerajk@math.iitb.ac.in, neeraj.unix@gmail.com
Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai, INDIA 400076

18

