# Resolution and Betti numbers of vertex cover ideals

Tài Huy Hà  Mathematics Department, Tulane University, 6823 St. Charles
Avenue, New Orleans, LA 70118, USA<EMAIL_ADDRESS>and  Takayuki Hibi
Department of Pure and Applied Mathematics, Graduate School of Information
Science and Technology, Osaka University, Suita, Osaka 565-0871, Japan
<EMAIL_ADDRESS>
###### Abstract.

The vertex cover ideal $J(G)$ of a finite graph $G$ is studied. We
characterize when a Cohen–Macaulay vertex cover ideal $J(G)$ has a Scarf
minimal free resolution. Furthermore, by using both combinatorial and
topological techniques, the graded Betti number $\beta_{i,i+j}(J(G))$, where
$i$ and $j$ are the projective dimension and the regularity of $J(G)$, is
computed, when $G$ is either a path or a cycle.

###### Key words and phrases:

vertex cover ideal, Scarf resolution, graded Betti number

###### 2020 Mathematics Subject Classification:

Primary 13D02; Secondary 13H10

The first author is partially supported by a Simons Foundation grant. This
research was done while the second author was visiting Mathematics Department
of Tulane University in the spring semester of 2024.

## Introduction

The role of combinatorics is distinguished in the current trends of
commutative algebra. Particularly, the combinatorics of finite graphs has
created fascinating research topics in this area. The present paper continues
along these research directions and investigates algebraic properties and
invariant of monomial ideals associated to finite graphs.

Let $G$ be a finite _simple_ graph on $[n]=\\{1,\ldots,n\\}$, with no loops,
no multiple edges and no isolated vertices, and let $E(G)$ denote the set of
edges of $G$. Let $S=K[x_{1},\ldots,x_{n}]$ be the polynomial ring in $n$
variables over a field $K$. The _edge ideal_ of $G$ is the ideal $I(G)$ of $S$
generated by the monomials $x_{i}x_{j}$ with $\\{i,j\\}\in E(G)$, and the
_vertex cover ideal_ of $G$ is the ideal $J(G)$ of $S$ generated by the
squarefree monomials $x_{i_{1}}x_{i_{2}}\cdots x_{i_{s}}$, with $1\leq
i_{1}<i_{2}<\cdots<i_{s}\leq n$, for which $\\{i_{1},i_{2},\ldots,i_{s}\\}$ is
the vertex cover of $G$.

Homological aspects of edge ideals and vertex cover ideals, together with
their powers, have been much studied. Especially, forces are being poured into
the challenging conjectures that $(I(G))^{q}$ have linear resolution, for
$q\gg 0$, if $G$ is gap-free (cf. [2, 15]), and that $(J(G))^{q}$ are
componentwise linear, for $q\geq 1$, if $G$ is chordal (cf. [10, 14]). In this
paper, we are interested in Scarf complexes/resolutions and graded Betti
numbers of vertex cover ideals.

Scarf complexes have been investigated for monomial ideals in general [3], and
for edge ideals of graphs in particular [7]. On the other hand, it follows
from [6, 9] that $J(G)$ is Cohen–Macaulay, i.e., $S/J(G)$ is Cohen–Macaulay,
if and only if the complementary graph $G^{c}$ of $G$ is chordal. In Theorem
2.3, we completely characterize when a Cohen-Macaulay vertex cover ideal
$J(G)$ admits a Scarf minimal free resolution. We prove that this is the case
if and only if one (or equivalently, all) leaf order of the clique complex of
$G^{c}$ is _sensitive_.

Restricting to the class of paths and cycles, we exhibit an interesting
phenomenon at the highest graded Betti numbers of their vertex cover ideals.
Specifically, in Theorems 3.7 and 4.1, when $G$ is a path or a cycle, the
graded Betti number $\beta_{i,i+j}(J(G))$, where $i$ and $j$ are the
projective dimension and the regularity of $J(G)$, is computed. Particularly,
our results show that for a path and a cycle, the regularity of its vertex
cover ideal is attainable at the last syzygy module. We will use both
combinatorial and topological techniques in the computation of these graded
Betti numbers.

##  1\. Fundamental materials

Let $\Delta$ be a simplicial complex on $[n]=\\{1,\ldots,n\\}$. Thus $\Delta$
is a collection of subsets of $[n]$ with the property that (i)
$\\{i\\}\in\Delta$ for each $i\in[n]$ and (ii) if $F\in\Delta$ and if
$G\subset F$, then $G\in\Delta$. Each $F\in\Delta$ is called a face of
$\Delta$. A facet is a maximal face of $\Delta$. The dimension of $\Delta$ is
$\dim\Delta=d-1$, where $d$ the maximal cardinality of facets of $\Delta$. Let
$f(\Delta)=(f_{0},f_{1},\ldots,f_{d-1})$ be the $f$-vector of $\Delta$, where
$f_{i}$ is the number of faces $F\in\Delta$ with $|F|=i+1$, and
$h(\Delta)=(h_{0},h_{1},\ldots,h_{d})$ the $h$-vector of $\Delta$ which is
defined by the formula

$\sum_{i=0}^{d}f_{i-1}(x-1)^{d-i}=\sum_{i=0}^{d}h_{i}x^{d-i}.$

with $f_{-1}=1$. In particular

(1) $\displaystyle h_{d}=(-1)^{d}\sum_{i=0}^{d}(-1)^{i}f_{i-1},$

and

(2) $\displaystyle h_{d-1}=f_{d-2}-2f_{d-3}+3f_{d-4}-\cdots+(-1)^{d-1}d\cdot
f_{-1}.$

A facet $F$ of a simplicial complex $\Delta$ is said to be a leaf of $\Delta$
if there is a facet $G$ of $\Delta$ with $G\neq F$, called a branch of $F$,
for which $H\cap F\subset G\cap F$ for each facet $H$ of $\Delta$ with $H\neq
F$. A quasi-forest is a simplicial complex $\Delta$ for which there exists a
labelling $F_{1},\ldots,F_{q}$ of the facets of $\Delta$, called a leaf order
of $\Delta$, with the property that $F_{i}$ is a leaf of the subcomplex
$\langle F_{1},\ldots,F_{i}\rangle$ of $\Delta$ for $1<i\leq q$, where

$\displaystyle\langle
F_{1},\ldots,F_{i}\rangle=\bigcup_{j=1}^{i}\\{F\in\Delta:F\subset F_{j}\\}.$

Let $G$ be a finite graph on $[n]$ with no loop, no multiple edge and no
isolated vertex. Let $E(G)$ denote the set of edges of $G$. A cycle $C$ of
length $\ell\geq 3$ of $G$ is a subgraph of $G$ with

$E(C)=\\{\\{i_{1},i_{2}\\},\\{i_{2},i_{3}\\},\ldots,\\{i_{\ell-1},i_{\ell}\\},\\{i_{\ell},i_{1}\\}\\},$

where $i_{j}\neq i_{j^{\prime}}$ if $j\neq j^{\prime}$. A chord of $C$ is an
edge $\\{i_{k},i_{k^{\prime}}\\}$ with $1\leq k<k^{\prime}-1<\ell$. A chordal
graph is a finite graph $G$ for which every cycle of length $>3$ of $G$ has a
chord. A clique of $G$ is a subset $W\subset[n]$ for which $\\{i,j\\}\in E(G)$
if $i,j\in W$ with $i\neq j$. The clique complex of a finite graph $G$ is a
simplicial complex $\Delta(G)$ consisting of all cliques of $G$. The classical
theorem by Dirac [13, Theorem 9.2.12] guarantees that $G$ is chordal if and
only if $\Delta(G)$ is a quasi-forest.

The Alexander dual of a simplicial complex $\Delta$ on $[n]$ is the simplicial
complex $\Delta^{\vee}$ on $[n]$ whose faces are those $[n]\setminus F$ with
$F\subset[n]$ and $F\not\in\Delta$. Let $S=K[x_{1},\ldots,x_{n}]$ deonte the
polynomial ring in $n$ variables over a field $K$. If
$F=\\{i_{1},\ldots,i_{t}\\}\subset[n]$, then $x_{F}$ stands for the squarefree
monomial $x_{i_{1}}\cdots x_{i_{t}}$ of $S$. The Stanley–Reisner ideal of a
simplicial complex $\Delta$ on $[n]$ is the ideal $I_{\Delta}$ of $S$
generated by those squarefree monomials $x_{F}$ with $F\subset[n]$ and
$F\not\in\Delta$. In other words, $I_{\Delta}$ is generated by those $x_{F}$
with $F\subset[n]$ for which $[n]\setminus F$ is a facet of $\Delta^{\vee}$.

A vertex cover of $G$ is a subset $W\subset[n]$ for which $e\cap
W\neq\emptyset$ for all $e\in E(G)$. A minimal vertex cover of $G$ is a vertex
cover of $G$ none of whose proper subsets is a vertex cover of $G$. The edge
ideal of $G$ is the ideal $I(G)$ of $S=K[x_{1},\ldots,x_{n}]$ generated by
those squarefree quadratic monomials $x_{i}x_{j}$ with $\\{i,j\\}\in E(G)$.
The vertex cover ideal of $G$ is the ideal $J(G)$ of $S$ generated by those
squarefree monomials $x_{W}$ for which $W$ is a minimal vertex cover of $G$.
The complementary graph of $G$ is the finite graph $G^{c}$ on $[n]$ whose
edges are those $\\{i,j\\}$ with $i\neq j$ and $\\{i,j\\}\not\in E(G)$. It
follows that $I(G)$ is the Stanley–Reisner ideal of the clique complex
$\Delta(G^{c})$ of $G^{c}$. Since $W\subset[n]$ is a vertex cover of $G$ if
and only if $[n]\setminus W$ is a clique of $G^{c}$, it follows that $J(G)$ is
generated by those squarefree monomials $x_{W}$ for which $[n]\setminus W$ is
a facet of $\Delta(G^{c})$. In other words, $J(G)$ is the Stanley–Reisner
ideal of the Alexander dual $\Delta(G^{c})^{\vee}$ of $\Delta(G^{c})$.

##  2\. Cohen–Macaulay vertex cover ideals

Let $G$ be a finite graph on $[n]$ and $S=K[x_{1},\ldots,x_{n}]$ the
polynomial ring in $n$ variables over a field $K$. Fröberg’s theorem (cf. [9]
and [13, Theorem 9.2.3]) says that the edge ideal $I(G)$ has linear resolution
if and only if the complementary graph $G^{c}$ of $G$ is chordal. On the other
hand, Eagon–Reiner theorem (cf. [6] and [13, Theorem 8.1.9]) guarantees that
the vertex cover ideal $J(G)$ is Cohen–Macaulay, i.e., the quotient ring
$S/J(G)$ is Cohen–Macaulay, if and only if $I(G)$ has linear resolution. In
other words, $J(G)$ is Cohen–Macaulay if and only if $G^{c}$ is chordal.

Throughout this section, we will assume that $G$ is a finite graph whose
complementary graph $G^{c}$ is chordal. We refer the reader to [7] for a quick
introduction to Scarf resolutions.

Let $\Delta(G^{c})$ be the clique complex of $G^{c}$. Thus $\Delta(G^{c})$ is
a quasi-forest. Fix a leaf order $F_{1},F_{2},\ldots,F_{q}$ of the facets of
$\Delta(G^{c})$. Let ${\mathcal{A}}$ denote the multiset of all intersections

$F_{i_{1}}\cap F_{i_{2}}\cap\cdots\cap F_{i_{j}},\,\,\,\,\,1\leq
i_{1}<i_{2}<\cdots<i_{j}\leq q,\,\,\,j\geq 2,$

of $F_{1},\ldots,F_{q}$. Let ${\mathcal{A}}^{*}$ denote the subset of
${\mathcal{A}}$ consisting of those ${\mathcal{F}}\in{\mathcal{A}}$ whose
multiplicity is $1$. For example, if $n=6$ and
$F_{1}=\\{1,2,3\\},F_{2}=\\{2,3,4\\},F_{3}=\\{3,5\\},F_{4}=\\{4,6\\}$, then
the multiset ${\mathcal{A}}$ is
$\\{\\{2,3\\},\\{4\\},\\{3\\}^{3},\emptyset^{6}\\}$ and
${\mathcal{A}}^{*}=\\{\\{2,3\\},\\{4\\}\\}$.

######  Lemma 2.1.

Let $G_{i}$ be the branch of $F_{i}$ in the subcomplex $\langle
F_{1},\ldots,F_{i}\rangle$ of $\Delta(G^{c})$. If a subset $H\subset[n]$
belongs to ${\mathcal{A}}^{*}$, then there is $1<i\leq q$ with $H=G_{i}\cap
F_{i}$.

###### Proof.

Let $F_{i_{1}}\cap F_{i_{2}}\cap\cdots\cap F_{i_{j}}\in{\mathcal{A}}$ with
$1\leq i_{1}<i_{2}<\cdots<i_{j}\leq q$ and $q\geq 2$. If none of $F_{i_{k}}$
is a branch $G_{i_{j}}$ of $F_{i_{j}}$, then $F_{i_{1}}\cap
F_{i_{2}}\cap\cdots\cap F_{i_{j}}=F_{i_{1}}\cap F_{i_{2}}\cap\cdots\cap
F_{i_{j}}\cap G_{i_{j}}$ cannot belong to ${\mathcal{A}}$. If $q\geq 3$ and
if, say, $F_{i_{k}}=G_{i_{j}}$, then $F_{i_{1}}\cap F_{i_{2}}\cap\cdots\cap
F_{i_{j}}=F_{i_{1}}\cap\cdots\cap F_{i_{k-1}}\cap F_{i_{k+1}}\cap\cdots\cap
F_{i_{j}}$ cannot belong to ${\mathcal{A}}$. ∎

######  Lemma 2.2.

Let $G_{i}$ be the branch of $F_{i}$ in the subcomplex $\langle
F_{1},\ldots,F_{i}\rangle$ of $\Delta(G^{c})$. Then ${\mathcal{A}}^{*}$
coincides with $\\{G_{i}\cap F_{i}:1\leq i\leq q\\}$ if and only if the
following conditions are satisfied:

  1. (i)

$G_{i}$ is a unique branch of $F_{i}$; and

  2. (ii)

$G_{i}\cap F_{i}\not\subset G_{j}\cap F_{j}$ for $i\neq j$.

###### Proof.

If $G_{i}$ and $G_{i}^{\prime}$ are branches of $F_{i}$ with $G_{i}\neq
G_{i}^{\prime}$, then $G_{i}\cap F_{i}=G_{i}^{\prime}\cap F_{i}$ cannot belong
to ${\mathcal{A}}$. Suppose that $G_{i}\cap F_{i}\subset G_{j}\cap F_{j}$ for
$i\neq j$. Let $i<j$. Then $G_{i}\cap F_{i}=G_{i}\cap F_{i}\cap F_{j}$ cannot
belong to ${\mathcal{A}}$. Let $j<i$. Then $G_{i}\cap F_{i}=G_{i}\cap
F_{i}\cap G_{j}$ cannot belong to ${\mathcal{A}}$ unless $G_{j}=G_{i}$. If
$G_{j}=G_{i}$, then $G_{i}\cap F_{i}=G_{j}\cap F_{i}\cap F_{j}$ cannot belong
to ${\mathcal{A}}$. Thus (i) and (ii) are satisfied if
${\mathcal{A}}^{*}=\\{G_{i}\cap F_{i}:1\leq i\leq q\\}$.

Now, suppose that (i) and (ii) are satisfied. Let $G_{i}\cap
F_{i}=F_{i_{1}}\cap\cdots\cap F_{i_{j}}$ with $1\leq i_{1}<\cdots<i_{j}\leq q$
and $j\geq 2$. Since $F_{i_{1}}\cap\cdots\cap F_{i_{j}}\subset G_{i_{j}}\cap
F_{i_{j}}$, one has $G_{i}\cap F_{i}\subset G_{i_{j}}\cap F_{i_{j}}$. Hence
$i=i_{j}$ by (ii). Thus $G_{i_{j}}\cap F_{i_{j}}=F_{i_{1}}\cap\cdots\cap
F_{i_{j}}$. However, since a branch of $F_{i_{j}}$ is unique by (i), this
cannot happen unless $j=2$ and $F_{i_{1}}=G_{i_{j}}$. Hence $G_{i}\cap
F_{i}\in{\mathcal{A}}^{*}$, as desired. ∎

We are ready to state our result that characterizes when a Cohen–Macaulay
vertex cover ideal has a Scarf resolution. We say that a leaf order
$F_{1},\ldots,F_{q}$ of the facets of the clique complex $\Delta(G^{c})$ is
sensitive if the conditions (i) and (ii) of Lemma 2.2 are satisfied.

######  Theorem 2.3.

Let $G$ be a finite graph on $[n]$ whose complementary graph $G^{c}$ is
chordal. Then the following conditions are equivalent:

  * (i)

the vertex cover ideal $J(G)$ has a Scarf resolution;

  * (ii)

a leaf order of $\Delta(G^{c})$ is sensitive;

  * (iii)

every leaf order of $\Delta(G^{c})$ is sensitive.

###### Proof.

Work with a fixed leaf order $F_{1},\ldots,F_{q}$ of the facets of the clique
complex $\Delta(G^{c})$. The vertex cover ideal $J(G)$ is generated by the
monomials $u_{i}=x_{[n]\setminus F_{i}}$. Furthermore, the least common
multiple of $u_{i}$ and $u_{j}$ is $x_{[n]\setminus(F_{i}\cap F_{j})}$. It was
discussed in the proof of Theorem 2.5 that $\operatorname{proj-dim}J(G)=1$ and
that the first Betti number of $I_{G}$ is equal to $q-1$. Hence $J(G)$ has a
Scarf resolution if and only if the number of monmials of the form
$x_{[n]\setminus(F_{i}\cap F_{j})}$ with $i<j$ which belong to the Scarf
complex of $J(G)$ is $q-1$, in other words, if and only if the number of
subsets of $[n]$ of the form $F_{i}\cap F_{j}$ with $i<j$ which belong to
${\mathcal{A}}^{*}$ is $q-1$, where ${\mathcal{A}}^{*}$ was introduced just
before Lemma 2.1. Now, Lemma 2.1 says that each element of ${\mathcal{A}}^{*}$
is of the form $G_{i}\cap F_{i}$, where $G_{i}$ is a branch of $F_{i}$ in
$\langle F_{1},\ldots,F_{i}\rangle$. Furthermore, Lemma 2.2 guarantees that
$|{\mathcal{A}}^{*}|=q-1$ if and only if the leaf order $F_{1},\ldots,F_{q}$
is sensitive. This completes the proof of (ii) $\Rightarrow$ (i) and (i)
$\Rightarrow$ (iii) of Theorem 2.3. Finally (iii) $\Rightarrow$ (ii) is
obvious. ∎

######  Example 2.4.

(a) Let $G$ be a finite graph for which $G^{c}$ is chordal and has exactly
three facets $F,F^{\prime},F^{\prime\prime}$. Since $G$ has no isolated
vertex, $F\cap F^{\prime}\cap F^{\prime\prime}=\emptyset$. Suppose that
$F,F^{\prime},F^{\prime\prime}$ is a leaf order. Then
$F,F^{\prime},F^{\prime\prime}$ is sensitive if and only if $F\cap
F^{\prime}\neq\emptyset$ and $(F\cup F^{\prime})\cap
F^{\prime\prime}\neq\emptyset$.

(b) Let $G$ be a finite graph on $[n]$ for which $G^{c}$ is a forest, i.e.,
$G^{c}$ has no cycle. Then $J(G)$ has a Scarf resolution if and only if
$G^{c}$ is a path, i.e., the edges of $G^{c}$ are
$\\{1,2\\},\\{2,3\\},\ldots,\\{n-1,n\\}$ by rearranging the vertices of $G$.

A complete bipartite graph of type $(a,b)$, where $a$ and $b$ are positive
integers, is a finite graph on $[a+b]$ whose edges are those $\\{i,j\\}$ with
$1\leq i\leq a$ and $a<j\leq a+b$. The following result was already proved in
[5, Theorem 4.3]. We include the result to showcase yet another application of
the Eagon-Reiner formula [6].

######  Theorem 2.5.

The vertex cover ideal $J(G)$ is Gorenstein, i.e., $S/J(G)$ is Gorenstein, if
and only if $G$ is a complete bipartite graph.

###### Proof.

First, suppose that $G$ is a complete graph of type $(a,b)$ whose vertices are
$x_{1},\ldots,x_{a},y_{1},\ldots,y_{b}$ and whose edges are those
$\\{x_{i},y_{j}\\}$ with $1\leq i\leq a,1\leq j\leq b$. Then
$J(G)=(x_{1}\cdots x_{a},y_{1}\cdots y_{b})$. Thus $S/J(G)$ is a complete
intersection and, in particular, is Gorenstein.

Second, suppose that $S/J(G)$ is Gorenstein. Since $I(G)$ has linear
resolution, one has $\operatorname{reg}I(G)=2$, where $\operatorname{reg}I(G)$
is the regularity of $I(G)$. Hence $\operatorname{proj-dim}J(G)=1$, where
$\operatorname{proj-dim}J(G)$ is the projective dimension of $J(G)$, see [13,
Proposition 8.1.10]. Now, it follows from Hilbert–Burch theorem [13, Lemma
9.2.4] that the first Betti number of $J(G)$ is equal to $s-1$, where $s$ is
the number of monomials belonging to the minimal system of monomial generators
of $J(G)$. Since $J(G)$ is Gorenstein, one has $s-1=1$. Thus $J(G)$ is
minimally generated by exactly two monomials. In other words, there are
exactly two minimal vertex covers $W$ and $W^{\prime}$ of $G$. Since $W\cap
W^{\prime}=\emptyset$, the edges of $G$ are those $\\{i,j\\}$, where $i\in W$
and $j\in W^{\prime}$. Hence $G$ is a complete bipartite graph, as desired. ∎

##  3\. Betti numbers of vertex cover ideals of paths

Let $P_{n}$ denote the path on $[n]$ with
$E(P_{n})=\\{\\{1,2\\},\\{2,3\\},\ldots,\\{n-1,n\\}\\}$. The present section
is devoted to computing the graded Betti number $\beta_{i,i+j}(J(P_{n}))$ of
$J(P_{n})$, where $i=\operatorname{proj-dim}J(P_{n})$ and
$j=\operatorname{reg}J(P_{n})$. The edge ideal $I(P_{n})$ is sequentially
Cohen–Macaulay and the vertex cover ideal $J(P_{n})$ is componentwise linear
following, for instance, [8, 12].

It is known from [11, Theorem 1.2] and [4, Corollary 5.4] that

$\operatorname{reg}I(P_{n})=\left\\{\begin{array}[]{ll}\left\lfloor\dfrac{n}{3}\right\rfloor+1&\text{if
}n\equiv 0,1(\text{mod }3)\\\ &\\\
\left\lfloor\dfrac{n}{3}\right\rfloor+2&\text{if }n\equiv 2(\text{mod
}3),\end{array}\right.$

and

$\operatorname{proj-
dim}I(P_{n})=\left\\{\begin{array}[]{ll}2\left\lfloor\dfrac{n}{3}\right\rfloor-1&\text{if
}n\equiv 0,1(\text{mod }3)\\\ &\\\
2\left\lfloor\dfrac{n}{3}\right\rfloor&\text{if }n\equiv 2(\text{mod
}3).\end{array}\right.$

Let $\Delta_{n}$ denote the clique complex $\Delta(P_{n}^{c})$ of the
complementary graph $P_{n}^{c}$ of $P_{n}$. One has
$\dim\Delta_{n}=[(n-1)/2]$. In general, if $\Delta$ is a simplicial complex
with $\dim\Delta=d-1$, then given an integer $0\leq q<d$, we introduce the
subcomplex $\Delta(q)$ whose facets are the faces $F$ of $\Delta$ with
$|F|=q+1$. Furthermore, we defines $\Delta(q)^{\prime}$ to be the subcomplex
whose facets are those faces $F$ of $\Delta$ with $|F|=q+1$ for which $F$ is
not a facet of $\Delta$.

Let $n=3k$. Then $i=k$ and $j=2k$. It follows from [12, Theorem 2.1] that

$\beta_{i,i+j}(J(P_{n}))=h_{k}(k-1),$

where
$h(\Delta_{n}(k-1))-h(\Delta_{n}(k-1)^{\prime})=(h_{0}(k-1),h_{1}(k-1),\ldots,h_{k}(k-1))$.

######  Lemma 3.1.

A facet $F$ of $\Delta_{3k}$ with $|F|=k$ uniquely exists. Let $F_{0}$ be the
facet of $\Delta_{3k}$ with $|F_{0}|=k$. Then each proper subset $F$ of
$F_{0}$ is a subset of a facet $F^{\prime}$ of $\Delta_{3k}$ with
$|F^{\prime}|>k$.

###### Proof.

The face $F_{0}=\\{2,5,8,\ldots,3k-1\\}$ is a unique facet $F$ of
$\Delta_{3k}$ with $|F|=k$. If $F\subset F_{0}$ with $|F|=k-1$, then clearly
$F$ is a subset of a facet $F^{\prime}$ of $\Delta_{3k}$ with
$|F^{\prime}|>k$. It then follows that each proper subset $F$ of $F_{0}$ is a
subset of a facet $F^{\prime}$ of $\Delta_{3k}$ with $|F^{\prime}|>k$, as
desired. ∎

######  Corollary 3.2.

$\beta_{k,k+2k}(J(P_{3k}))=1$.

###### Proof.

Let
$f(\Delta_{3k}(k-1))=(f_{0},f_{1},\ldots,f_{k-1}),f(\Delta_{3k}(k-1)^{\prime})=(f^{\prime}_{0},f^{\prime}_{1},\ldots,f^{\prime}_{k-1})$
be the $f$-vectors of $\Delta_{3k}(k-1),\Delta_{3k}(k-1)^{\prime}$. Lemma 3.1
says that $f_{i}=f^{\prime}_{i}$ for $0\leq i<k-1$ and
$f_{k-1}=f^{\prime}_{k-1}-1$. Hence by the formula (1) one has $h_{k}(k-1)=1$,
in other words, $\beta_{k,k+2k}(J(P_{3k}))=1$, as desired. ∎

Let $n=3k-1$. Then $i=k$ and $j=2k-1$. It follows from [12, Theorem 2.1] that

$\beta_{i,i+j}(J(P_{n}))=h_{k}(k-1),$

where
$h(\Delta_{n}(k-1))-h(\Delta_{n}(k-1)^{\prime})=(h_{0}(k-1),h_{1}(k-1),\ldots,h_{k}(k-1))$.

######  Lemma 3.3.

The number of facet F of $\Delta_{3k-1}$ with $|F|=k$ is $k+1$. Let
$F_{1},\ldots,F_{k+1}$ be the facets of $\Delta_{3k-1}$ with each $|F_{i}|=k$.
Then the number of faces F of the subcomplex $\langle
F_{1},\ldots,F_{k+1}\rangle$ with $|F|=k-1$ for which there is no facet
$F^{\prime}\in\Delta_{3k-1}$ with $F\subset F^{\prime}$ and $|F^{\prime}|>k$
is $k$. Furthermore, each face $F$ of $\langle F_{1},\ldots,F_{k+1}\rangle$
with $|F|<k-1$ is a subset of a facet $F^{\prime}\in\Delta_{3k-1}$ with
$|F^{\prime}|>k$.

###### Proof.

Let $F=\\{i_{1},i_{2},\ldots,i_{k}\\}$ be a face of $\Delta_{3k-1}$, where
$1\leq i_{1}<i_{2}<\cdots<i_{k}\leq 3k-1$. Let $n_{j}=i_{j}-i_{j-1}$ for
$1<j\leq k$. Then $F$ is a facet of $\Delta_{3k-1}$ if and only if $n_{1}\leq
2,i_{k}\geq 3k-2$ and each $n_{j}\leq 3$. Since $1+1+2(k-1)+k=3k$, the number
of facet F of $\Delta_{3k-1}$ with $|F|=k$ is $k+1$.

Let $F=\\{i_{1},i_{2},\ldots,i_{k-1}\\}$ be a face of $\langle
F_{1},\ldots,F_{k+1}\rangle$, where $1\leq i_{1}<i_{2}<\cdots<i_{k-1}\leq
3k-1$. Let $n_{j}=i_{j}-i_{j-1}$ for $1<j<k$. Then there is no facet
$F^{\prime}\in\Delta_{3k-1}$ with $F\subset F^{\prime}$ and $|F^{\prime}|>k$
if and only if one of the following conditions are satisfied:

  * (i)

$n_{1}=4,i_{k}=3k-2$ and each $n_{j}=3$;

  * (ii)

$n_{1}=2,i_{k}=3k-4$ and each $n_{j}=3$;

  * (iii)

$n_{1}=2,i_{k}=3k-2$ and there is $j_{0}$ with $n_{j_{0}}=5$ and each
$n_{j}=3$ for $j\neq j_{0}$.

Thus the number of faces $F$ of $\langle F_{1},\ldots,F_{k+1}\rangle$ with
$|F|=k-1$ for which there is no facet $F^{\prime}\in\Delta_{3k-1}$ with
$F\subset F^{\prime}$ and $|F^{\prime}|>k$ is $k$.

If $F$ is a face of $\langle F_{1},\ldots,F_{k+1}\rangle$ with $|F|=k-2$, then
$F$ is a subset of a facet $F^{\prime}\in\Delta_{3k-1}$ with $|F^{\prime}|>k$.
Thus each face $F$ of $\langle F_{1},\ldots,F_{k+1}\rangle$ with $|F|<k-1$ is
a subset of a facet $F^{\prime}\in\Delta_{3k-1}$ with $|F^{\prime}|>k$. ∎

######  Corollary 3.4.

$\beta_{k,k+(2k-1)}(J(P_{3k-1}))=1$.

###### Proof.

Let
$f(\Delta_{3k-1}(k-1))=(f_{0},f_{1},\ldots,f_{k-1}),f(\Delta_{3k-1}(k-1)^{\prime})=(f^{\prime}_{0},f^{\prime}_{1},\ldots,f^{\prime}_{k-1})$
be the $f$-vectors of $\Delta_{3k-1}(k-1),\Delta_{3k-1}(k-1)^{\prime}$. It
follows from Lemma 3.3 that $f_{i}=f^{\prime}_{i}$ for $0\leq i<k-2$ and that

$f_{k-1}-f^{\prime}_{k-1}=k+1,\,\,\,\,\,f_{k-2}-f^{\prime}_{k-2}=k.$

Hence by the formula (1) one has $h_{k}(k-1)=1$, in other words,
$\beta_{k,k+2k-1}(J(P_{3k-1}))=1$, as desired. ∎

Let $n=3k+1$. Then $i=k$ and $j=2k$. It follows from [12, Theorem 2.1] that

$\beta_{i,i+j}(J(P_{n}))=h_{k}(k),$

where
$h(\Delta_{n}(k))-h(\Delta_{n}(k)^{\prime})=(h_{0}(k-1),h_{1}(k-1),\ldots,h_{k+1}(k))$.

######  Lemma 3.5.

(1) Let ${\mathcal{F}}_{k}$ denote the set of those faces $F\in\Delta_{3k+1}$
with $|F|=k$ for which $F$ is a subset of a facet $F^{\prime}\in\Delta_{3k+1}$
with $|F^{\prime}|=k+1$, but not a subset of a facet
$F^{\prime\prime}\in\Delta_{3k+1}$ with $|F^{\prime\prime}|>k+1$. Then
$|{\mathcal{F}}_{k}|=(k+1)^{2}$.

(2) Let ${\mathcal{F}}_{k-1}$ denote the set of those faces
$F\in\Delta_{3k+1}$ with $|F|=k-1$ for which $F$ is a subset of a facet
$F^{\prime}\in\Delta_{3k+1}$ with $|F^{\prime}|=k+1$, but not a subset of a
facet $F^{\prime\prime}\in\Delta_{3k+1}$ with $|F^{\prime\prime}|>k+1$. Then
$|{\mathcal{F}}_{k-1}|=k(k+1)/2$.

(3) Each face $F$ of $\Delta_{3k+1}$ with $|F|=k-2$ is a subset of a facet
$F^{\prime}\in\Delta_{3k+1}$ with $|F^{\prime}|>k+1$.

###### Proof.

(1) With ignoring the symmetric structure, each face belonging to
${\mathcal{F}}$ can be regarded to be one of the following types:

  * (type $a_{1}^{(1)}$) $\\{3,6,9,\ldots,3k\\}$

  * (type $a_{1}^{(2)}$) $\\{4,7,10,\ldots,3k-2,3k\\}$

  * (type $a_{1}^{(3)}$) $\\{4,7,10,\ldots,3k-2,3k+1\\}$

  * (type $a_{2}^{(1)}$) $\\{1,6,9,\ldots,3k\\}$

  * (type $a_{2}^{(2)}$) $\\{2,6,9,\ldots,3k\\}$

  * (type $a_{2}^{(3)}$) $\\{2,7,10,\ldots,3k+1\\}$

  * (type $a_{2}^{(4)}$) $\\{2,7,10,\ldots,3k-2,3k\\}$

The number of faces of types $a_{1}^{(1)},a_{1}^{(2)},a_{1}^{(3)}$ is $2(k+1)$
and that of $a_{2}^{(1)},a_{2}^{(2)},a_{2}^{(3)},a_{2}^{(4)}$ is $(k+1)(k-1)$.
Thus $|{\mathcal{F}}_{k}|=2(k+1)+(k+1)(k-1)=(k+1)^{2}$.

(2) With ignoring the symmetric structure, each face belonging to
${\mathcal{F}}^{\prime}$ can be regarded to be one of the following types:

  * (type $a_{1}^{(1)}$) $\\{6,9,\ldots,3k\\}$

  * (type $a_{1}^{(2)}$) $\\{2,9,12,\ldots,3k\\}$

  * (type $a_{2}^{(1)}$) $\\{4,7,10,\ldots,3k-2\\}$

  * (type $a_{2}^{(2)}$) $\\{4,9,12,\ldots,3k\\}$

  * (type $a_{2}^{(3)}$) $\\{2,7,12,15,18,\ldots,3k\\}$

The numbers of faces of types $a_{1}^{(1)},\ldots,a_{2}^{(3)}$ are
$2,k-2,1,2(k-2),\binom{k-2}{2}$. Thus $|{\mathcal{F}}_{k}|=k(k+1)/2$.

(3) Since $(3k+1)-(k-2)-2(k-2)=7>6$, each face $F$ of $\Delta_{3k+1}(k)$ with
$|F|=k-2$ is a subset of a facet $F^{\prime}$ with $|F^{\prime}|>k+1$. ∎

######  Corollary 3.6.

$\beta_{k,k+2k}(J(P_{3k+1}))=k+1$.

###### Proof.

Let
$f(\Delta_{3k+1}(k))=(f_{0},f_{1},\ldots,f_{k}),f(\Delta_{3k+1}(k-1)^{\prime})=(f^{\prime}_{0},f^{\prime}_{1},\ldots,f^{\prime}_{k})$
be the $f$-vectors of $\Delta_{3k+1}(k),\Delta_{3k+1}(k)^{\prime}$. It follows
from Lemma 3.5 that $f_{i}=f^{\prime}_{i}$ for $0\leq i<k-3$ and that

$f_{k-1}-f^{\prime}_{k-1}=(k+1)^{2},\,\,\,\,\,f_{k-2}-f^{\prime}_{k-2}=k(k+1)/2.$

Hence by the formula (2) one has $h_{k}(k-1)=(k+1)^{2}-2(k(k+1)/2)=k+1$, in
other words, $\beta_{k,k+2k-1}(J(P_{3k+1}))=k+1$, as desired. ∎

Summarizing the above discussions yields the following

######  Theorem 3.7.

Let $P_{n}$ denote the path on $[n]$ and $J(P_{n})$ its vertex cover ideal.
Let $i=\operatorname{proj-dim}{J(P_{n})}$ and
$j=\operatorname{reg}{J(P_{n})}$. Then

  * (i)

If $n=3k$, then $i=k,j=2k$ and $\beta_{k,k+2k}(J_{P_{3k}})=1$;

  * (ii)

If $n=3k-1$, then $i=k,j=2k-1$ and $\beta_{k,k+(2k-1)}(J_{P_{3k-1}})=1$;

  * (iii)

If $n=3k+1$, then $i=k,j=2k$ and $\beta_{k,k+2k}(J_{P_{3k+1}})=k+1$.

On the other hand, a topological approach to the computation for
$\beta_{k,3k}(J_{P_{3k}})$ and $\beta_{k,3k-1}(J_{P_{3k-1}})$ is possible.
Observe that in both of these cases, when $n=3k$ or $n=3k-1$, we are to
compute the graded Betti number $\beta_{k,n}(J(P_{n}))$. It then follows from
[13, Corollary 8.1.4] that

(3)
$\displaystyle\beta_{k,n}(J(P_{n}))=\dim_{K}\widetilde{H}_{k-1}(\Delta_{n};K).$

######  Lemma 3.8.

For any integers $n$ and $i$, one has

$\widetilde{H}_{i}(\Delta_{n})\simeq\widetilde{H}_{i-1}(\Delta_{n-3}).$

###### Proof.

Observe that $\operatorname{del}_{\Delta_{n}}(n-1)$ is a cone with vertex $n$.
Thus, for any $i\geq 0$,

$\widetilde{H}_{i}(\operatorname{del}_{\Delta_{n}}(n-1))=0.$

Let $\Gamma=\text{st}_{\Delta_{n}}(n-1)$ be the closed star of $(n-1)$ in
$\Delta_{n}$. Then, $\Gamma$ has no homology. Also, it is easy to see that
$\Delta_{n}-\Gamma$ has the same homotopy type as that of
$\operatorname{del}_{\Delta_{n}}(n-1)$. Clearly,

$(\Delta_{n}-\Gamma)\cap\Gamma=\operatorname{link}_{\Delta_{n}}(n-1).$

The desired equality then follows from a standard use of Mayer–Vietoris
sequence, applied to $\Delta_{n}-\Gamma$ and $\Gamma$. ∎

######  Corollary 3.9.

$\beta_{k,k+2k}(J(P_{3k}))=1=\beta_{k,k+2k-1}(J(P_{3k-1})).$

###### Proof.

It follows from (3) and Lemma 3.8 that

$\beta_{k,k+2k}(J(P_{3k}))=\dim_{K}\widetilde{H}_{k-1}(\Delta_{3k})=\dim_{K}\widetilde{H}_{0}(\Delta_{3})=1,$

and

$\beta_{k,k+2k-1}(J(P_{3k-1}))=\dim_{K}\widetilde{H}_{k-1}(\Delta_{3k-1})=\dim_{K}\widetilde{H}_{0}(\Delta_{2})=1,$

as desired. ∎

##  4\. Betti numbers of vertex cover ideals of cycles

Let $C_{n}$ denote the cycle on $[n]$ with
$E(C_{n})=\\{\\{1,2\\},\\{2,3\\},\ldots,\\{n-1,n\\},\\{1,n\\}\\}$. The present
section is devoted to computing the graded Betti number
$\beta_{i,i+j}(J(C_{n}))$ of $J(C_{n})$, where $i=\operatorname{proj-
dim}J(C_{n})$ and $j=\operatorname{reg}J(C_{n})$. For the remaining of this
paper, without any possibly confusion with the notation used in the last
section, let $\Delta_{n}$ denote the clique complex $\Delta(C_{n}^{c})$ of the
complementary graph $C_{n}^{c}$ of $C_{n}$. It follows from [13, Corollary
8.1.4] that

(4)
$\displaystyle\beta_{i,i+j}(J(C_{n}))=\sum_{F\in\Delta_{n},\,|F|=n-(i+j)}\dim_{K}\widetilde{H}_{i-1}(\operatorname{link}_{\Delta_{n}}F;K).$

It is known from [1, Corollary 5.5] that

$\operatorname{reg}I(C_{n})=\left\\{\begin{array}[]{ll}\left\lfloor\dfrac{n}{3}\right\rfloor+1&\text{if
}n\equiv 0,1(\text{mod }3)\\\ &\\\
\left\lfloor\dfrac{n}{3}\right\rfloor+2&\text{if }n\equiv 2(\text{mod
}3),\end{array}\right.$

and

$\operatorname{proj-
dim}I(C_{n})=\left\\{\begin{array}[]{ll}2\left\lfloor\dfrac{n}{3}\right\rfloor-1&\text{if
}n\equiv 0(\text{mod }3)\\\ &\\\
2\left\lfloor\dfrac{n}{3}\right\rfloor&\text{if }n\equiv 1,2(\text{mod
}3).\end{array}\right.$

Thus by using [13, Proposition 8.1.10], one has

$\operatorname{proj-dim}J(C_{3k})=k,\,\,\operatorname{proj-
dim}J(C_{3k+1})=k,\,\,\,\operatorname{proj-dim}J(C_{3k+2})=k+1,$

and

$\operatorname{reg}J(C_{3k})=2k,\,\,\operatorname{reg}J(C_{3k+1})=2k+1,\,\,\,\operatorname{reg}J(C_{3k+2})=2k+1.$

Our target is to compute the graded Betti numbers

$\beta_{k,3k}(J(C_{3k})),\,\,\beta_{k,3k+1}(J(C_{3k+1})),\,\,\beta_{k+1,3k+2}(J(C_{3k+2})).$

It follows from (4) that

$\beta_{k,3k}(J(C_{3k}))=\dim_{K}\widetilde{H}_{k-1}(\Delta_{3k};K),$
$\beta_{k,3k+1}(J(C_{3k+1}))=\dim_{K}\widetilde{H}_{k-1}(\Delta_{3k+1};K),$
$\beta_{k+1,3k+2}(J(C_{3k+2}))=\dim_{K}\widetilde{H}_{k}(\Delta_{3k+2};K).$

By virtue of the formula on simplicial homology (as in Lemma 3.8)

$\widetilde{H}_{q}(\Delta_{n};K)\cong\widetilde{H}_{q-1}(\Delta_{n-3};K),$

it follows that

$\beta_{k,3k}(J(C_{3k}))=\dim_{K}\widetilde{H}_{k-1}(\Delta_{3k};K)=\dim_{K}\widetilde{H}_{0}(\Delta_{3};K)=2,$
$\beta_{k,3k+1}(J(C_{3k+1}))=\dim_{K}\widetilde{H}_{k-1}(\Delta_{3k+1};K)=\dim_{K}\widetilde{H}_{0}(\Delta_{4};K)=1,$

and

$\beta_{k+1,3k+2}(J(C_{3k+2}))=\dim_{K}\widetilde{H}_{k}(\Delta_{3k+2};K)=\dim_{K}\widetilde{H}_{1}(\Delta_{5};K)=1.$

Again, summarizing this discussion results in the following theorem.

######  Theorem 4.1.

Let $C_{n}$ denote the cycle on $[n]$ and $J(C_{n})$ its vertex cover ideal.
Let $i=\operatorname{proj-dim}{J(C_{n})}$ and
$j=\operatorname{reg}{J(C_{n})}$. Then

  * (i)

If $n=3k$, then $i=k,j=2k$ and $\beta_{k,k+2k}(J(C_{3k}))=2$;

  * (ii)

If $n=3k+1$, then $i=k,j=2k+1$ and $\beta_{k,k+(2k+1)}(J(C_{3k-1}))=1$;

  * (iii)

If $n=3k+2$, then $i=k+1,j=2k+1$ and
$\beta_{k+1,(k+1)+(2k+1)}(J(C_{3k+1}))=1$.

## References

  * [1] A. Alilooee and S. Faridi, On the resolution of path ideals of cycles, Comm. Alg. 43 (2015), 5413–5433.
  * [2] A. Banerjee, S. Kara Beyarslan, and H.T. Hà, Regularity of edge ideals and their powers Springer Proc. Math. Stat., 277 Springer, Cham, 2019, 17–52.
  * [3] D. Bayer, I. Peeva, B. Sturmfels, Monomial resolutions, Math. Res. Lett. 5 (1998), no. 1-2, 31–46.
  * [4] R. Bouchat, H.T. Hà, and A. O’Keefe, Path ideals of rooted trees and their graded Betti numbers. J. Combin. Theory Ser. A 118 (2011), no.8, 2411–2425.
  * [5] A. Constantinescu, M.R. Pournaki, S.A. Seyed Fakhari, N. Terai, and S. Yassemi, Cohen-Macaulayness and limit behavior of depth for powers of cover ideals, Comm. Alg. 43 (2015), 143–157.
  * [6] J. A. Eagon and V. Reiner, Resolutions of Stanley–Reisner rings and Alexander duality, J. Pure Appl. Algebra 130 (1998), 265–275.
  * [7] S. Faridi, T. Hà, T. Hibi and S. Morey, Scarf complexes of graphs and their powers, arXiv:2403.05439.
  * [8] C. Francisco and A. Van Tuyl, Sequentially Cohen–Macaulay edge ideals, Proc. Amer. Math. Soc. 135 (2007), 2327–2337.
  * [9] R. Fröberg, On Stanley–Reisner rings with linear resolution, in “Topics in Algebra,” Banach Center Publications, 26 Part 2, 1990, pp. 57–70.
  * [10] H.T. Hà and A. Van Tuyl, Powers of componentwise linear ideals: the Herzog-Hibi-Ohsugi conjecture and related problems. Res. Math. Sci. 9 (2022), no. 2, Paper No. 22, 26 pp.
  * [11] J. He and A. Van Tuyl, Algebraic properties of the path ideal of a tree. Comm. Algebra 38 (2010), no.5, 1725–1742.
  * [12] J. Herzog and T. Hibi, Componentwise linear ideals, Nagoya Math. J. 153 (1999), 141–153.
  * [13] J. Herzog and T. Hibi, “Monomial Ideals,” GTM 260, Springer, Berlin, 2011, xvi + 321 pp.
  * [14] J. Herzog, T. Hibi and H. Ohsugi, Powers of componentwise linear ideals. Combinatorial aspects of commutative algebra and algebraic geometry, 49–61, Abel Symp., 6, Springer, Berlin, 2011.
  * [15] E. Nevo and I. Peeva, $C_{4}$-free edge ideals, J. Algebraic Combin. 37 (2013), no. 2, 243–248.