# Matching powers of monomial ideals and edge ideals of weighted oriented
graphs

Nursel Erey, Antonino Ficarra  Nursel Erey, Gebze Technical University,
Department of Mathematics, 41400 Gebze, Kocaeli, Turkey<EMAIL_ADDRESS>Antonino Ficarra, Department of mathematics and computer sciences, physics and
earth sciences, University of Messina, Viale Ferdinando Stagno d’Alcontres 31,
98166 Messina, Italy<EMAIL_ADDRESS>
###### Abstract.

We introduce the concept of matching powers of monomial ideals. Let $I$ be a
monomial ideal of $S=K[x_{1},\dots,x_{n}]$, with $K$ a field. The $k$th
matching power of $I$ is the monomial ideal $I^{[k]}$ generated by the
products $u_{1}\cdots u_{k}$ where $u_{1},\dots,u_{k}$ is a monomial regular
sequence contained in $I$. This concept naturally generalizes that of
squarefree powers of squarefree monomial ideals. We study depth and regularity
functions of matching powers of monomial ideals and edge ideals of weighted
oriented graphs. We show that the last nonvanishing power of a quadratic
monomial ideal is always polymatroidal and thus has a linear resolution. When
$I$ is a non-quadratic edge ideal of a weighted oriented forest, we
characterize when $I^{[k]}$ has a linear resolution.

###### Key words and phrases:

Edge Ideals, Linear Resolutions, Matching Powers, Polymatroids, Weighted
Graphs

###### 2020 Mathematics Subject Classification:

Primary 13F20; Secondary 05E40

## Introduction

Let $S=K[x_{1},\dots,x_{n}]$ be the polynomial ring over a field $K$. Recall
that the edge ideal of a finite simple graph $G$ with vertices
$x_{1},\dots,x_{n}$ is generated by all the monomials $x_{i}x_{j}$ such that
$\\{x_{i},x_{j}\\}$ is an edge of $G$. The study of minimal free resolutions
of edge ideals and their powers produced a great deal of interaction between
combinatorics and commutative algebra. One of the most natural problems in
this regard is to understand when those ideals, or more generally monomial
ideals, have linear resolutions. Although edge ideals with linear resolutions
are combinatorially characterized by a famous result of Fröberg [16], it is
unknown in general when powers of edge ideals have linear resolutions. Herzog,
Hibi and Zheng [21] showed that if an edge ideal has a linear resolution, then
so does every power of it. It is their result that served as a starting point
for the close examination of linear resolutions of powers of edge ideals by
many researchers, resulting in several interesting results and conjectures.

For any squarefree monomial ideal $I$ of $S$, the $k$th squarefree power of
$I$, denoted by $I^{[k]}$ is the monomial ideal generated by all squarefree
monomials in $I^{k}$. Recently, squarefree powers of edge ideals were studied
in [4, 7, 8, 9, 10, 14, 27, 28]. Determining linearity of minimal free
resolutions of squarefree powers or finding their invariants is as challenging
as those of ordinary powers although squarefree and ordinary powers have quite
different behavior. In the case that $I$ is considered as edge ideal of a
hypergraph $\mathcal{H}$, the minimal monomial generators of $I^{[k]}$
correspond to matchings of $\mathcal{H}$ of size $k$, which makes
combinatorial aspect of squarefree powers interesting as well.

This paper aims at presenting a wider framework for the study of squarefree
powers by introducing a more general concept which we call matching powers. If
$I$ is a monomial ideal of $S$, then the _$k^{\text{th}}$ matching power_
$I^{[k]}$ of $I$ is generated by the products $u_{1}\cdots u_{k}$ where
$u_{1},\dots,u_{k}$ is a monomial regular sequence contained in $I$, or
equivalently, $u_{1},\dots,u_{k}$ is a sequence of monomials with pairwise
disjoint support. Indeed, if $I$ is a squarefree monomial ideal, then the
$k$th squarefree power of $I$ is the same as the $k$th matching power of $I$.
With this new concept, since we are no longer restricted to squarefree
monomial ideals, we can consider not only edge ideals of simple graphs but
also edge ideals of weighted oriented graphs.

We now discuss how the paper is organized. In Section 1, we summarize basic
facts of the theory of matching powers. We define the normalized depth
function $g_{I}$ of a monomial ideal $I$ in Definition 1.5. This function
generalizes the normalized depth function introduced in [10] for squarefree
monomial ideals. It was conjectured in [10] that $g_{I}$ is a non-increasing
function for any squarefree monomial ideal. We show in Proposition 1.8 that
this conjecture can be equivalently stated for monomial ideals. Hence, the
normalized depth functions of squarefree monomial ideals comprise all
normalized depth functions. In Theorem 1.10 we show that if $I$ is a quadratic
monomial ideal, then the highest nonvanishing matching power of $I$ (namely
$I^{[\nu(I)]}$, where $\nu(I)$ is the monomial grade of $I$) is polymatroidal.
Since polymatroidal ideals have linear quotients, Theorem 1.10 provides a
stronger result than [4, Theorem 4.1].

In Section 2, we turn our attention to edge ideals of weighted oriented
graphs. We make comparisons between homological invariants of matching powers
$I(\mathcal{D})^{[k]}$ and $I(G)^{[k]}$, where $G$ is the underlying graph of
a weighted oriented graph $\mathcal{D}$. We provide a lower bound for the
regularity of $I(\mathcal{D})^{[k]}$ when $k$ does not exceed the induced
matching number of the underlying graph of $\mathcal{D}$.

In Section 3, we are interested in linearly related matching powers. The main
result of this section is Theorem 3.6 which characterizes when
$I(\mathcal{D})^{[k]}$ has a linear resolution or is linearly related provided
that the underlying graph $G$ of $\mathcal{D}$ has the property that every
subgraph of $G$ has at most one perfect matching and $I(\mathcal{D})\neq
I(G)$. In particular, this result combined with [8, Theorem 41] gives a
complete classification of weighted oriented forests $\mathcal{D}$ such that
$I(\mathcal{D})^{[k]}$ has a linear resolution. The last section is devoted to
demonstrate how one can recursively construct those weighted oriented forests
described in Theorem 3.6.

##  1\. Matching Powers

Let $S=K[x_{1},\dots,x_{n}]$ be the standard graded polynomial ring with
coefficients in a field $K$. Recall that $f_{1},\dots,f_{m}$ is a regular
sequence (on $S$) if $f_{i}$ is a non zero–divisor on
$S/(f_{1},\dots,f_{i-1})$ for $i=1,\dots,m$.

Let $I\subset S$ be a monomial ideal. We denote by $G(I)$ its unique minimal
monomial generating set. Whereas, by $M(I)$ we denote the set of monomials
belonging to $I$.

The $k$th matching power of $I\subset S$ is the monomial ideal defined as

$I^{[k]}\ =\ (f_{1}\cdots f_{k}\ :\ f_{i}\in M(I),f_{1},\dots,f_{k}\
\textit{is a regular sequence}).$

If $u$ is a monomial, we set $\operatorname{supp}(u)=\\{i:x_{i}\
\textup{divides}\ u\\}$. It is easy to check when a sequence of monomials is a
(monomial) regular sequence. Indeed,

######  Lemma 1.1.

Let $v_{1},\dots,v_{r}$ be monomials of $S$. Then $v_{1},\dots,v_{r}$ is a
regular sequence (for any ordering) if and only if
$\operatorname{supp}(v_{i})\cap\operatorname{supp}(v_{j})=\emptyset$ for all
$1\leq i<j\leq k$.

Let $I\subset S$ be a monomial ideal. The set
$\operatorname{supp}(I)=\bigcup_{u\in G(I)}\operatorname{supp}(u)$ is called
the support of $I$. We say that $I$ is fully supported if
$\operatorname{supp}(I)=\\{1,2,\dots,n\\}$. From now, we tacitly assume that
all monomial ideals we consider are fully supported.

We denote by $\nu(I)$ the monomial grade of $I$, that is, the maximal length
of a monomial regular sequence contained in $I$. In the next proposition, we
collect some basic facts about matching powers.

######  Proposition 1.2.

Let $I\subset S$ be a monomial ideal. Then, the following hold.

  1. (a)

$I^{[k]}=(u_{1}\cdots u_{k}\ :\ u_{i}\in
G(I),\operatorname{supp}(u_{i})\cap\operatorname{supp}(u_{j})=\emptyset,1\leq
i<j\leq k)$.

  2. (b)

$I^{[k]}\neq 0$ if and only if $1\leq k\leq\nu(I)$.

  3. (c)

$I^{[k]}$ is a monomial ideal.

###### Proof.

Statements (b) and (c) follow from statement (a). To prove the latter
assertion, we set $J=(u_{1}\cdots u_{k}:u_{i}\in
G(I),\operatorname{supp}(u_{i})\cap\operatorname{supp}(u_{j})=\emptyset,1\leq
i<j\leq k)$ and show that $J=I^{[k]}$. By Lemma 1.1, it is clear that
$J\subseteq I^{[k]}$.

Conversely, let $v_{1},\dots,v_{k}$ be a monomial regular sequence contained
in $I$. Then $v_{1}\cdots v_{k}\in I^{[k]}$ and by Lemma 1.1, we have
$\operatorname{supp}(v_{i})\cap\operatorname{supp}(v_{j})=\emptyset$ for
$i\neq j$. Since $I$ is a monomial ideal, $v_{i}=f_{i}u_{i}$ where $f_{i}$ is
a monomial of $S$ and $u_{i}\in G(I)$, for all $i$. Hence,
$\operatorname{supp}(u_{i})\cap\operatorname{supp}(u_{j})=\emptyset$ for all
$i\neq j$, as well. Thus $u_{1}\cdots u_{k}\in J$ divides $v_{1}\cdots v_{k}$,
and this implies that $I^{[k]}\subseteq J$.

######  Example 1.3.

  1. (i)

Suppose that $I$ is a squarefree monomial ideal. Then, a product $u_{1}\cdots
u_{k}$ with $u_{i}\in G(I)$ is in $I^{[k]}$ if and only if $u_{1}\cdots u_{k}$
is squarefree. Thus, in this case $I^{[k]}$ is just the usual $k$th squarefree
power of $I$ introduced in [4].

  2. (ii)

Let $I$ be a complete intersection monomial ideal generated by
$u_{1},\dots,u_{m}$. Then $I^{[k]}=(u_{i_{1}}\cdots u_{i_{k}}:1\leq
i_{1}<\dots<i_{k}\leq m)$ and $\nu(I)=m$.

  3. (iii)

Let $(x_{1}^{2},\,x_{2}^{2},\,x_{3}^{2},\,x_{3}x_{4},\,x_{5}^{5})$. Then
$\nu(I)=4$ and

$\displaystyle\phantom{aaaaa}I^{[2]}\ $ $\displaystyle=\
(x_{1}^{2}x_{2}^{2},\,x_{1}^{2}x_{3}^{2},\,x_{1}^{2}x_{3}x_{4},\,x_{1}^{2}x_{5}^{5},\,x_{2}^{2}x_{3}^{2},\,x_{2}^{2}x_{3}x_{4},\,x_{2}^{2}x_{5}^{5},\,x_{3}^{2}x_{5}^{5},\,x_{3}x_{4}x_{5}^{5})$
$\displaystyle I^{[3]}\ $ $\displaystyle=\
(x_{1}^{2}x_{2}^{2}x_{3}^{2},\,x_{1}^{2}x_{2}^{2}x_{3}x_{4},\,x_{1}^{2}x_{2}^{2}x_{5}^{5},\,x_{1}^{2}x_{3}^{2}x_{5}^{5}\,,x_{1}^{2}x_{3}x_{4}x_{5}^{5},\,x_{2}^{2}x_{3}^{2}x_{5}^{5},\,x_{2}^{2}x_{3}x_{4}x_{5}^{5}),$
$\displaystyle I^{[4]}\ $ $\displaystyle=\
(x_{1}^{2}x_{2}^{2}x_{3}^{2}x_{5}^{5},\,x_{1}^{2}x_{2}^{2}x_{3}x_{4}x_{5}^{5}).$

### Normalized depth function

For a monomial $u\in S$, $u\neq 1$, the $x_{i}$-degree of $u$ is defined as
the integer

$\deg_{x_{i}}(u)\ =\ \max\\{j\geq 0:x_{i}^{j}\ \textup{divides}\ u\\}.$

Let $I\subset S$ be a monomial ideal. The initial degree of $I$, denoted by
$\textup{indeg}(I)$ is the smallest degree of a monomial belonging to $I$.
Following [11], we define the bounding multidegree of $I$ to be the vector

${\bf deg}(I)\ =\ (\deg_{x_{1}}(I),\dots,\deg_{x_{n}}(I)),$

with

$\deg_{x_{i}}(I)\ =\ \max_{u\in G(I)}\deg_{x_{i}}(u),\ \ \textup{for all}\ \ \
1\leq i\leq n.$

We provide a lower bound for the depth of $S/I^{[k]}$ in terms of the initial
degree of $I^{[k]}$ and the bounding multidegree of $I$ as follows:

######  Theorem 1.4.

Let $I\subset S$ be a monomial ideal. Then, for all $1\leq k\leq\nu(I)$, we
have

$\operatorname{depth}(S/I^{[k]})\ \geq\ \textup{indeg}(I^{[k]})-1+(n-|{\bf
deg}(I)|).$

###### Proof.

We divide the proof in three steps.
(Step 1). Let $J\subset S$ be a monomial ideal. We claim that

$\operatorname{pd}(J)\leq|{\bf deg}(J)|-\textup{indeg}(J).$

To prove the assertion, we use the Taylor resolution. Let $\beta_{i,j}(J)$ be
a non–zero graded Betti number with $i=\operatorname{pd}(J)$. Then
$j\geq\textup{indeg}(J)+\operatorname{pd}(J)$. It follows from the Taylor
resolution that the highest shift in the minimal resolution of $J$ is at most
$|{\bf deg}(J)|$, see [11, Theorem 1.3]. Thus, $|{\bf deg}(J)|\geq j$.
Altogether, we obtain $|{\bf deg}(J)|\geq
j\geq\textup{indeg}(J)+\operatorname{pd}(J)$ and the assertion follows.
(Step 2). We claim that $|{\bf deg}(I^{[k]})|\leq|{\bf deg}(I)|$ for all
$1\leq k\leq\nu(I)$. Indeed, we even show that
$\deg_{x_{\ell}}(I^{[k]})\leq\deg_{x_{\ell}}(I)$ for all $\ell$. A set of
generators of $I^{[k]}$ is

$\Omega\ =\ \\{u_{1}\cdots u_{k}\ :\ u_{i}\in
G(I),\operatorname{supp}(u_{i})\cap\operatorname{supp}(u_{j})=\emptyset,1\leq
i<j\leq k\\}.$

Thus, $G(I^{[k]})$ is a subset of $\Omega$. Hence, if $v\in G(I^{[k]})$, then
$v=u_{1}\cdots u_{k}\in\Omega$. Let $x_{\ell}$ be a variable dividing $v$,
then $x_{\ell}$ divides at most one monomial $u_{i}$, say $u_{i_{\ell}}$.
Therefore,
$\deg_{x_{\ell}}(v)\leq\deg_{x_{\ell}}(u_{i_{\ell}})\leq\deg_{x_{\ell}}(I)$
and the assertion follows.
(Step 3). By Steps 1 and 2 we have

$\operatorname{pd}(S/I^{[k]})\ \leq\ |{\bf
deg}(I^{[k]})|-\textup{indeg}(I^{[k]})+1\ \leq\ |{\bf
deg}(I)|-\textup{indeg}(I^{[k]})+1.$

The asserted inequality follows from the Auslander–Buchsbaum formula.

As a consequence of Theorem 1.4, we can give the next definition:

######  Definition 1.5.

Let $I\subset S$ be a monomial ideal. For all $1\leq k\leq\nu(I)$, we set

$g_{I}(k)\ =\ \operatorname{depth}(S/I^{[k]})+|{\bf
deg}(I)|-n-(\textup{indeg}(I^{[k]})-1),$

and call $g_{I}$ the normalized depth function of $I$.

By Theorem 1.4 we have $g_{I}(k)\geq 0$ for all $1\leq k\leq\nu(I)$.

If $I\subset S$ is a squarefree monomial ideal, then ${\bf deg}(I)={\bf
1}=(1,\dots,1)$ and so

$g_{I}(k)=\operatorname{depth}(S/I^{[k]})-(\textup{indeg}(I^{[k]})-1)$

is the normalized depth function of $I$ introduced in [10]. It is expected
that the following is true.

######  Conjecture 1.6.

(Erey–Herzog–Hibi–Madani [10]). Let $I\subset S$ be a squarefree monomial
ideal. Then $g_{I}$ is a nonincreasing function.

Since the concept of the normalized depth function is extended from squarefree
monomial ideals to all monomial ideals, it is natural to expect that the
following more general statement is true.

######  Conjecture 1.7.

Let $I\subset S$ be a monomial ideal. Then $g_{I}$ is nonincreasing.

It is clear that Conjecture 1.7 implies Conjecture 1.6. Surprisingly, we show
that the converse also holds.

######  Proposition 1.8.

Conjectures 1.6 and 1.7 are equivalent.

To prove this result, we use the polarization technique. Let
$u=x_{1}^{b_{1}}\cdots x_{n}^{b_{n}}\in S$ be a monomial. Then, the
polarization of $u$ is the monomial

$u^{\wp}=\prod_{i=1}^{n}(\prod_{j=1}^{b_{i}}x_{i,j})=\prod_{\begin{subarray}{c}1\leq
i\leq n\\\ b_{i}>0\end{subarray}}x_{i,1}x_{i,2}\cdots x_{i,b_{i}}$

in the polynomial ring $K[x_{i,j}:1\leq i\leq n,1\leq j\leq b_{i}]$.

Let $I\subset S$ be a monomial ideal. Then, the polarization of $I$ is defined
to be the squarefree monomial ideal $I^{\wp}$ of $S^{\wp}=K[x_{i,j}:1\leq
i\leq n,1\leq j\leq\deg_{x_{i}}(I)]$ with minimal generating set
$G(I^{\wp})=\\{u^{\wp}:u\in G(I)\\}$.

###### Proof of Proposition 1.8..

Suppose that Conjecture 1.6 holds, and let $I\subset S$ be a monomial ideal.
We claim that

$(I^{[k]})^{\wp}\ =\ (I^{\wp})^{[k]},\ \ \textup{for all}\ \ 1\leq
k\leq\nu(I).$ (1)

Indeed, let $v_{1},\dots,v_{k}\in G(I^{\wp})$ with
$\operatorname{supp}(v_{i})\cap\operatorname{supp}(v_{j})=\emptyset$ for all
$1\leq i<j\leq k$. Then $v_{1}\cdots v_{k}\in(I^{\wp})^{[k]}$. Since
$G(I^{\wp})=\\{u^{\wp}:u\in G(I)\\}$, we see that $v_{i}=u_{i}^{\wp}$ with
$u_{i}\in G(I)$ for all $i$. It is clear that the condition
$\operatorname{supp}(u_{i}^{\wp})\cap\operatorname{supp}(u_{j}^{\wp})=\emptyset$
is verified if and only if
$\operatorname{supp}(u_{i})\cap\operatorname{supp}(u_{j})=\emptyset$. By this
discussion, we have

$\displaystyle(I^{\wp})^{[k]}\ $ $\displaystyle=\ (u_{1}^{\wp}\cdots
u_{k}^{\wp}:u_{i}^{\wp}\in
G(I^{\wp}),\operatorname{supp}(u_{i}^{\wp})\cap\operatorname{supp}(u_{j}^{\wp})=\emptyset,1\leq
i<j\leq k)$ $\displaystyle=\ (u_{1}^{\wp}\cdots u_{k}^{\wp}:u_{i}\in
G(I),\operatorname{supp}(u_{i})\cap\operatorname{supp}(u_{j})=\emptyset,1\leq
i<j\leq k)$ $\displaystyle=\ ((u_{1}\cdots u_{k})^{\wp}:u_{i}\in
G(I),\operatorname{supp}(u_{i})\cap\operatorname{supp}(u_{j})=\emptyset,1\leq
i<j\leq k)$ $\displaystyle=\ (I^{[k]})^{\wp}.$

In the third equality we used the equation $u_{1}^{\wp}\cdots
u_{k}^{\wp}=(u_{1}\cdots u_{k})^{\wp}$, which holds because the monomials
$u_{1},\dots,u_{k}$ are in pairwise disjoint sets of variables. Hence,
equation (1) follows.

By [19, Corollary 1.6.3(d)] and equation (1) it follows that

$\operatorname{pd}(S/I^{[k]})\ =\ \operatorname{pd}(S^{\wp}/(I^{[k]})^{\wp})\
=\ \operatorname{pd}(S^{\wp}/(I^{\wp})^{[k]}).$

Taking into account that $S^{\wp}$ is a polynomial ring in $|{\bf deg}(I)|$
variables, applying the Auslander–Buchsbaum formula we get

$\operatorname{depth}(S/I^{[k]})+|{\bf
deg}(I)|-n=\operatorname{depth}(S^{\wp}/(I^{\wp})^{[k]}).$

Since $\textup{indeg}(I^{[k]})=\textup{indeg}((I^{\wp})^{[k]})$, subtracting
$\textup{indeg}(I^{[k]})-1$ from both sides of the above equation, we obtain

$g_{I}(k)\ =\ g_{I^{\wp}}(k),\ \ \textup{for all}\ \ 1\leq k\leq\nu(I).$

By our assumption, $g_{I^{\wp}}$ is nonincreasing, because $I^{\wp}$ is a
squarefree monomial ideal. Hence, $g_{I}$ is nonincreasing, as well.

In the course of the proof, we have shown:

######  Corollary 1.9.

Let $I\subset S$ be a monomial ideal. Then, the following hold.

  1. (a)

$g_{I}=g_{I^{\wp}}$ and $\nu(I)=\nu(I^{\wp})$.

  2. (b)

$(I^{[k]})^{\wp}=(I^{\wp})^{[k]}$ for all $1\leq k\leq\nu(I)$.

  3. (c)

$\operatorname{depth}(S/I^{[k]})=\operatorname{depth}(S^{\wp}/(I^{\wp})^{[k]})-|{\bf
deg}(I)|+n$, for all $1\leq k\leq\nu(I)$.

### Highest nonvanishing matching power of a quadratic monomial ideal

A monomial ideal $I\subset S$ generated in a single degree is called
polymatroidal if the exchange property holds: for all $u,v\in G(I)$ and all
$i$ with $\deg_{x_{i}}(u)>\deg_{x_{i}}(v)$ there exists $j$ such that
$\deg_{x_{j}}(u)<\deg_{x_{j}}(v)$ and $x_{j}(u/x_{i})\in G(I)$. A squarefree
polymatroidal ideal is called matroidal.

A polymatroidal ideal has linear quotients with respect to the lexicographic
order induced by any ordering of the variables. Indeed, a polymatroidal ideal
is weakly polymatroidal and the above claim follows from [19, Proof of Theorem
12.7.2].

Our next main result states that the highest nonvanishing matching power of a
quadratic monomial ideal is polymatroidal and thus it has linear quotients.

######  Theorem 1.10.

Let $I\subset S$ be a monomial ideal generated in degree two. Then
$I^{[\nu(I)]}$ is a polymatroidal ideal.

We postpone the proof of Theorem 1.10 until the end of this section because it
is based upon the squarefree version of the theorem which we will prove first.
We will use the technique of polarization to pass from the squarefree case to
the non-squarefree case. If $I$ is a polymatroidal ideal, then $I^{\wp}$ is
not necessarily polymatroidal. For instance, the ideal
$I=(x_{1}^{2},x_{1}x_{2},x_{2}^{2})$ is polymatroidal but $I^{\wp}$ is not. On
the other hand, we have

######  Lemma 1.11.

Let $I\subset S$ be a monomial ideal. If $I^{\wp}$ is polymatroidal, then so
is $I$.

###### Proof.

Let $u,v\in G(I)$ with $p=\deg_{x_{i}}(u)>\deg_{x_{i}}(v)$. Then $x_{i,p}$
divides $u^{\wp}$ but not $v^{\wp}$. In fact,

$\deg_{x_{i,p}}(u^{\wp})=1>0=\deg_{x_{i,p}}(v^{\wp}).$

Since $I^{\wp}$ is polymatroidal, there exists $x_{j,k}$ with $j\neq i$ such
that

$\deg_{x_{j,k}}(v^{\wp})=1>0=\deg_{x_{j,k}}(u^{\wp})$

and $x_{j,k}(u^{\wp}/x_{i,p})\in G(I^{\wp})$. This implies
$\deg_{x_{j}}(u)=k-1$ and $\deg_{x_{j}}(v)\geq k$. Then

$(x_{j}u/x_{i})^{\wp}=x_{j,k}(u^{\wp}/x_{i,p})\in G(I^{\wp})$

and thus $x_{j}u/x_{i}\in G(I)$.

Now, let us recall some definitions and fix some notation. Hereafter, for an
integer $n\geq 1$, we set $[n]=\\{1,2,\dots,n\\}$. If $F\subseteq[n]$ is non
empty, we set ${\bf x}_{F}=\prod_{i\in F}x_{i}$.

Let $G$ be a finite simple graph on vertex set $V(G)=[n]$ and with edge set
$E(G)$. The edge ideal of $G$ is the ideal $I(G)=(x_{i}x_{j}:\\{i,j\\}\in
E(G))$ of $S=K[x_{1},\dots,x_{n}]$. A matching of $G$ is a set of edges of $G$
which are pairwise disjoint. If $M$ is a matching, then we denote by $V(M)$
the set of vertices $\bigcup_{e\in M}e$. We denote by $\nu(G)$ the matching
number of $G$ which is the maximum size of a matching of $G$. Then one can
verify that $\nu(I(G))=\nu(G)$.

Bigdeli et al. showed in [4, Theorem 4.1] that $I(G)^{[\nu(G)]}$ has linear
quotients for any finite simple graph $G$. We strengthen their result as
follows:

######  Theorem 1.12.

Let $G$ be a finite simple graph. Then $I(G)^{[\nu(G)]}$ is polymatroidal.

###### Proof.

Set $k=\nu(G)$, and let $u,v\in G(I(G)^{[k]})$ and $i$ such that
$\deg_{x_{i}}(u)>\deg_{x_{i}}(v)$. Our job is to find $j$ such that
$\deg_{x_{j}}(u)<\deg_{x_{j}}(v)$ and $x_{j}(u/x_{i})\in G(I(G)^{[k]})$.

Since $\nu(G)=\nu(I(G))$, we have

$u={\bf x}_{e_{1}}\cdots{\bf x}_{e_{k}}\ \ \ \textup{and}\ \ \ v={\bf
x}_{f_{1}}\cdots{\bf x}_{f_{k}},$

where $M_{u}=\\{e_{1},\dots,e_{k}\\}$ and $M_{v}=\\{f_{1},\dots,f_{k}\\}$ are
$k$-matchings of $G$. Up to relabelling, we have $e_{1}=\\{i,h\\}$ for some
$h\in[n]$. Since $\deg_{x_{i}}(u)>\deg_{x_{i}}(v)$ and $u$ and $v$ are
squarefree, it follows that $i\notin V(M_{v})$. Thus $h\in V(M_{v})$,
otherwise $\\{e_{1},f_{1},\dots,f_{k}\\}$ would be a $(k+1)$-matching of $G$,
against the fact that $k=\nu(G)$. Thus, we may assume that
$f_{1}=\\{h,i_{1}\\}$ for some vertex $i_{1}\neq h$.

Suppose that $i_{1}\notin V(M_{u})$. Then we have
$\deg_{x_{i_{1}}}(u)<\deg_{x_{i_{1}}}(v)$ and

$x_{i_{1}}(u/x_{i})=(x_{h}x_{i_{1}}){\bf x}_{e_{2}}\cdots{\bf x}_{e_{k}}\in
G(I(G)^{[k]}).$

The exchange property holds in this case.

Otherwise, if $i_{1}\in V(M_{u})$, then we may assume that
$e_{2}=\\{i_{1},j_{1}\\}$ for some vertex $j_{1}\notin\\{i,h\\}$. Then,
$j_{1}$ must be in $V(M_{v})$, otherwise
$\\{\\{i,h\\},\\{i_{1},j_{1}\\},f_{2},\dots,f_{k}\\}$ would be a
$(k+1)$-matching of $G$, which is absurd. Hence, we may assume that
$f_{2}=\\{j_{1},i_{2}\\}$ for some $i_{2}\notin\\{i,h,i_{1},j_{1}\\}$. Now, we
distinguish two more cases.

Suppose that $i_{2}\notin V(M_{u})$. Then we have
$\deg_{x_{i_{2}}}(u)<\deg_{x_{i_{2}}}(v)$ and

$x_{i_{2}}(u/x_{i})=(x_{h}x_{i_{1}})(x_{j_{1}}x_{i_{2}}){\bf
x}_{e_{3}}\cdots{\bf x}_{e_{k}}\in G(I(G)^{[k]}).$

Thus, we are finished in this case.

Otherwise, if $i_{2}\in V(M_{u})$, then we may assume that
$e_{3}=\\{i_{2},j_{2}\\}$ for some vertex
$j_{2}\notin\\{i,h,i_{1},j_{1},i_{2}\\}$. Arguing as before, we obtain that
$j_{2}\in V(M_{v})$, and we can assume that $f_{3}=\\{j_{2},i_{3}\\}$ for some
vertex $i_{3}\notin\\{i,h,i_{1},j_{1},i_{2}\\}$.

Iterating this argument, we obtain at the $p$th step that

  1. (i)

$e_{1}=\\{i,h\\}$, $e_{2}=\\{i_{1},j_{1}\\}$, $\dots$,
$e_{p}=\\{i_{p-1},j_{p-1}\\}$ and

  2. (ii)

$f_{1}=\\{h,i_{1}\\}$, $f_{2}=\\{j_{1},i_{2}\\}$, $\dots$,
$f_{p}=\\{j_{p-1},i_{p}\\}$.

Thus, if $i_{p}\notin V(M_{u})$, then
$\deg_{x_{i_{p}}}(u)<\deg_{x_{i_{p}}}(v)$ and

$x_{i_{p}}(u/x_{i})={\bf x}_{f_{1}}\cdots{\bf x}_{f_{p}}{\bf
x}_{e_{p+1}}\cdots{\bf x}_{e_{k}}\in G(I(G)^{[k]}).$

The exchange property holds in such a case.

Otherwise, if $i_{p}\in V(M_{u})$, then $e_{p+1}=\\{i_{p},j_{p}\\}$ for some
vertex $j_{p}$ different from all vertices
$i,h,i_{1},j_{1},\dots,i_{p-1},j_{p-1},i_{p}$, and
$f_{p+1}=\\{j_{p},i_{p+1}\\}$ for some vertex $i_{p+1}$.

It is clear that the process described in (i)–(ii) terminates at most after
$k$ steps. If we reach the $k$th step, then
$\deg_{x_{i_{k}}}(u)<\deg_{x_{i_{k}}}(v)$ and

$x_{i_{k}}(u/x_{i})={\bf x}_{f_{1}}\cdots{\bf x}_{f_{k}}=v\in G(I(G)^{[k]}).$

Thus, the exchange property holds in any case and $I(G)^{[k]}$ is
polymatroidal.

We are now ready for the proof of Theorem 1.10.

###### Proof of Theorem 1.10.

Let $k=\nu(I)$. By Corollary 1.9(b), $(I^{[k]})^{\wp}=(I^{\wp})^{[k]}$.
Moreover, $I^{\wp}$ is an edge ideal and $\nu(I)=\nu(I^{\wp})$ by Corollary
1.9(a). Then Theorem 1.12 implies that $(I^{[k]})^{\wp}$ is polymatroidal.
Finally, Lemma 1.11 implies that $I^{[k]}$ is polymatroidal as well.

In [10, Corollary 3.5] it was proved that $g_{I(G)}(\nu(G))=0$ for any fully
supported edge ideal $I(G)$. As an interesting consequence of Theorem 1.12 we
extend this result to quadratic monomial ideals.

######  Corollary 1.13.

Let $I\subset S$ be a monomial ideal generated in degree two. Then
$g_{I}(\nu(I))=0$ and $\operatorname{reg}(I^{[\nu(I)]})=2\nu(I)$.

###### Proof.

By Theorem 1.12, $(I^{\wp})^{[\nu(I)]}$ is matroidal. Hence [10, Theorem 1.6]
yields that
$\operatorname{depth}(S^{\wp}/(I^{\wp})^{[\nu(I^{\wp})]})=\textup{indeg}((I^{\wp})^{[k]})-1$
and $g_{I^{\wp}}(\nu(I^{\wp}))=0$. Corollary 1.9 implies that
$g_{I}(\nu(I))=g_{I^{\wp}}(\nu(I^{\wp}))=0$. Since $I^{[\nu(I)]}$ is a
polymatroidal ideal generated in degree $2\nu(I)$, $I^{[\nu(I)]}$ has a linear
resolution. Hence $\operatorname{reg}(I^{[\nu(I)]})=2\nu(I)$.

The above result is no longer valid for monomial ideals generated in a single
degree bigger than two. For instance, for the ideal
$I=(x_{1}x_{2}^{2},x_{2}x_{3}^{2},x_{3}x_{4}^{2},x_{4}x_{1}^{2})$ of
$S=K[x_{1},\dots,x_{4}]$ we have $\nu(I)=2$ but $I^{[2]}$ does not have a
linear resolution and $g_{I}(2)=1\neq 0$.

##  2\. Edge ideals of weighted oriented graphs

In this section, we focus our attention on matching powers of edge ideals of
weighted oriented graphs. The interest in these ideals stemmed from their
relevance in coding theory, in particular in the study of Reed-Muller type
codes [24]. Recently, these ideals have been the subject of many research
papers in combinatorial commutative algebra, e.g. [2, 3, 5, 18, 23, 26].
Hereafter, by a graph $G$ we mean a finite simple undirected graph without
isolated vertices.

A (vertex)-weighted oriented graph
$\mathcal{D}=(V(\mathcal{D}),E(\mathcal{D}),w)$ consists of an underlying
graph $G$, with $V(\mathcal{D})=V(G)$, on which each edge is given an
orientation and it is equipped with a weight function
$w:V(G)\rightarrow\mathbb{Z}_{\geq 1}$. The weight of a vertex $i\in V(G)$,
denoted by $w_{i}$, is the value $w(i)$ of the weight function at $i$. The
directed edges of $\mathcal{D}$ are denoted by pairs $(i,j)\in E(\mathcal{D})$
to reflect the orientation, hence $(i,j)$ represents an edge directed from $i$
to $j$. The edge ideal of $\mathcal{D}$ is defined as the ideal

$I(\mathcal{D})\ =\ (x_{i}x_{j}^{w_{j}}\ :\ (i,j)\in E(\mathcal{D}))$

of the polynomial ring $S=K[x_{i}:i\in V(G)]$. If $w_{i}=1$ for all $i\in
V(G)$, then $I(\mathcal{D})=I(G)$ is the usual edge ideal of $G$.

######  Remark 2.1.

If $i\in V(G)$ is a source, that is a vertex such that $(j,i)\notin
E(\mathcal{D})$ for all $j$, then $\deg_{x_{i}}(I(\mathcal{D}))=1$. Therefore,
hereafter we assume that $w_{i}=1$ for all sources $i\in V(G)$.

By Proposition 1.2(a), $I(\mathcal{D})^{[k]}$ is generated by the products
$u=u_{1}\cdots u_{k}$ where $u_{p}=x_{i_{p}}x_{j_{p}}^{w_{j_{p}}}\in
G(I(\mathcal{D}))$ and
$\operatorname{supp}(u_{p})\cap\operatorname{supp}(u_{q})=\emptyset$ for all
$p\neq q$. Thus $u\in I(\mathcal{D})^{[k]}$ if and only if
$M=\\{\\{i_{1},j_{1}\\},\dots,\\{i_{k},j_{k}\\}\\}$ is a $k$-matching of $G$.
This observation justifies the choice to name $I^{[k]}$ the $k$th matching
power of $I$.

Firstly, we establish the homological comparison between the matching powers
$I(\mathcal{D})^{[k]}$ and $I(G)^{[k]}$, where $G$ is the underlying graph of
$\mathcal{D}$. The assumption in Remark 2.1 is crucial for the statement (e)
of Theorem 2.2.

######  Theorem 2.2.

Let $\mathcal{D}$ be a weighted oriented graph with underlying graph $G$.
Then, the following statements hold.

  1. (a)

$\nu(I(\mathcal{D}))=\nu(I(G))=\nu(G)$.

  2. (b)

$\operatorname{pd}(I(G)^{[k]})\leq\operatorname{pd}(I(\mathcal{D})^{[k]})$,
for all $1\leq k\leq\nu(G)$.

  3. (c)

$\operatorname{reg}(I(G)^{[k]})\leq\operatorname{reg}(I(\mathcal{D})^{[k]})$,
for all $1\leq k\leq\nu(G)$.

  4. (d)

$\beta_{i}(I(G)^{[k]})\leq\beta_{i}(I(\mathcal{D})^{[k]})$, for all $1\leq
k\leq\nu(G)$ and $i$.

  5. (e)

$g_{I(\mathcal{D})}(k)\leq g_{I(G)}(k)+\sum\limits_{i\in V(G)}w_{i}-|V(G)|$,
for all $1\leq k\leq\nu(G)$.

For the proof we recall a few basic facts. Let $I\subset S$ be a monomial
ideal.

  1. (i)

We have $\beta_{i,j}(I)=\beta_{i,j}(I^{\wp})$ for all $i$ and $j$ [19,
Corollary 1.6.3].

  2. (ii)

For a monomial $u\in S$, we set
$\sqrt{u}=\prod_{i\in\operatorname{supp}(u)}x_{i}$. If
$G(I)=\\{u_{1},\dots,u_{m}\\}$, then [19, Proposition 1.2.4] gives

$\sqrt{I}=(\sqrt{u_{1}},\dots,\sqrt{u_{m}}).$

  3. (iii)

Let $P$ be a monomial prime ideal of $S$. Let $S(P)$ be the polynomial ring in
the variables which generate $P$. The monomial localization of $I$ at $P$ is
the monomial ideal $I(P)$ of $S(P)$ which is obtained from $I$ by the
substitution $x_{i}\mapsto 1$ for all $x_{i}\notin P$. The monomial
localization can also be described as the saturation $I:(\prod_{x_{i}\notin
P}x_{i})^{\infty}$.

If ${\mathbb{F}}$ is the minimal (multi)graded free $S$-resolution of $I$, one
can construct, starting from ${\mathbb{F}}$, a possibly non-minimal
(multi)graded free $S$-resolution of $I(P)$ [20, Lemma 1.12]. It follows from
this construction that $\beta_{i}(I(P))\leq\beta_{i}(I)$ for all $i$.
Moreover, $\operatorname{pd}(I(P))\leq\operatorname{pd}(I)$ and
$\operatorname{reg}(I(P))\leq\operatorname{reg}(I)$.

###### Proof.

Statement (a) is clear. To prove (b), (c) and (d), set
$J=I(\mathcal{D})^{[k]}$. Assume that $I(\mathcal{D})$ is a fully supported
ideal of $S=K[x_{1},\dots,x_{n}]$. Let $P=(x_{1,1},\dots,x_{n,1})$.
Identifying $x_{i,1}$ with $x_{i}$ for all $i$, by applying (ii), $J^{\wp}(P)$
can be identified with $\sqrt{J}$. Then by (i) and (iii) we obtain

$\beta_{i}(\sqrt{J})=\beta_{i}(J^{\wp}(P))\leq\beta_{i}(J^{\wp})=\beta_{i}(J)$

for all $i$. To complete the proof, we will show that $\sqrt{J}=I(G)^{[k]}$.
For this aim, let $v\in G(J)$. Then
$v=(x_{i_{1}}x_{j_{1}}^{w_{j_{1}}})\cdots(x_{i_{k}}x_{j_{k}}^{w_{j_{k}}})$
with $(i_{1},j_{1}),\dots,(i_{k},j_{k})\in E(\mathcal{D})$ and the
corresponding undirected edges form a $k$-matching of $G$. Thus
$\sqrt{v}=(x_{i_{1}}x_{j_{1}})\cdots(x_{i_{k}}x_{j_{k}})\in I(G)^{[k]}$ and
consequently $\sqrt{J}\subseteq I(G)^{[k]}$. Conversely, let
$u=(x_{i_{1}}x_{j_{1}})\cdots(x_{i_{k}}x_{j_{k}})\in G(I(G)^{[k]})$ with
$\\{\\{i_{1},j_{1}\\},\dots,\\{i_{k},j_{k}\\}\\}$ a $k$-matching of $G$. Then
$(i_{1},j_{1}),\dots,(i_{k},j_{k})\in E(\mathcal{D})$ up to relabelling. So
$v=(x_{i_{1}}x_{j_{1}}^{w_{j_{1}}})\cdots(x_{i_{k}}x_{j_{k}}^{w_{j_{k}}})\in
J$ and $\sqrt{v}=u\in\sqrt{J}$. This shows that $I(G)^{[k]}\subseteq\sqrt{J}$.
Equality follows.

It remains to prove (e). Let $L$ be a monomial ideal of $S$. By the
Auslander–Buchsbaum formula we have
$\operatorname{depth}(S/L)=n-1-\operatorname{pd}(L)$. Hence, for all $1\leq
k\leq\nu(L)$ we can rewrite $g_{L}(k)$ as

$g_{L}(k)=|{\bf deg}(L)|-\operatorname{pd}(L^{[k]})-\textup{indeg}(L^{[k]}).$

By (b) we have
$\operatorname{pd}(I(G)^{[k]})\leq\operatorname{pd}(I(\mathcal{D})^{[k]})$ for
all $k$. It is clear that $|{\bf deg}(I(G))|=n$ and
$\textup{indeg}(I(G)^{[k]})=2k\leq\textup{indeg}(I(\mathcal{D})^{[k]})$ for
all $1\leq k\leq\nu(G)$. Therefore,

$\displaystyle g_{I(\mathcal{D})}(k)$ $\displaystyle=$ $\displaystyle|{\bf
deg}(I(\mathcal{D}))|-\operatorname{pd}(I(\mathcal{D})^{[k]})-\textup{indeg}(I(\mathcal{D})^{[k]})$
$\displaystyle\leq$ $\displaystyle|{\bf
deg}(I(\mathcal{D}))|-\operatorname{pd}(I(G)^{[k]})-\textup{indeg}(I(G)^{[k]})$
$\displaystyle=$ $\displaystyle
n-\operatorname{pd}(I(G)^{[k]})-\textup{indeg}(I(G)^{[k]})+|{\bf
deg}(I(\mathcal{D}))|-n$ $\displaystyle=$ $\displaystyle g_{I(G)}(k)+|{\bf
deg}(I(\mathcal{D}))|-n.$

Since $\deg_{x_{i}}(I(\mathcal{D}))=w_{i}$ for all $i$, we have $|{\bf
deg}(I(\mathcal{D}))|=\sum_{i=1}^{n}w_{i}$, as wanted.

The inequalities in (b), (c), (d) and (e) need not to be equalities.

######  Example 2.3.

Let $\mathcal{D}$ be the oriented 4-cycle with all vertices having weight 2
and with edge set $E(\mathcal{D})=\\{(a,b),(b,c),(c,d),(d,a)\\}$. Then
$I(G)^{[2]}=(abcd)$, while $I(\mathcal{D})^{[2]}=(ab^{2}cd^{2},a^{2}bc^{2}d)$.
By using Macaulay2 [17] and the package [13], we checked that
$\operatorname{pd}(I(G)^{[2]})=1<2=\operatorname{pd}(I(\mathcal{D})^{[2]})$,
$\operatorname{reg}(I(G)^{[2]})=4<7=\operatorname{reg}(I(\mathcal{D})^{[2]})$,
$\beta_{1}(I(G)^{[2]})=0<1=\beta_{1}(I(\mathcal{D})^{[2]})$, and
$g_{I(G)}(2)=1<5=g_{I(\mathcal{D})}(2)+\sum_{i=1}^{4}w_{i}-4$.

Hereafter, we concentrate our attention on edge ideals of vertex-weighted
oriented graphs. Let $\mathcal{D}^{\prime}$ and $\mathcal{D}$ be weighted
oriented graphs with underlying graphs $G^{\prime}$ and $G$ respectively. We
say $\mathcal{D}^{\prime}$ is a weighted oriented subgraph of $\mathcal{D}$ if
the vertex and edge sets of $\mathcal{D}^{\prime}$ are contained in
respectively those of $\mathcal{D}$ and the weight functions coincide on
$V(\mathcal{D}^{\prime})$. A weighted oriented subgraph $\mathcal{D}^{\prime}$
of $\mathcal{D}$ is called induced weighted oriented subgraph of $\mathcal{D}$
if $G^{\prime}$ is an induced subgraph of $G$.

Firstly, we turn to the problem of bounding the regularity of matching powers
of edge ideals. We begin with the so-called restriction lemma.

######  Lemma 2.4.

Let $\mathcal{D}^{\prime}$ be an induced weighted oriented subgraph of
$\mathcal{D}$. Then

  1. (a)

$\beta_{i,{\bf a}}(I(\mathcal{D}^{\prime})^{[k]})\leq\beta_{i,{\bf
a}}(I(\mathcal{D})^{[k]})$ for all $i$ and ${\bf a}\in\mathbb{Z}^{n}$.

  2. (b)

$\operatorname{reg}(I(\mathcal{D}^{\prime})^{[k]})\leq\operatorname{reg}(I(\mathcal{D})^{[k]})$.

###### Proof.

It follows from [9, Lemma 1.2].

Let $\operatorname{im}(G)$ denote the induced matching number of $G$. For any
weighted oriented graph $\mathcal{D}$ with underlying graph $G$, let
$\operatorname{wim}(\mathcal{D})$ denote the weighted induced matching number
of $\mathcal{D}$. That is,

$\displaystyle\operatorname{wim}(\mathcal{D})=\max\big{\\{}\\!\sum_{i=1}^{m}w(y_{i})\
:\ \ $ $\displaystyle\\{\\{x_{1},y_{1}\\},\dots,\\{x_{m},y_{m}\\}\\}\ \text{is
an}$ $\displaystyle\ \text{induced matching of}\ G,\ \text{and}\
(x_{i},y_{i})\in E(\mathcal{D})\big{\\}}.$

Notice that if $w_{i}=1$ for every $i\in V(\mathcal{D})$, then
$\operatorname{wim}(\mathcal{D})=\operatorname{im}(G)$. Otherwise, we have the
inequality $\operatorname{wim}(\mathcal{D})\geq\operatorname{im}(G)$. We
extend the regularity lower bound given in [3, Theorem 3.8] as follows.

######  Proposition 2.5.

Let $\mathcal{D}$ be a weighted oriented graph with underlying graph $G$. Then

$\operatorname{reg}(I(\mathcal{D})^{[k]})\geq\operatorname{wim}(\mathcal{D})+k$

for all $1\leq k\leq\operatorname{im}(G)$.

###### Proof.

The proof is similar to [9, Theorem 2.1]. We include the details for the sake
of completeness. Let $\\{\\{x_{1},y_{1}\\},\dots,\\{x_{r},y_{r}\\}\\}$ be an
induced matching. Suppose that $(x_{i},y_{i})\in E(\mathcal{D})$ with
$w(y_{i})=t_{i}$ and $\sum_{i=1}^{r}t_{i}=\operatorname{wim}(\mathcal{D})$.
Let $\mathcal{D}^{\prime}$ be the induced weighted oriented subgraph of
$\mathcal{D}$ on the vertices $x_{1},\dots,x_{r},y_{1},\dots,y_{r}$. Then by
Lemma 2.4 it suffices to show that

$\operatorname{reg}(I(\mathcal{D}^{\prime})^{[k]})\geq\operatorname{wim}(\mathcal{D})+k.$

To this end, we set $I=I(\mathcal{D}^{\prime})$ and we claim that

$\beta_{r-k,\operatorname{wim}(\mathcal{D})+r}(I^{[k]})\neq 0.$

Let $J=(z_{1},\dots,z_{r})$, where $z_{1},\dots,z_{r}$ are new variables. Then
$J^{[k]}$ is a squarefree strongly stable ideal in the polynomial ring
$R=K[z_{1},\dots,z_{r}]$. It was proved in [9, Theorem 2.1] that
$\beta_{r-k,r}(J^{[k]})\neq 0$.

Define the map $\phi:R\rightarrow S=K[x_{1},\dots,x_{r},y_{1},\dots,y_{r}]$ by
$z_{i}\mapsto x_{i}y_{i}^{t_{i}}$ for $i=1,\dots,r$. Since
$x_{1}y_{1}^{t_{1}},\dots,x_{r}y_{r}^{t_{r}}$ is a regular sequence on $S$,
the $K$-algebra homomorphism $\phi$ is flat. If $\mathbb{F}$ is the minimal
free resolution of $J^{[k]}$ over $R$, then
$\mathbb{G}:\mathbb{F}\otimes_{R}S$ is the minimal free resolution of
$I^{[k]}$ over $S$. It follows that

$\beta_{i,(a_{1},\dots,a_{r})}(J^{[k]})=\beta_{i,(a_{1},\dots,a_{r},t_{1}a_{1},\dots,t_{r}a_{r})}(I^{[k]})$

for any $i$ and $(a_{1},\dots,a_{r})\in\mathbb{Z}^{r}$. Then,

$0\neq\beta_{r-k,r}(J^{[k]})=\beta_{r-k,(1,\dots,1)}(J^{[k]})=\beta_{r-k,(1,\dots,1,t_{1},\dots,t_{r})}(I^{[k]})$

and $\beta_{r-k,\operatorname{wim}(\mathcal{D})+r}(I^{[k]})\neq 0$ as desired.

We close this section by providing a lower bound for the projective dimension
of matching powers of edge ideals. Let $P_{n}$ be the path of length $n$. That
is, $V(P_{n})=[n]$ and $E(P_{n})=\\{\\{1,2\\},\\{2,3\\},\dots,\\{n-1,n\\}\\}$.
We denote by $\mathcal{P}_{n}$ a weighted oriented path of length $n$, that
is, a weighted oriented graph whose underlying graph is $P_{n}$. It is
well–known that $\nu(P_{n})=\lfloor\frac{n}{2}\rfloor$.

For a weighted oriented graph $\mathcal{D}$ with underlying graph $G$, we
denote by $\ell(\mathcal{D})$ the maximal length of an induced path of $G$.

######  Proposition 2.6.

Let $\mathcal{D}$ be a weighted oriented graph. Then
$\nu(I(\mathcal{D}))\geq\lfloor\frac{\ell(\mathcal{D})}{2}\rfloor$ and

$\operatorname{pd}(I(\mathcal{D})^{[k]})\ \geq\
\begin{cases}\ell(\mathcal{D})-\lceil\frac{\ell(\mathcal{D})}{3}\rceil-k&\text{if}\
1\leq k\leq\lceil\frac{\ell(\mathcal{D})}{3}\rceil,\\\
\ell(\mathcal{D})-2k&\text{if}\ \lceil\frac{\ell(\mathcal{D})}{3}\rceil+1\leq
k\leq\lfloor\frac{\ell(\mathcal{D})}{2}\rfloor.\end{cases}$

###### Proof.

Let $\ell=\ell(\mathcal{D})$. There exists a subset $W$ of $V(\mathcal{D})$
such that the induced subgraph of $\mathcal{D}$ on $W$ is a weighted oriented
path $\mathcal{P}_{\ell}$. Theorem 2.2(b) combined with Lemma 2.4 implies that
$\operatorname{pd}(I(P_{\ell})^{[k]})\leq\operatorname{pd}(I(\mathcal{P}_{\ell})^{[k]})\leq\operatorname{pd}(I(\mathcal{D})^{[k]})$.
It was shown in [7, Theorem 3.1] that

$g_{I(P_{\ell})}(k)\ =\ \begin{cases}\lceil\frac{\ell}{3}\rceil-k&\text{if}\
1\leq k\leq\lceil\frac{\ell}{3}\rceil,\\\ \hfil 0&\text{if}\
\lceil\frac{\ell}{3}\rceil+1\leq
k\leq\lfloor\frac{\ell}{2}\rfloor.\end{cases}$

For a squarefree monomial ideal $I\subset S$, we have
$g_{I}(k)=n-\operatorname{pd}(I^{[k]})-\textup{indeg}(I^{[k]})$. Hence, the
assertion follows from the above formula.

Although we only considered weighted oriented graphs in this section, our
methods can be useful to prove analogous results for matching powers of edge
ideals of edge-weighted graphs. An edge-weighted graph
$G_{w}=(V(G_{w}),E(G_{w}),w)$ consists of an underlying graph $G$, with
$V(G_{w})=V(G)$ and $E(G_{w})=E(G)$, equipped with a weight function
$w:E(G)\rightarrow\mathbb{Z}_{\geq 1}:\\{i,j\\}\in E(G)\mapsto
w(\\{i,j\\})=w_{i,j}$. The edge ideal of $G_{w}$ is defined as the ideal

$I(G_{w})\ =\ ((x_{i}x_{j})^{w_{i,j}}\ :\ \\{i,j\\}\in E(G))$

of $S=K[x_{i}:i\in V(G)]$, see [25]. Notice that if the weight of every edge
is $1$, then the edge ideal of $G_{w}$ coincides with that of $G$.

##  3\. Linearly related matching powers

Let $I\subset S$ be a graded ideal generated in a single degree. We say $I$ is
linearly related, if the first syzygy module of $I$ is generated by linear
relations. In this section, we want to discuss which matching powers of the
edge ideal $I(\mathcal{D})$ of a vertex-weighted oriented graph $\mathcal{D}$
are linearly related.

Let $I$ be a monomial ideal of $S$ generated in degree $d$. Let $G_{I}$ denote
the graph with vertex set $G(I)$ and edge set

$E(G_{I})=\\{\\{u,v\\}:u,v\in
G(I)~{}\text{with}~{}\deg(\operatorname{lcm}(u,v))=d+1\\}.$

For all $u,v\in G(I)$ let $G^{(u,v)}_{I}$ be the induced subgraph of $G_{I}$
whose vertex set is

$V(G^{(u,v)}_{I})=\\{w\in G(I)\colon\text{$w$ divides
$\operatorname{lcm}(u,v)$}\\}.$

The following theorem provides a criterion through the graphs defined above to
determine if a monomial ideal is linearly related.

######  Theorem 3.1.

[4, Corollary 2.2] Let $I$ be a monomial ideal generated in degree $d$. Then
$I$ is linearly related if and only if for all $u,v\in G(I)$ there is a path
in $G^{(u,v)}_{I}$ connecting $u$ and $v$.

######  Lemma 3.2.

Let $I$ be a monomial ideal and let $1\leq k<\nu(I)$. Suppose that $I^{[k]}$
is generated in single degree. Then, there is an integer $d$ such that

  * (a)

$I^{[k]}$ is generated in degree $dk$.

  * (b)

$I^{[k+1]}$ is generated in degree $d(k+1)$. Moreover, if $u=u_{1}\dots
u_{k+1}\in G(I^{[k+1]})$, with each $u_{i}\in G(I)$ and
$\operatorname{supp}(u_{i})\cap\operatorname{supp}(u_{j})=\emptyset$ for
$i\neq j$, then $\deg(u_{i})=d$ for each $i$.

###### Proof.

Let $u=u_{1}\cdots u_{k+1}\in G(I^{[k+1]})$ with each $u_{i}\in G(I)$ and
$\operatorname{supp}(u_{i})\cap\operatorname{supp}(u_{j})=\emptyset$ for
$i\neq j$. Observe that $u/u_{\ell}\in G(I^{[k]})$ for any $\ell=1,\dots,k+1$.
First, we show that $\deg(u_{i})=\deg(u_{j})$ for each $i\neq j$. Without loss
of generality, assume for a contradiction that $\deg(u_{1})\neq\deg(u_{2})$.
Then $u_{2}u_{3}\cdots u_{k+1}$ and $u_{1}u_{3}\cdots u_{k+1}$ are minimal
monomial generators of $I^{[k]}$ of different degrees, which is a
contradiction. It follows that $u_{1},\dots,u_{k}$ are all of degree $d$ for
some $d$. Now, suppose that $v=v_{1}\cdots v_{k+1}\in G(I^{[k+1]})$ with each
$v_{i}\in G(I)$ and
$\operatorname{supp}(v_{i})\cap\operatorname{supp}(v_{j})=\emptyset$ for
$i\neq j$. By the above argument, each $v_{i}$ is of the same degree, say
$d^{\prime}$. Then $u_{1}\cdots u_{k}$ is a minimal monomial generator of
$I^{[k]}$ of degree $dk$ whereas $v_{1}\cdots v_{k}$ is a minimal monomial
generator of $I^{[k]}$ of degree $d^{\prime}k$. Therefore $d=d^{\prime}$ and
$u$ and $v$ have the same degree.

In [4, Theorem 3.1] it was proved that $I(G)^{s}$ is linearly related for some
$s\geq 1$ if and only if $I(G)^{k}$ is linearly related for all $k\geq 1$.
Unlike the ordinary powers of edge ideals, not all squarefree powers of $I(G)$
are linearly related if some squarefree power is linearly related. On the
other hand, it was proved in [9, Theorem 3.1] that if $I(G)^{[k]}$ is linearly
related for some $k\geq 1$, then $I(G)^{[k+1]}$ is linearly related as well.
We extend [9, Theorem 3.1] to monomial ideals, under some additional
assumptions.

######  Theorem 3.3.

Let $I$ be a monomial ideal such that $|\operatorname{supp}(w)|=2$ for every
$w\in G(I)$. Suppose that $I^{[k]}$ is linearly related for some $1\leq
k<\nu(I)$. If $\operatorname{supp}(u)\neq\operatorname{supp}(v)$ for every
$u,v\in G(I^{[k+1]})$ with $u\neq v$, then $I^{[k+1]}$ is linearly related.

###### Proof.

Suppose that $\operatorname{supp}(u)\neq\operatorname{supp}(v)$ for every
$u,v\in G(I^{[k+1]})$ with $u\neq v$. By the previous lemma, $I^{[k]}$ is
generated in degree $dk$, and $I^{[k+1]}$ is generated in degree $d(k+1)$. Let
$u,v\in G(I^{[k+1]})$ with $u\neq v$. By Theorem 3.1 and Lemma 3.2, it
suffices to find a path in $G_{I^{[k+1]}}^{(u,v)}$ connecting $u$ to $v$. Let
$u=u_{1}\cdots u_{k+1}$ and let $v=v_{1}\cdots v_{k+1}$ where $u_{i},v_{i}\in
G(I)$ for each $i=1,\dots,k+1$ and

$\operatorname{supp}(u_{p})\cap\operatorname{supp}(u_{q})=\emptyset=\operatorname{supp}(v_{p})\cap\operatorname{supp}(v_{q})$

for every distinct $p,q\in\\{1,\dots,k+1\\}$. By Lemma 3.2, we have that
$\deg(u_{i})=\deg(v_{i})=d$ for every $i=1,\dots,k+1$. By the initial
assumption, we may assume that there exists
$\ell\in\operatorname{supp}(u)\setminus\operatorname{supp}(v)$. Without loss
of generality, we may assume that $x_{\ell}$ divides $u_{1}$. Let
$\operatorname{supp}(u_{1})=\\{\ell,m\\}$. By definition of matching power,
there exists at most one $j$ such that $x_{m}$ divides $v_{j}$. Again, without
loss of generality, we may assume that $x_{m}$ does not divide $v_{i}$ for
$i=2,\dots,k+1$. Now, we have

$\operatorname{supp}(u_{1})\cap\operatorname{supp}(v_{p})=\emptyset\ \ \text{
for all }\ \ p=2,3,\dots,k+1.$

Let $u^{\prime}=u_{2}\dots u_{k+1}$ and $v^{\prime}=v_{2}\dots v_{k+1}$. Since
$u^{\prime},v^{\prime}\in G(I^{[k]})$ there exists a path
$u^{\prime}=z_{0},z_{1},z_{2},\dots,z_{t},v^{\prime}=z_{t+1}$ in
$G_{I^{[k]}}^{(u^{\prime},v^{\prime})}$ connecting $u^{\prime}$ to
$v^{\prime}$. We claim that

$P:u,u_{1}z_{1},u_{1}z_{2},\dots,u_{1}z_{t},u_{1}v^{\prime}$

is a path in $G_{I^{[k+1]}}^{(u,u_{1}v^{\prime})}$. To prove the claim, we
must show that

  * (i)

$u_{1}z_{i}\in G(I^{[k+1]})$ for all $i=1,\dots,t+1$,

  * (ii)

$u_{1}z_{i}$ divides $\operatorname{lcm}(u,u_{1}v^{\prime})$ for all
$i=1,\dots,t$ and,

  * (iii)

$\deg(\operatorname{lcm}(u_{1}z_{i},u_{1}z_{i+1}))=d(k+1)+1$ for all
$i=0,\dots,t$.

Since
$\operatorname{supp}(u_{1})\cap\operatorname{supp}(\operatorname{lcm}(u^{\prime},v^{\prime}))=\emptyset$,
the monomial $u_{1}z_{i}$ belongs to $I^{[k+1]}$ for all $i=1,\dots,t+1$.
Moreover, since $u_{1}z_{i}$ is of degree $d(k+1)$, it follows that
$u_{1}z_{i}\in G(I^{[k+1]})$, which proves (i). To see (ii) holds, observe
that

$\operatorname{lcm}(u,u_{1}v^{\prime})=\operatorname{lcm}(u_{1}z_{0},u_{1}z_{t+1})=u_{1}\operatorname{lcm}(z_{0},z_{t+1}).$

Lastly, (iii) holds because for all $i=0,\dots,t$ we have

$\deg(\operatorname{lcm}(u_{1}z_{i},u_{1}z_{i+1}))=\deg(u_{1})+\deg(\operatorname{lcm}(z_{i},z_{i+1}))=d+(dk+1).$

Now, let $w=u_{1}v_{2}\dots v_{k}$ and $w^{\prime}=v_{1}v_{2}\dots v_{k}$.
Since $w,w^{\prime}\in G(I^{[k]})$ there exists a path
$w,y_{1},y_{2},\dots,y_{s},w^{\prime}$ in $G_{I^{[k]}}^{(w,w^{\prime})}$
connecting $w$ to $w^{\prime}$. As before, we can then form a path
$P^{\prime}$

$P^{\prime}:wv_{k+1},y_{1}v_{k+1},y_{2}v_{k+1},\dots,y_{s}v_{k+1},w^{\prime}v_{k+1}=v$

in $G_{I^{[k+1]}}^{(u_{1}v^{\prime},v)}$. Connecting $P$ and $P^{\prime}$ we
get the required path, as $u_{1}v^{\prime}=wv_{k+1}$.

We will now observe that the assumption of the previous theorem is satisfied
for edge ideals of some weighted oriented graphs including those whose
underlying graphs are forests. Hereafter, to simplify the notation, we
identify each vertex $i\in V(\mathcal{D})$ with the variable $x_{i}$. Hence,
we will often write $x_{i}$ to denote $i$.

######  Lemma 3.4.

Let $\mathcal{D}$ be a weighted oriented graph whose underlying graph is $G$.
Suppose that every subgraph of $G$ has at most one perfect matching. Let
$1\leq k\leq\nu(I(\mathcal{D}))$ and $u,v\in G(I(\mathcal{D})^{[k]})$. If
$\operatorname{supp}(u)=\operatorname{supp}(v)$, then $u=v$.

###### Proof.

Let $u=x_{1}y_{1}^{w(y_{1})}\dots x_{k}y_{k}^{w(y_{k})}$ where
$(x_{i},y_{i})\in E(\mathcal{D})$ for each $i$ and
$M_{1}=\\{\\{x_{i},y_{i}\\}:i=1,\dots,k\\}$ is a matching in $G$. Let
$v=z_{1}t_{1}^{w(t_{1})}\dots z_{k}t_{k}^{w(t_{k})}$ where $(z_{i},t_{i})\in
E(\mathcal{D})$ for each $i$ and $M_{2}=\\{\\{z_{i},t_{i}\\}:i=1,\dots,k\\}$
is a matching in $G$. Suppose that
$\operatorname{supp}(u)=\operatorname{supp}(v)$. Then we can set

$W:=\\{x_{1},\dots x_{k},y_{1},\dots,y_{k}\\}=\\{z_{1},\dots,z_{k},t_{1},\dots
t_{k}\\}.$

Since the induced subgraph of $G$ on $W$ has at most one perfect matching, it
follows that $M_{1}=M_{2}$ and therefore $u=v$.

Combining Theorem 3.3 and Lemma 3.4, we get the following immediate corollary.

######  Corollary 3.5.

Let $\mathcal{D}$ be a weighted oriented graph such that every subgraph of its
underlying graph has at most one perfect matching (e.g., a forest). If
$I(\mathcal{D})^{[k]}$ is linearly related for some $1\leq
k<\nu(I(\mathcal{D}))$, then $I(\mathcal{D})^{[k+1]}$ is linearly related as
well.

Let $G$ be the underlying graph of $\mathcal{D}$. If every subgraph of $G$ has
at most one perfect matching (e.g., $G$ is a forest, or an odd cycle), and
$I(\mathcal{D})\neq I(G)$, then even more is true.

######  Theorem 3.6.

Let $\mathcal{D}$ be a weighted oriented graph with underlying graph $G$.
Suppose that every subgraph of $G$ has at most one perfect matching, and that
$I(\mathcal{D})\neq I(G)$. Let $1\leq k\leq\nu(G)$. If $I(\mathcal{D})^{[k]}$
is linearly related, then $k=\nu(I(\mathcal{D}))$.

The next example shows that we can not drop the hypothesis that every subgraph
of $G$ has at most one perfect matching.

######  Example 3.7.

Let $\mathcal{D}$ be the oriented graph on vertex set $[6]$, with weights
$w(1)=2$ and $w(i)=1$ for $i\in[6]\setminus\\{1\\}$, and with edge set

$E(\mathcal{D})=\\{(2,1),(1,3),(1,4),(1,5),(1,6)\\}\cup\\{(i,j):2\leq i<j\leq
6\\}.$

Then, $G$ has several perfect matchings, and

$I(\mathcal{D})=(x_{1}^{2}x_{2},x_{1}x_{3},x_{1}x_{4},x_{1}x_{5},x_{1}x_{6},x_{2}x_{3},x_{2}x_{4},x_{2}x_{5},x_{2}x_{6},\dots,x_{4}x_{5},x_{4}x_{6},x_{5}x_{6}).$

We have $\nu(I(\mathcal{D}))=3$. However $I(\mathcal{D})^{[2]}=I(G)^{[2]}$ and
$I(\mathcal{D})^{[3]}=I(G)^{[3]}$ are linearly related, indeed they even have
a linear resolution.

Before we can prove Theorem 3.6, we need some preliminary lemmas. Hereafter,
with abuse of notation, for a monomial $u$, we denote by
$\operatorname{supp}(u)$ also the set of variables dividing $u$.

######  Lemma 3.8.

Let $\mathcal{D}$ be a weighted oriented graph and let $1\leq
k\leq\nu(I(\mathcal{D}))$.

  1. (a)

Suppose that every subgraph of the underlying graph $G$ of $\mathcal{D}$ has
at most one perfect matching. Then, $u\in G(I(\mathcal{D}^{[k]}))$ if and only
if $u=x_{1}y_{1}^{w(y_{1})}\dots x_{k}y_{k}^{w(y_{k})}$ for some
$(x_{i},y_{i})\in E(\mathcal{D})$ with $\\{\\{x_{i},y_{i}\\}:i=1,\dots,k\\}$ a
matching in $G$.

  2. (b)

Let $u,v\in G(I(\mathcal{D})^{[k]})$ such that
$\operatorname{supp}(u)\neq\operatorname{supp}(v)$ and

$\deg(\operatorname{lcm}(u,v))=\deg(u)+1=\deg(v)+1.$

Then there exist variables $z_{1}\notin\operatorname{supp}(u)$,
$z_{2}\notin\operatorname{supp}(v)$ such that $v=uz_{1}/z_{2}$,
$\deg_{z_{1}}(v)=1$ and $\deg_{z_{2}}(u)=1$.

###### Proof.

(a) The “only if” side of the statement is by definition of matching power.
The “if” side of the statement follows from Lemma 3.4 and the fact that every
minimal monomial generator of $I(\mathcal{D})^{[k]}$ has a support of size
$2k$.

(b) Since both $u$ and $v$ have support of size $2k$ and
$\operatorname{supp}(u)\neq\operatorname{supp}(v)$, there exists a variable
$z_{1}\in\operatorname{supp}(v)\setminus\operatorname{supp}(u)$ and
$z_{2}\in\operatorname{supp}(u)\setminus\operatorname{supp}(v)$. Since
$\deg(\operatorname{lcm}(u,v))=\deg(u)+1$, we get
$\operatorname{supp}(v)\setminus\operatorname{supp}(u)=\\{z_{1}\\}$ and
$\deg_{z_{1}}(v)=1$. Similarly, since
$\deg(\operatorname{lcm}(u,v))=\deg(v)+1$, we get
$\operatorname{supp}(u)\setminus\operatorname{supp}(v)=\\{z_{2}\\}$ and
$\deg_{z_{2}}(u)=1$. Then for every
$t\in\operatorname{supp}(u)\cap\operatorname{supp}(v)$, we get
$\deg_{t}(u)=\deg_{t}(v)$ and the result follows.

######  Lemma 3.9.

Let $\mathcal{D}$ be a weighted oriented graph with underlying graph $G$.
Suppose that every subgraph of $G$ has at most one perfect matching. Suppose
that $I(\mathcal{D})^{[k]}$ is linearly related. Let $u\in
G(I(\mathcal{D})^{[k]})$ and let $x$ be a variable such that
$\deg_{x}(u)=r>1$. Then $\deg_{x}(v)=r$ for every $v\in
G(I(\mathcal{D})^{[k]})$.

###### Proof.

Let $u\neq v$. By Theorem 3.1 there is a path
$u_{0}=u,u_{1},u_{2},\dots,u_{s}=v$ in the graph
$H:=G^{(u,v)}_{I(\mathcal{D})^{[k]}}$. Since $\\{u_{0},u_{1}\\}\in E(H)$, by
Lemma 3.4 and Lemma 3.8(b) it follows that $\deg_{x}(u_{1})=r$. Similarly,
since $\\{u_{1},u_{2}\\}\in E(H)$ it follows that $\deg_{x}(u_{2})=r$.
Continuing this way, we obtain $\deg_{x}(u_{s})=r$.

###### Proof of Theorem 3.6.

We assume for a contradiction that $I(\mathcal{D})^{[k]}$ is linearly related
but $k<\nu(I(\mathcal{D}))$. Let $M=\\{\\{a_{i},b_{i}\\}:i=1,\dots,k+1\\}$ be
a matching with $(a_{i},b_{i})\in E(\mathcal{D})$. We claim that all the
$b_{i}$s have the same weight, say $q$. To see this, we let
$z=(a_{1}b_{1}^{w(b_{1})})\cdots(a_{k}b_{k}^{w(b_{k})})(a_{k+1}b_{k+1}^{w(b_{k+1})})$.
Then by Lemma 3.8(a) we see that $z/(a_{i}b_{i}^{w(b_{i})})\in
G(I(\mathcal{D})^{[k]})$ for each $i=1,\dots,k+1$. Since
$I(\mathcal{D})^{[k]}$ is generated in single degree, it follows that
$w(b_{i})=w(b_{j})$ for all $i,j$.

Since $I(\mathcal{D})\neq I(G)$ there is an edge $(c,d)\in E(\mathcal{D})$
with $w(d)=r>1$. We will show that $r=q$. Without loss of generality, we may
assume that

$\\{c,d\\}\cap\\{a_{3},a_{4},\dots,a_{k+1},b_{3},b_{4},\dots,b_{k+1}\\}=\emptyset.$

Then $\\{\\{c,d\\},\\{a_{3},b_{3}\\},\dots,\\{a_{k+1},b_{k+1}\\}\\}$ is a
matching.

On the other hand, by Lemma 3.8(a)

$(cd^{r})(a_{3}b_{3}^{q})\cdots(a_{k+1}b_{k+1}^{q})\in
G(I(\mathcal{\mathcal{D}})^{[k]})\text{ and
}(a_{2}b_{2}^{q})(a_{3}b_{3}^{q})\cdots(a_{k+1}b_{k+1}^{q})\in
G(I(\mathcal{D})^{[k]}).$

Since $I(\mathcal{D})^{[k]}$ is generated in single degree, it follows that
$r=q>1$.

Let $u=(a_{1}b_{1}^{r})(a_{2}b_{2}^{r})\cdots(a_{k}b_{k}^{r})$ and
$v=(a_{2}b_{2}^{r})(a_{3}b_{3}^{r})\cdots(a_{k+1}b_{k+1}^{r})$. Since
$\deg_{b_{1}}(u)=r>1$, Lemma 3.9 implies $\deg_{b_{1}}(v)=r$, which is a
contradiction.

We can now characterize when $I(\mathcal{D})^{[k]}$ has a linear resolution or
is linearly related provided that every subgraph of $G$ has at most one
perfect matching.

######  Theorem 3.10.

Let $\mathcal{D}$ be a weighted oriented graph with underlying graph $G$.
Suppose that every subgraph of $G$ has at most one perfect matching. Suppose
that $I(\mathcal{D})\neq I(G)$ and $1\leq k\leq\nu(G)$. Then the following
statements are equivalent.

  1. (a)

$I(\mathcal{D})^{[k]}$ is linearly related.

  2. (b)

$I(\mathcal{D})^{[k]}$ is polymatroidal.

  3. (c)

$I(\mathcal{D})^{[k]}$ has a linear resolution.

###### Proof.

A polymatroidal ideal has linear quotients [19, Theorem 12.6.2] and therefore
it has a linear resolution [19, Proposition 8.2.1]. We will only show that (a)
$\Rightarrow$ (b) because (b) $\Rightarrow$ (c) $\Rightarrow$ (a) is known.

Suppose that $I(\mathcal{D})^{[k]}$ is linearly related. For the rest of the
proof, keep in mind that by Lemma 3.9 for any $m_{1},m_{2}\in
G(I(\mathcal{D})^{[k]})$

$\deg_{t}(m_{1})=\deg_{t}(m_{2})\text{ for every
}t\in\operatorname{supp}(m_{1})\cap\operatorname{supp}(m_{2}).$ (2)

Let $u,v\in G(I(\mathcal{D})^{[k]})$. Let $\\{e_{1},\dots,e_{k}\\}$ be the
underlying matching (of undirected edges) for $u$, that is,
$\bigcup_{i=1}^{k}e_{i}=\operatorname{supp}(u)$. Similarly, let
$\\{f_{1},\dots,f_{k}\\}$ be the underlying matching (of undirected edges) for
$v$, that is, $\bigcup_{i=1}^{k}f_{i}=\operatorname{supp}(v)$. Let $M_{e_{i}}$
be the monomial factor of $u$ corresponding to $e_{i}$. More precisely, we
define

$M_{e_{i}}=\prod_{t\in e_{i}}t^{\deg_{t}(u)}\ \ \text{ and }\ \
M_{f_{i}}=\prod_{t\in f_{i}}t^{\deg_{t}(v)}$

for every $i=1,\dots,k$ so that $u=M_{e_{1}}\dots M_{e_{k}}$ and
$v=M_{f_{1}}\dots M_{f_{k}}$.

We know from Theorem 3.6 that $k=\nu(G)$. Therefore,
$\operatorname{supp}(v)\cap e_{i}\neq\emptyset$ for every $i=1,\dots,k$.
Suppose that $z_{0}$ is a variable which divides $u$ but not $v$. Then by
Lemma 3.9 we must have $\deg_{z_{0}}(u)=1$. We may assume that $z_{0}\in
e_{1}=\\{z_{0},y_{1}\\}$. Then $y_{1}$ divides $v$ because
$\operatorname{supp}(v)\cap e_{1}\neq\emptyset$. We may assume that $y_{1}\in
f_{1}$.

(Step 1). Let $f_{1}=\\{y_{1},z_{1}\\}$. Assume for a moment that $z_{1}$ does
not divide $u$. Then by Lemma 3.9 we must have $\deg_{z_{1}}(v)=1$. If
$(y_{1},z_{1})\in E(\mathcal{D})$, then $w:=(y_{1}z_{1})M_{e_{2}}\dots
M_{e_{k}}\in G(I(\mathcal{D})^{[k]})$ by Lemma 3.8(a) and $\deg_{y_{1}}(u)=1$
by (2). In that case, the exchange property is satisfied because
$w=z_{1}u/z_{0}$. On the other hand, if $(z_{1},y_{1})\in E(\mathcal{D})$,
then similarly the exchange property is satisfied because
$w:=(z_{1}y_{1}^{w(y_{1})})M_{e_{2}}\dots M_{e_{k}}\in
G(I(\mathcal{D})^{[k]})$.

We may assume that $z_{1}$ divides $u$ and $z_{1}\in e_{2}$. Let
$e_{2}=\\{y_{2},z_{1}\\}$. Then $y_{2}$ divides $v$ since otherwise
$\nu(G)>k$.

(Step 2). Let $f_{2}=\\{y_{2},z_{2}\\}$. Assume for a moment that $z_{2}$ does
not divide $u$. Then by Lemma 3.9 we must have $\deg_{z_{2}}(v)=1$. If
$(y_{2},z_{2})\in E(\mathcal{D})$, then
$w:=(y_{2}z_{2})M_{f_{1}}M_{e_{3}}\dots M_{e_{k}}\in G(I(\mathcal{D})^{[k]})$
by Lemma 3.8 and $\deg_{y_{2}}(u)=1$ by (2). In that case, the exchange
property is satisfied because $w=z_{2}u/z_{0}$ by (2). On the other hand, if
$(z_{2},y_{2})\in E(\mathcal{D})$, then similarly the exchange property is
satisfied because $w:=(z_{2}y_{2}^{w(y_{2})})M_{f_{1}}M_{e_{3}}\dots
M_{e_{k}}\in G(I(\mathcal{D})^{[k]})$.

We may assume that $z_{2}$ divides $u$ and $z_{2}\in e_{3}$. Let
$e_{3}=\\{y_{3},z_{2}\\}$. Then $y_{3}$ divides $v$ since otherwise
$\nu(G)>k$. If this process stops at some point, then we are done. Suppose
that it continues until the last step:

(Step $\mathbf{k-1}$). At this point, we have $e_{i}=\\{y_{i},z_{i-1}\\}$ for
all $1\leq i\leq k$ and $f_{j}=\\{y_{j},z_{j}\\}$ for all $1\leq j\leq k-1$.
First, observe that $y_{k}\in f_{k}$ since otherwise
$\\{e_{1},e_{2},\dots,e_{k}\\}\cup\\{f_{k}\\}$ is a matching in $G$, which is
not possible because $\nu(G)=k$. Now, let $f_{k}=\\{y_{k},z_{k}\\}$. Then by
Lemma 3.9 we must have $\deg_{z_{k}}(v)=1$. If $(y_{k},z_{k})\in
E(\mathcal{D})$, then $w:=(y_{k}z_{k})M_{f_{1}}M_{f_{2}}\dots M_{f_{k-1}}\in
G(I(\mathcal{D})^{[k]})$ by Lemma 3.8. By (2) we get $w=z_{k}u/z_{0}$. On the
other hand, if $(z_{k},y_{k})\in E(\mathcal{D})$, then by a similar argument
$w:=(z_{k}y_{k}^{w(y_{k})})M_{f_{1}}M_{f_{2}}\dots M_{f_{k-1}}\in
G(I(\mathcal{D})^{[k]})$ and $w=z_{k}u/z_{0}$.

######  Example 3.11.

Let $\mathcal{D}$ be a weighted oriented graph whose underlying graph $G$ is
an odd cycle, say $C_{2k+1}$ with $V(C_{2k+1})=[2k+1]$ and edge set

$E(C_{2k+1})=\\{\\{1,2\\},\\{2,3\\},\dots,\\{2k,2k+1\\},\\{2k+1,1\\}\\}.$

It is well–known that $\nu(G)=k$. We claim that $I(\mathcal{D})^{[\nu(G)]}$ is
linearly related if and only if $I(\mathcal{D})=I(G)$. Indeed, suppose that
this is not the case but that $I(\mathcal{D})^{[\nu(G)]}$ is linearly related.
Then there exists a vertex $i\in V(G)$ which is not a source such that
$w(i)>1$. Up to relabeling, we may assume that $i=1$ and $(2,1)\in
E(\mathcal{D})$. Hence, there is a generator of $I(\mathcal{D})^{[\nu(G)]}$
whose $x_{1}$-degree is $w(1)>1$. Then, Lemma 3.9 would imply that all
generators of $I(\mathcal{D})^{[\nu(G)]}$ have $x_{1}$-degree bigger than 1.
However, if we consider the $k$-matching
$M=\\{\\{2,3\\},\\{4,5\\},\dots,\\{2k,2k+1\\}\\}$ of undirected edges of $G$,
then there is a unique generator $v$ of $I(\mathcal{D})^{[\nu(G)]}$ whose
support is $V(M)$ and so $\deg_{x_{1}}(v)=0$, which is absurd. Thus, we must
have $I(\mathcal{D})=I(G)$ and by Theorem 1.12 $I(\mathcal{D})^{[\nu(G)]}$ is
linearly related, indeed it even has a linear resolution.

######  Example 3.12.

In the above Theorem 3.10, the condition that every subgraph of $G$ has at
most one perfect matching is crucial. For example, let $\mathcal{D}$ be a
weighted oriented graph with
$I(\mathcal{D})=(x_{1}x_{2}^{2},x_{2}x_{3}^{2},x_{2}x_{4}^{2},x_{3}x_{1}^{2},x_{3}x_{4}^{2},x_{4}x_{1}^{2})$.
Then $I(\mathcal{D})^{[2]}$ has a linear resolution but it is not
polymatroidal. On the other hand, we do not know the answer to the following
question:

######  Question 3.13.

Let $\mathcal{D}$ be a weighted oriented graph with $I(\mathcal{D})\neq I(G)$
where $G$ is the underlying graph. Suppose that $I(\mathcal{D})^{[k]}$ is
linearly related. Then, does $I(\mathcal{D})^{[k]}$ have a linear resolution?

If $\mathcal{D}$ is a connected weighted oriented graph with
$I(\mathcal{D})\neq I(G)$, then the above question has a positive answer for
$k=1$ by [3, Theorem 3.5].

##  4\. Forests whose last matching power is polymatroidal

In this section, we combinatorially classify the weighted oriented forests
$\mathcal{D}$ whose last matching power
$I(\mathcal{D})^{[\nu(I(\mathcal{D}))]}$ is polymatroidal.

To state the classification, we recall some concepts. A leaf $v$ of a graph
$G$ is a vertex incident to only one edge. Any tree with at least one edge
possesses at least two leaves. Let $a\in V(G)$ be a leaf and $b$ be the unique
neighbor of $a$. Following [8], we say that $a$ is a distant leaf if at most
one of the neighbors of $b$ is not a leaf. In this case, we say that
$\\{a,b\\}$ is a distant edge. It is proved in [22, Proposition 9.1.1] (see,
also, [8, Lemma 4.2] or [7, Proposition 2.2]) that any forest with at least
one edge has a distant leaf.

We say that an edge $\\{a,b\\}$ of a graph $G$ is a separated edge if $a$ and
$b$ are leaves. In this case $I(G)=I(G\setminus\\{a,b\\})+(ab)$.

Suppose that $G$ is a forest whose not all edges are separate. Then, the above
result [22, Proposition 9.1.1] implies that we can find vertices
$a_{1},\dots,a_{t},b,c$, with $t\geq 1$, such that $a_{1},\dots,a_{t}$ are
distant leaves and $\\{a_{1},b\\},\dots,\\{a_{t},b\\},\\{b,c\\}\in E(G)$. In
this case we say that $(a_{1},\dots,a_{t}\ |\ b,c)$ is a distant configuration
of the forest $G$. Figure 1 displays this situation.

$c$$b$$a_{t}$$a_{1}$$a_{2}$$a_{3}$

$\dots$

$a_{4}$$G$ Figure 1. A forest $G$ with distant configuration
$(a_{1},\dots,a_{t}\ |\ b,c)$.

Let $\mathcal{D}$ be a weighted oriented graph with underlying graph $G$. If
$W\subset V(\mathcal{D})$, we denote by $\mathcal{D}\setminus W$ the induced
weighted oriented subgraph of $\mathcal{D}$ on the vertex set
$V(\mathcal{D})\setminus W$. For any edge $\\{a,b\\}\in E(G)$, we set

${\bf x}_{\\{a,b\\}}^{(\mathcal{D})}\ =\
\begin{cases}x_{a}x_{b}^{w(b)}&\textit{if}\ (a,b)\in E(\mathcal{D}),\\\
x_{b}x_{a}^{w(a)}&\textit{if}\ (b,a)\in E(\mathcal{D}).\end{cases}$

We say that $\\{a,b\\}\in E(G)$ is a strong edge if $\\{a,b\\}$ belongs to all
matchings of $G$ having maximal size $\nu(G)$. In such a case,
$I(\mathcal{D})^{[\nu(G)]}={\bf
x}_{\\{a,b\\}}^{(\mathcal{D})}I(\mathcal{D}\setminus\\{a,b\\})^{[\nu(G)-1]}$.
It is clear that a separate edge is a strong edge.

######  Lemma 4.1.

Let $G$ be a forest with distant configuration $(a_{1},\dots,a_{t}\ |\ b,c)$
and with $\nu(G)\geq 2$. Then $\\{a_{i},b\\}$ is a strong edge of $G$, for
some $i$, if and only if, $t=1$ and $c\in V(M)$ for all $(\nu(G)-1)$-matchings
$M$ of $G\setminus\\{b\\}$.

###### Proof.

Suppose that $\\{a_{i},b\\}$ is a strong edge for some $i$. Then $t=1$.
Indeed, let $M$ be a matching of $G$ of size $\nu(G)$. Then $\\{a_{i},b\\}\in
M$. But, if $t>1$ then for some $j\neq i$,
$(M\setminus\\{\\{a_{i},b\\}\\})\cup\\{\\{a_{j},b\\}\\}$ would also be a
matching of $G$ of maximal size not containing $\\{a_{i},b\\}$, which is
absurd. Thus $t=1$. Now, suppose that there exists a $(\nu(G)-1)$-matching $M$
of $G\setminus b$ with $c\notin V(M)$. Then $M\cup\\{\\{b,c\\}\\}$ would be a
maximum matching of $G$ not containing $\\{a_{i},b\\}$, which is absurd.

Conversely, assume that $(a\ |\ b,c)$ is a distant configuration of $G$ and
that $c\in V(M)$, for all $(\nu(G)-1)$-matchings of $G\setminus b$. Note that
every matching $N$ of $G$ of size $\nu(G)$ contains either $\\{b,c\\}$ or
$\\{a,b\\}$. But if $N$ contains $\\{b,c\\}$, then $N\setminus\\{\\{b,c\\}\\}$
would be a $(\nu(G)-1)$-matching of $G\setminus b$ whose vertex set does not
contain $c$, against our assumption. The conclusion follows.

######  Theorem 4.2.

Let $\mathcal{D}$ be a weighted oriented graph whose underlying graph $G$ is a
forest, with $\nu(G)\geq 2$. Suppose that $I(\mathcal{D})\neq I(G)$. Then, the
following conditions are equivalent.

  1. (a)

$I(\mathcal{D})^{[\nu(G)]}$ is linearly related.

  2. (b)

$I(\mathcal{D})^{[\nu(G)]}$ is polymatroidal.

  3. (c)

$I(\mathcal{D})^{[\nu(G)]}$ has a linear resolution.

  4. (d)

One of the following conditions holds:

  1. (d-1)

$G$ has a separate edge $\\{a,b\\}$ such that
$I(\mathcal{D}\setminus\\{a,b\\})^{[\nu(G)-1]}$ is polymatroidal, and

$I(\mathcal{D})^{[\nu(G)]}={\bf
x}_{\\{a,b\\}}^{(\mathcal{D})}I(\mathcal{D}\setminus\\{a,b\\})^{[\nu(G)-1]}.$

  2. (d-2)

$G$ has a distant configuration $(a\ |\ b,c)$ with $\\{a,b\\}\in E(G)$ a
strong edge of $G$, $I(\mathcal{D}\setminus\\{a,b\\})^{[\nu(G)-1]}$ is
polymatroidal, and

$I(\mathcal{D})^{[\nu(G)]}={\bf
x}_{\\{a,b\\}}^{(\mathcal{D})}I(\mathcal{D}\setminus\\{a,b\\})^{[\nu(G)-1]}.$

  3. (d-3)

$G$ has a distant configuration $(a_{1},\dots,a_{t}\ |\ b,c)$,
$w(a_{1})=\dots=w(a_{t})=1$, and $I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}$
is polymatroidal. Moreover the following statements hold.

     * (d-3-i)

If $I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}=0$, then ${\bf
x}_{\\{a_{i},b\\}}^{(\mathcal{D})}=x_{a_{i}}x_{b}^{\delta}$ with
$\delta\in\\{1,w(b)\\}$ for all $i$, and

$I(\mathcal{D})^{[\nu(G)]}=x_{b}^{\delta}[(x_{a_{1}},\dots,x_{a_{t}})I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}].$
(3)

     * (d-3-ii)

Otherwise, $I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}\neq 0$ is
polymatroidal, $\delta=w(b)$, $w(c)=1$ and

$I(\mathcal{D})^{[\nu(G)]}=x_{b}^{w(b)}[(x_{a_{1}},\dots,x_{a_{t}})I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}+x_{c}I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}].$
(4)

###### Proof.

From Theorem 3.10 and Lemma 3.6 it follows that (a) $\Longleftrightarrow$ (b)
$\Longleftrightarrow$ (c). To conclude the proof, we show that (b)
$\Longleftrightarrow$ (d).

Firstly, we show that (b) $\Rightarrow$ (d). Suppose that
$I(\mathcal{D})^{[\nu(G)]}$ is polymatroidal. If $G$ has a separate edge, then
the statement (d-1) holds. Let us assume that $G$ has no separate edge. Then
$G$ contains a distant configuration $(a_{1},\dots,a_{t}\ |\ b,c)$.

Suppose that $\\{a_{i},b\\}$ is a strong edge for some $i$. Then, Lemma 4.1
implies $t=1$. Since $I(\mathcal{D})^{[\nu(G)]}$ is polymatroidal if and only
if $I(\mathcal{D}\setminus\\{a,b\\})^{[\nu(G)-1]}$ is polymatroidal, (d-2)
follows.

Suppose that $\\{a_{i},b\\}$ is not a strong edge for all $i$. Every matching
of $G$ of size $\nu(G)$ contains either $\\{b,c\\}$ or $\\{a_{i},b\\}$ for
some $i=1,\dots,t$. Therefore

$I(\mathcal{D})^{[\nu(G)]}=\ \sum_{i=1}^{t}{\bf
x}_{\\{a_{i},b\\}}^{(\mathcal{D})}I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}+\
{\bf
x}_{\\{b,c\\}}^{(\mathcal{D})}I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}.$
(5)

We claim that

  1. (i)

$w(a_{i})=1$ for all $i=1,\dots,t$ and

  2. (ii)

there exists $\delta\in\\{1,w(b)\\}$ such that ${\bf
x}_{\\{a_{i},b\\}}^{(\mathcal{D})}=x_{a_{i}}x_{b}^{\delta}$ for all
$i=1,\dots,t$,

  3. (iii)

if $I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}\neq 0$ then ${\bf
x}_{\\{b,c\\}}^{(\mathcal{D})}=x_{c}x_{b}^{w(b)}$ and $\delta=w(b)$.

Once we have proved these facts, if
$I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}\neq 0$, equation (5) combined
with (i), (ii) and (iii) implies that

$I(\mathcal{D})^{[\nu(G)]}=x_{b}^{w(b)}\Big{[}(x_{a_{1}},\dots,x_{a_{t}})I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}+x_{c}I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}\Big{]}.$

Since $I(\mathcal{D})^{[\nu(G)]}$ is polymatroidal by assumption, by Lemma 2.4
applied to the graph $\mathcal{D}\setminus\\{a_{1},\dots,a_{t}\\}$, it follows
that $x_{c}I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}$ has a linear
resolution. By applying [1, Theorem 1.1], we obtain that

$\displaystyle(I(\mathcal{D})^{[\nu(G)]}:x_{a_{1}}\cdots x_{a_{t}})\ $
$\displaystyle=\
x_{b}^{w(b)}\Big{[}I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}+x_{c}I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}\Big{]}$
$\displaystyle=\ x_{b}^{w(b)}I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}$

has a linear resolution. Now, Theorem 3.10 implies that both
$I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}$ and
$I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}$ are polymatroidal, and so
(d-3-ii) follows.

Otherwise, if $I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}=0$, then equation
(5) combined with (i) and (ii) implies that

$I(\mathcal{D})^{[\nu(G)]}=x_{b}^{\delta}[(x_{a_{1}},\dots,x_{a_{t}})I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}]$

By a similar argument as before,
$I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}$ has a linear resolution. Then,
Theorem 3.10 implies that it is polymatroidal and thus (d-3-i) follows.

Next, we prove (i), (ii) and (iii).

Proof of (i): By Remark 2.1 if $a_{i}$ is a source, then we assume
$w(a_{i})=1$. Assume for a contradiction that $(b,a_{i})\in E(\mathcal{D})$
but $w(a_{i})>1$ for some $i$. Since $\\{b,c\\}$ is not a strong edge,
equation (5) implies that we can find a generator $u$ of
$I(\mathcal{D})^{[\nu(G)]}$ with $\deg_{x_{a_{i}}}(u)=w(a_{i})>1$. Lemma 3.9
implies that all generators of $I(\mathcal{D})^{[\nu(G)]}$ must have
$x_{a_{i}}$-degree equal to $w(a_{i})$. Then this implies that $\\{b,a_{i}\\}$
is a strong edge which is against our assumption. So, $w(a_{i})=1$ for all
$i$. $\square$

Proof of (ii): Lemma 3.9 and definition of $I(\mathcal{D})$ implies that there
exists a $\delta\in\\{1,w(b)\\}$ such that ${\bf
x}_{\\{a_{i},b\\}}^{(\mathcal{D})}=x_{a_{i}}x_{b}^{\delta}$ for all
$i=1,\dots,t$. $\square$

Proof of (iii): Suppose that $I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}$
is non-zero. Let $u$ be a minimal monomial generator of
$I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}$. Then ${\bf
x}_{\\{a_{i},b\\}}^{(\mathcal{D})}u$ is a minimal monomial generator of
$I(\mathcal{D})^{[\nu(G)]}$ whose $x_{c}$-degree is zero. Lemma 3.9, the
assumption that $I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}$ is non-zero
and equation (5), imply that $\deg_{x_{c}}({\bf
x}_{\\{b,c\\}}^{(\mathcal{D})})=1$. Next, we claim that $\delta=w(b)$. If $b$
is a source then $w(b)=1$ and there is nothing to prove. If $w(b)=1$, there is
also nothing to prove. Suppose that $b$ is not a source and $w(b)>1$, then
there is a vertex $d\in\\{a_{1},\dots,a_{t},c\\}$ with $(d,b)\in E(G)$ and
${\bf x}_{\\{b,d\\}}^{(\mathcal{D})}=x_{d}x_{b}^{w(b)}$. Equation (5) then
implies the existence of a generator of $I(\mathcal{D})^{[\nu(G)]}$ whose
$x_{b}$-degree is $w(b)>1$. Lemma 3.9 implies that all generators of
$I(\mathcal{D})^{[\nu(G)]}$ have $x_{b}$-degree equal to $w(b)$. Therefore
$\delta=w(b)$ and ${\bf x}_{\\{b,c\\}}^{(\mathcal{D})}=x_{c}x_{b}^{w(b)}$.
$\square$

We now prove that (d) $\Rightarrow$ (b). If (d-1) or (d-2) holds then (b)
follows from the following fact. If $I$ is a polymatroidal ideal and $u\in S$
is a monomial, then $uI$ is again polymatroidal. Suppose that (d-3) holds. If
$I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}=0$, then by equation (3), the
ideal $I(\mathcal{D})^{[\nu(G)]}$ is a product of polymatroidal ideals.
Therefore it is polymatroidal as well by [19, Theorem 12.6.3].

Now, suppose that (d-3-ii) holds. Then
$I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}$ and
$x_{c}I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}$ are polymatroidal ideals.
Hence,
$(x_{a_{1}},\dots,x_{a_{t}})I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}$ has a
linear resolution, as it is the product of monomial ideals with linear
resolution in pairwise disjoint sets of variables. Therefore [15, Corollary
2.4] implies that (4) is a Betti splitting. Now, since

$x_{c}I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}\subset
I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}\subset
I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}$

and $x_{a_{i}}$ do not divide any generator of
$x_{c}I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}$ and
$I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}$, for all $1\leq i\leq t$, we
obtain that

$(x_{a_{1}},\dots,x_{a_{t}})I(\mathcal{D}\setminus\\{b\\})^{[\nu(G)-1]}\cap
x_{c}I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}=$

$=x_{c}(x_{a_{1}},\dots,x_{a_{t}})I(\mathcal{D}\setminus\\{b,c\\})^{[\nu(G)-1]}$

and this ideal has a linear resolution. Thus [6, Proposition 1.8] implies that
$I(\mathcal{D})^{[\nu(G)]}$ has a linear resolution. By Theorem 3.10 it
follows that $I(\mathcal{D})^{[\nu(G)]}$ is polymatroidal and (b) follows.

Inspecting the proof of Theorem 4.2, we see how to construct, recursively, all
weighted oriented forests $\mathcal{D}$, with a given matching number, whose
last matching power $I(\mathcal{D})^{[\nu(I(\mathcal{D}))]}$ is polymatroidal.
Indeed, suppose that we have constructed all weighted oriented forests
$\mathcal{D}$ with $\nu(I(\mathcal{D}))=k$ and $I(\mathcal{D})^{[k]}$
polymatroidal, then, according to the three possible cases (d-1), (d-2),
(d-3), we can construct all weighted oriented forests $\mathcal{H}$ with
$I(\mathcal{H})^{[\nu(I(\mathcal{H}))]}$ polymatroidal and with matching
number $k+1$, one bigger than the previous fixed matching number.

Let $\mathcal{D}$ be a weighted oriented graph, whose underlying graph $G$ is
a forest, such that $I(\mathcal{D})\neq I(G)$. We illustrate the above
procedure.

If $\nu(G)=1$, then $G$ is a star graph, with, say, $V(G)=[m]$ and
$E(G)=\\{\\{i,m\\}:1\leq i\leq m-1\\}$. If
$I(\mathcal{D})^{[1]}=I(\mathcal{D})$ is polymatroidal, then
$w_{1}=\dots=w_{m-1}=1$ by Lemma 3.9. Since $I(\mathcal{D})\neq I(G)$, then
$w_{m}>1$ and $E(\mathcal{D})=\\{(i,m):1\leq i\leq n-1\\}$. Thus,
$I(\mathcal{D})=(x_{1}x_{m}^{w_{m}},x_{2}x_{m}^{w_{m}},\dots,x_{m-1}x_{m}^{w_{m}})=x_{m}^{w_{m}}(x_{1},\dots,x_{m-1})$
is polymatroidal, for it is the product of polymatroidal ideals. In this case,

$\dots$

Now, let $\nu(G)=2$, and suppose that $I(\mathcal{D})^{[2]}$ is polymatroidal.
By Theorem 4.2, only one of the possibilities (d-1), (d-2), (d-3) occurs.
Exploiting these three possibilities, one can see that the only weighted
oriented forests $\mathcal{D}$ such that $I(\mathcal{D})^{[2]}$ is
polymatroidal, are the following ones:

$\dots$

$\dots$

$\dots$

$\dots$

$\dots$

$\dots$

In the second graph displayed above, the edge connecting the two bottom
vertices can have an arbitrary orientation.

## References

  * [1] S. Bandari, J. Herzog, Monomial localizations and polymatroidal ideals, Eur. J. Combin. 34 (2013) 752–763.
  * [2] A. Banerjee, B. Chakraborty, K. K Das, M. Mandal, S. Selvaraja, Equality of ordinary and symbolic powers of edge ideals of weighted oriented graphs, Comm. Algebra 51 (2023), no. 4, 1575–1580.
  * [3] A. Banerjee, K. K. Das, and S. Selvaraja, Powers of edge ideals of weighted oriented graphs with linear resolutions, J. Algebra Appl. 22 (2023), no. 7, Paper No. 2350148.
  * [4] M. Bigdeli, J. Herzog, R. Zaare-Nahandi, On the index of powers of edge ideals, Comm. Algebra, 46 (2018), 1080–1095.
  * [5] B. Casiday, S. Kara, Betti numbers of weighted oriented graphs, Electron. J. Combin. 28 (2021), no.2, Paper No. 2.33, 20 pp.
  * [6] M. Crupi, A. Ficarra, Linear resolutions of t-spread lexsegment ideals via Betti splittings, Journal of Algebra and Its Applications, doi 10.1142/S0219498824500725
  * [7] M. Crupi, A. Ficarra, E. Lax, Matchings, squarefree powers and Betti splittings, 2023, available at https://arxiv.org/abs/2304.00255
  * [8] N. Erey, T. Hibi, Squarefree powers of edge ideals of forests, Electron. J. Combin., 28 (2) (2021), P2.32.
  * [9] N. Erey, J. Herzog, T. Hibi, S. Saeedi Madani, Matchings and squarefree powers of edge ideals, J. Comb. Theory Series. A, 188 (2022).
  * [10] N. Erey, J. Herzog, T. Hibi, S. Saeedi Madani, The normalized depth function of squarefree powers, Collect. Math. (2023). https://doi.org/10.1007/s13348-023-00392-x
  * [11] A. Ficarra, Homological shifts of polymatroidal ideals, available at arXiv preprint https://arxiv.org/abs/2205.04163 (2022).
  * [12] A. Ficarra. HomologicalShiftIdeals, Macaulay2 Package, 2023, preprint arXiv:2309.09271.
  * [13] A. Ficarra, MatchingPowers, Macaulay2 Package (2023).
  * [14] A. Ficarra, J. Herzog, T. Hibi, Behaviour of the normalized depth function, Electron. J. Comb., 30 (2), (2023) P2.31.
  * [15] C. A. Francisco, H. T. Hà, A. Van Tuyl, Splittings of monomial ideals, Proc. Amer. Math. Soc., 137 (10) (2009), 3271-3282.
  * [16] R. Fröberg, On Stanley-Reisner rings, Topics in algebra, Banach Center Publications, 26 (2) (1990), 57–70.
  * [17] D. R. Grayson, M. E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2.
  * [18] H.T. Hà, K.N. Lin, S. Morey, E. Reyes, R.H. Villarreal, Edge ideals of oriented graphs, International Journal of Algebra and Computation, 29 (03), (2019), 535–559.
  * [19] J. Herzog, T. Hibi. _Monomial ideals_ , Graduate texts in Mathematics 260, Springer, 2011.
  * [20] J. Herzog, S. Moradi, M. Rahimbeigi, G. Zhu, Homological shift ideals, Collect. Math. 72 (2021), 157–174.
  * [21] J. Herzog, T. Hibi, X. Zheng, Monomial ideals whose powers have a linear resolution, Math. Scand., 95 (2004), 23–32.
  * [22] S. Jacques, Betti numbers of graph ideals, 2004, Ph.D. thesis, University of Sheffield, Great Britain.
  * [23] S. Kara, J. Biermann, K.N. Lin, A. O’Keefe, Algebraic invariants of weighted oriented graphs, J. Algebraic Combin. 55 (2022), no.2, 461–491.
  * [24] J. Martínez-Bernal, Y. Pitones and R. H. Villarreal, Minimum distance functions of graded ideals and Reed-Muller-type codes, J. Pure Appl. Algebra 221 (2017), 251–275.
  * [25] C. Paulsen and S. Sather-Wagstaff, Edge ideals of weighted graphs, J. Algebra Appl., 12 (2013), 1250223-1-24.
  * [26] Y. Pitones, E. Reyes, J. Toledo, Monomial ideals of weighted oriented graphs, Electron. J. Combin., 26 (2019), no. 3, Research Paper P3.44.
  * [27] S. A. Seyed Fakhari, On the Castelnuovo-Mumford regularity of squarefree powers of edge ideals, 2022, available at arxiv.org/abs/2303.02791
  * [28] S. A. Seyed Fakhari, On the Regularity of squarefree part of symbolic powers of edge ideals, 2023, available at arxiv.org/abs/2207.08559