Algebraic invariants of weighted oriented graphs

Abstract

Let $\mathcal {D}$ be a weighted oriented graph and let $I(\mathcal {D})$ be its edge ideal in a polynomial ring R. We give the formula of Castelnuovo–Mumford regularity of $R/I(\mathcal {D})$ when $\mathcal {D}$ is a weighted oriented path or cycle such that edges of $\mathcal {D}$ are oriented in one direction. Additionally, we compute the projective dimension for this class of graphs.

1 Introduction

A vertex-weighted (or simply weighted) oriented graph is a triple $\mathcal {D}= (V(\mathcal {D}), E(\mathcal {D}), w)$ where $V(\mathcal {D}) = \{x_1, \dots , x_n\}$ is the vertex set of the graph, $E(\mathcal {D})$ is a directed edge set, and w is a weight function $w: V(\mathcal {D}) \rightarrow \mathbb {N^+}$. Specifically, $E(\mathcal {D})$ consists of ordered pairs $(x_i, x_j) \in V(\mathcal {D})\times V(\mathcal {D})$ where the pair $(x_i,x_j)$ represents a directed edge from $x_i$ to $x_j$. We consider finite simple oriented graphs, that is, graphs in which $V(\mathcal {D})$ is a finite set and there are neither loops nor multiple edges in $E(\mathcal {D})$. Furthermore, we simplify notation by setting $w_i = w(x_i)$ for each $i\in \{1,\ldots ,n\}.$ If the weight of a vertex $x_i$ is equal to one, i.e., $w_i =1,$ we say that the graph has a trivial weight at $x_i.$ Otherwise, we say $x_i$ has a non-trivial weight.

Given a weighted oriented graph $\mathcal {D}= (V(\mathcal {D}), E(\mathcal {D}), w)$ and $R = k[x_1, \dots , x_n]$ the polynomial ring on the vertex set $V(\mathcal {D})$ over a field k, the edge ideal of $\mathcal {D}$ is defined to be

$$\begin{aligned} I(\mathcal {D}) = \left( x_ix_j^{w_j} : (x_i, x_j) \in E(\mathcal {D})\right) \subseteq R. \end{aligned}$$

The generators of $I(\mathcal {D})$ are independent of the weight assigned to a source vertex. Therefore to simplify our formulas, throughout this paper, we shall assume that source vertices always have weight one. Furthermore, since isolated vertices do not contribute to the generating set of the edge ideal of weighted oriented graph, we assume that our graphs have no isolated vertices. When all vertices have weight one, $I(\mathcal {D})$ is the edge ideal of an unweighted unoriented graph which was introduced by Villarreal in [16] and has since been studied extensively. The study of edge ideals of weighted oriented graphs is much more recent and consequently there are many fewer results in this direction. The Cohen–Macaulayness of edge ideals of weighted oriented graphs has been studied in [5, 7, 15]. Related to our work in this paper, the authors of [18] consider the Castelnuovo–Mumford regularity (hereafter referred to as just regularity), and the projective dimension of a special case of weighted oriented paths and cycles.

The interest in studying edge ideals of weighted oriented graphs has its foundation in coding theory, specifically in the study of Reed–Muller-type codes (see [13]). Such codes arise as the image of a degree d evaluation map of a given set of projective points over a finite field. The regularity of the vanishing ideal provides a threshold for the degree of the map indicating when a Reed–Muller-type code has sufficiently large minimal distance, and is thus considered “good.” The vanishing ideal is itself a binomial ideal whose initial ideal is exactly the edge ideal of an appropriately defined weighted oriented graph. It is well-known that the regularity of an ideal is bounded above by that of its initial ideal. Given that invariants of monomial ideals are generally much easier to compute than in the binomial case, deriving formulas for the regularity of edge ideals of vertex-weighted oriented graphs is a practical strategy for eliminating “bad” Reed–Muller-type codes.

In this paper, we study the regularity and projective dimension of edge ideals of weighted oriented graphs with the goal of characterizing these algebraic invariants in terms of the combinatorial data of our weighted oriented graphs. To describe the generators of the edge ideal of a weighted oriented graph, one needs to consider the structure of the underlying undirected graph, the orientation of its edges, and its weight function. Thus it is quite a difficult problem to incorporate all of these data when deriving general formulas for the regularity and the projective dimension of an arbitrary weighted oriented graph. While the characteristic of the field can add complexity to calculating regularity and projective dimension, our formulas are combinatorial and independent of characteristic. As a natural first step, we consider two basic structures: paths and cycles. We further restrict our attention to weighted oriented paths and cycles with the natural orientation of all edges pointing in the same direction. We call these graphs weighted naturally oriented paths and cycles.

The main results of this paper provide formulas for the regularity of weighted naturally oriented paths (Theorem 7) and weighted naturally oriented cycles (Theorem 9). Our results place no restrictions on the weight function associated with these graphs apart from the requirement that any source vertices have weight one. The case in which all non-source vertices have non-trivial weights was considered in [18], the results of which are recovered in this paper.

While the majority of this paper focuses on the regularity of these edge ideals, one can also compute their projective dimension by viewing them as the ideals of string hypergraphs and cycle hypergraphs as studied in [12]. We translate the necessary notions from [12] in terms of weighted oriented paths and cycles and present the formulas for their projective dimensions (Theorem 3 and 4), thus completing the discussion on the projective dimension of weighted naturally oriented paths and cycles where all non-source vertices can have arbitrary weight.

Our paper is organized as follows. In Sect. 2, we collect necessary terminology and results from the literature. In Sect. 3, we discuss the connection between edge ideals of weighted oriented graphs and labeled hypergraphs. In particular, we present the formulas for the projective dimension of weighted naturally oriented paths and cycles. Section 4 focuses on Betti splittings of monomial ideals in which we give a large class of Betti splittings of edge ideals of weighted oriented graphs to be used in later sections. In Sect. 5, we introduce our first main result Theorem 7, which gives a formula for the regularity of weighted naturally oriented paths. In Sect. 6, we extend this result to weighted naturally oriented cycles in Theorem 9.

2 Preliminaries

In this section, we collect the notation and terminology that will be used throughout the paper. We follow the convention of the standard text [17].

Let $R = k[x_1, \ldots , x_n]$ be a polynomial ring over a field k and M be a finitely generated graded R module. Then, the graded minimal free resolution of M is an exact sequence of the form

$$\begin{aligned} 0\longrightarrow \bigoplus _{j \in {\mathbb Z}} R(-j)^{\beta _{p,j}(M)} \longrightarrow \bigoplus _{j \in {\mathbb Z}} R(-j)^{\beta _{p-1,j}(M)} \cdots \longrightarrow \bigoplus _{j \in {\mathbb Z}} R(-j)^{\beta _{0,j}(M)} \longrightarrow M \longrightarrow 0. \end{aligned}$$

Since the graded minimal free resolution of a module is unique up to isomorphism, the exponents $\beta _{i,j}(M)$ are invariants of the module called the graded Betti numbers of M. In general, computing Betti numbers explicitly is intractable so we focus instead on coarser invariants which measure the complexity of the module. In particular, this paper focuses on studying the (Castelnuovo–Mumford) regularity and projective dimension of $M=R/I$ where I is an ideal of R. These invariants are defined as follows:

$$\begin{aligned} {{\,\mathrm{reg}\,}}(M) = \max \{ j-i : \beta _{i,j} (M) \ne 0\} \end{aligned}$$

and

$$\begin{aligned} {{\,\mathrm{pd}\,}}(M) = \max \{ i : \beta _{i,j} (M) \ne 0\}. \end{aligned}$$

Calculating or even estimating the regularity or projective dimension for a general ideal is a difficult problem. Thus, we restrict our focus to edge ideals of vertex-weighted oriented graphs where we can exploit the combinatorial structure of the graph to give us information about the regularity and the projective dimension of the associated ideal.

Let I be a homogeneous ideal in R and m be a monomial of degree d with the following standard short exact sequence

$$\begin{aligned} 0 \rightarrow R/(I:m) (-d) \rightarrow R/I \rightarrow R/(I,m) \rightarrow 0. \end{aligned}$$

(2.1)

One can then obtain the following well-known regularity relationships (see, for example [14, Section 2.18]).

Lemma 1

Let I be a homogeneous ideal in a polynomial ring $R = k[x_1, \dots , x_n]$ and let m be a monomial of degree d. Then,

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/I)\le & {} \max \{ {{\,\mathrm{reg}\,}}(R/(I:m))+d, {{\,\mathrm{reg}\,}}(R/(I,m))\} \\ {{\,\mathrm{reg}\,}}(R/(I:m)) +d\le & {} \max \{ {{\,\mathrm{reg}\,}}(R/I) , {{\,\mathrm{reg}\,}}(R/(I,m))+1\}\\ {{\,\mathrm{reg}\,}}(R/(I,m))\le & {} \max \{ {{\,\mathrm{reg}\,}}(R/I) , {{\,\mathrm{reg}\,}}(R/(I:m)+d-1) \}. \end{aligned}$$

when m is a variable, we have the following special property regarding the regularity.

Lemma 2

[2, Lemma 2.10] Let I be a monomial ideal, and x is a variable in ${{\,\mathrm{supp}\,}}(I).$ Then, ${{\,\mathrm{reg}\,}}(R/(I,x)) \le {{\,\mathrm{reg}\,}}(R/I)$ and ${{\,\mathrm{reg}\,}}(R/I) \in \{{{\,\mathrm{reg}\,}}(R/(I:x))+1, {{\,\mathrm{reg}\,}}(R/(I,x))\}$.

When discussing algebraic invariants of the edge ideal of a weighted oriented graph $\mathcal {D}$, we simplify notation and use ${{\,\mathrm{reg}\,}}(\mathcal {D})$ (respectively ${{\,\mathrm{pd}\,}}(\mathcal {D})$) to refer to ${{\,\mathrm{reg}\,}}(R/I(\mathcal {D}))$ (respectively ${{\,\mathrm{pd}\,}}(R/I(\mathcal {D})).$

The following well-known results will be used throughout the paper. See [9, Lemma 3.2] for the proof.

Lemma 3

Let $R_1 = k[x_1, \ldots , x_n], R_2= k[y_1, \ldots , y_m]$ be polynomial rings over disjoint variables and $R=k[x_1\ldots , x_n, y_1, \ldots , y_m].$ Suppose $I \subset R_1$ and $J\subset R_2$ be two nonzero homogeneous ideals. Then,

• 1. ${{\,\mathrm{reg}\,}}(R/(I +J)) = {{\,\mathrm{reg}\,}}(R_1/I)+{{\,\mathrm{reg}\,}}(R_2/J),$

• 2. ${{\,\mathrm{reg}\,}}(R/(IJ)) = {{\,\mathrm{reg}\,}}(R_1/I) +{{\,\mathrm{reg}\,}}(R_2/J)+1.$

Remark 1

There are situations where we want to consider the regularity of the quotient of ideals of the form $(I(\mathcal {D}),x)$ where $x\not \in {{\,\mathrm{supp}\,}}(I(\mathcal {D}))$. The above lemma yields the equality ${{\,\mathrm{reg}\,}}(R/(I(\mathcal {D}),x))={{\,\mathrm{reg}\,}}(R/I(\mathcal {D}))$.

In our proofs, we often deal with the underlying graphs of weighted oriented paths and cycles. The regularity of the edge ideals of these underlying graphs is known and we recall the formulas of regularity for paths and cycles below.

Theorem 1

[10, Corollary 7.6.28 and 7.7.34] Let P denote a path on n vertices and C denote a cycle on n vertices. Then, ${{\,\mathrm{reg}\,}}(P) = {{\,\mathrm{reg}\,}}(C) = {\Big \lfloor }{\frac{n+1}{3}}{\Big \rfloor }.$

A useful tool in the study of monomial ideals is the process of polarization which allows us to pass from a general monomial ideal to a squarefree monomial ideal. We recall here the definition of polarization (for more information on the subject see for example [14]).

Definition 1

[14, Construction 21.7] Let $R=k[x_1,\ldots , x_n]$ be a polynomial ring over a field k. Given a n-tuple $\mathbf{a}=(a_1, \ldots , a_n) \in {\mathbb Z}_{\ge 0}^n,$ let $\mathbf {x^a}$ denote the monomial $x_1^{a_1}\cdots x_n^{a_n} \in R.$

• 1. The polarization of $\mathbf {x^a}$ is defined to be $(x^{\mathbf{a}})^{{{\,\mathrm{pol}\,}}} ,$ where $(\bullet )^{{{\,\mathrm{pol}\,}}}$ replaces $x_i^{a_i}$ by a product of distinct variables $\prod _{j=1}^{a_i} x_{i,j}.$

• 2. Let $I=(\mathbf {x^{a_1}}, \ldots , \mathbf {x^{a_r}}) \subseteq$ $R$ be a monomial ideal. The polarization of I is defined to be the ideal $I^{{{\,\mathrm{pol}\,}}} = ((\mathbf {x^{a_1}})^{{{\,\mathrm{pol}\,}}}, \ldots , (\mathbf {x^{a_r}})^{{{\,\mathrm{pol}\,}}})$ in a new polynomial ring $R^{{{\,\mathrm{pol}\,}}} = k [x_{i,j} ~|~ 1 \le i \le n, 1 \le j \le p_i],$ where $p_i$ is the maximum power of $x_i$ appearing in $\mathbf {x^{a_1}}, \ldots , \mathbf {x^{a_r}}.$

Note that for any monomial ideals J and K, we have $(J+K)^{{{\,\mathrm{pol}\,}}}=J^{{{\,\mathrm{pol}\,}}}+K^{{{\,\mathrm{pol}\,}}}.$

Polarization is particularly useful as the polarized ideal shares the same Betti numbers as the original ideal, as stated in the following lemma from [8]. This allows us to utilize the combinatorial structure of objects associated to the squarefree polarized ideal, such as hypergraphs and simplicial complexes, to characterize the algebraic invariants of the original ideal.

Lemma 4

[8, Corollary 1.6.3] Let $I \subset R$ be a monomial ideal and $I^{{{\,\mathrm{pol}\,}}} \subset R^{{{\,\mathrm{pol}\,}}}$ its polarization. Then,

• 1. $\beta _{i,j} (R/I) =\beta _{i,j} (R^{{{\,\mathrm{pol}\,}}}/I^{{{\,\mathrm{pol}\,}}})$ for all $i,j \ge 0,$

• 2. ${{\,\mathrm{pd}\,}}(R/I) ={{\,\mathrm{pd}\,}}(R^{{{\,\mathrm{pol}\,}}}/I^{{{\,\mathrm{pol}\,}}})$ and ${{\,\mathrm{reg}\,}}(R/I) ={{\,\mathrm{reg}\,}}(R^{{{\,\mathrm{pol}\,}}}/I^{{{\,\mathrm{pol}\,}}}).$

There are several ways to relate a squarefree monomial ideal I with a hypergraph. The common association is obtained by defining the edges of the hypergraph from the generators of the ideal so that I is the edge ideal of the hypergraph. However, in this paper, we study the labeled hypergraph associated with a given squarefree monomial ideal I by using the construction introduced in [11]. In this special construction, generators of the ideal correspond to vertices of the hypergraph, and the edges of the hypergraph correspond to variables which are obtained by the divisibility relations between the minimal generators of the ideal. We refer an interested reader to [11] for details on labeled hypergraphs.

Construction 2

[11] Let $I\subseteq R= k[x_1,\ldots ,x_n]$ be a squarefree monomial ideal with minimal monomial generating set $\{f_{1},\cdots ,f_{m}\}.$ The labeled hypergraph of I is the tuple $H(I) = (V(H), E(H), X(H))$. The set $V(H)=\{1,\ldots ,m\}$ is called the vertex set of H. The set E(H) is called the edge set of H(I) and is the image of the function $\phi : \{x_1,\ldots , x_n\} \rightarrow 2^V$ defined by $\phi (x_i) =\{j ~:~ x_i \text { divides } f_j\}$ where $2^V$ represents the power set of V(H). The set $X(H)=\{ x_i : \phi (x_i) \ne \emptyset \}.$

The label of an edge $F \in E(H)$ is defined as the collection of variables $x_i \in \{x_1,\ldots ,x_n\}$ such that $\phi (x_i)=F.$ The number |X(H)| counts the number of labels appearing in H(I).

It should be noted that the underlying hypergraph of H(I) is exactly the dual hypergraph (see [1]) of the hypergraph whose edge ideal is I.

Example 1

Let $I=(x_{1}x_{2},x_{2}x_{3}x_{4},x_{3}x_{4}x_{5},x_{5}x_{2}) \subseteq k[x_1, \ldots , x_6].$ Set $f_1 = x_1x_2, f_2 = x_{2}x_{3}x_{4}, f_3 = x_{3}x_{4}x_{5},$ and $f_4 = x_{5}x_{2}$. Then, $V(H)=\{1,2,3,4\},$ $E(H)=\{\{1\},\{1,2,4\},\{2,3\},\{3,4\}\},$ and $X(H)=\{ x_1,x_2,x_3,x_4,x_5\}$. See Fig. 1.

Fig. 1

Labeled hypergraph of $I = (x_{1}x_{2},x_{2}x_{3}x_{4},x_{3}x_{4}x_{5},x_{5}x_{2})$

Given a weighted oriented graph $\mathcal {D},$ we can associate the ideal $I^{{{\,\mathrm{pol}\,}}}(\mathcal {D})$ with a labeled hypergraph by using Construction 2 and denote this labeled hypergraph by $H(\mathcal {D}).$

3 Labeled hypergraphs associated to edge ideals

In this section, we employ the labeled hypergraph construction as the main tool to study the algebraic invariants of $R/I(\mathcal {D})$ for a weighted oriented graph $\mathcal {D}.$ We collect results from the literature on labeled hypergraphs and provide their immediate applications to our objects. The first part of this section presents formulas for the regularity and projective dimension of weighted oriented paths and cycles with non-trivial weights at all non-source vertices. The second part presents a formula for the projective dimension of any weighted naturally oriented path and cycle, thus completing the investigation into projective dimension for these classes of weighted oriented graphs. Furthermore, we provide a corollary that presents a closed formula for the regularity and projective dimension of a large class of weighted oriented graphs.

We begin with the following result from [11] which relates the regularity and projective dimension of $R/I(\mathcal {D})$ to the graph-theoretical invariants of the labeled hypergraph $H(\mathcal {D}).$ Here, we present a translated version of the original statement of [11, Proposition 4.1].

Proposition 1

Let $\mathcal {D}$ be a weighted oriented graph with associated labeled hypergraph $H=H(\mathcal {D})$. If $\{i\}\in E(H)$ for all $i\in [m]=V(H),$ then ${{\,\mathrm{reg}\,}}(\mathcal {D})=|X(H)|-|V(H)|$ and ${{\,\mathrm{pd}\,}}(\mathcal {D})=|V(H)|.$

Taking $\mathcal {D}$ to be a weighted oriented path or cycle in the above proposition results in explicit expressions for the regularity and projective dimension of the weighted oriented graph. The following corollary is a special case of the above result. Recall that a vertex $x \in V(\mathcal {D})$ is called a leaf in $\mathcal {D}$ if there is only one edge incident to x, and we assume the source vertices all have weight 1.

Corollary 1

Let $\mathcal {D}$ be a weighted oriented graph with weight function w on the vertices $\{x_1,\ldots , x_n\}$ with the property that there is at most one edge oriented into each vertex. Suppose that for all non-leaf, non-source vertices, $x_j$, either $w_j \ge 2$ or the unique edge $(x_i, x_j)$ into the vertex $x_j$ has the property that $x_i$ is a leaf. Then,

$$\begin{aligned} {{\,\mathrm{reg}\,}}(\mathcal {D})= & {} \sum _{i = 1}^n w_i - |E(\mathcal {D})|,\\ {{\,\mathrm{pd}\,}}(\mathcal {D})= & {} |E(\mathcal {D})|. \end{aligned}$$

Proof

Let $I(\mathcal {D})$ be the edge ideal of the weighted oriented graph $\mathcal {D}$ and let $m_1, \dots , m_r$ be the minimal generators of its polarization $I(\mathcal {D})^{\text {pol}}$. For all $1 \le s \le r$, let $m_s=x_ix_j\prod _{\ell = 1}^{w_j-1}y_{j, \ell }.$ If $x_j$ is a leaf, then $m_s$ is the only minimal generator of $I(\mathcal {D})^{\text {pol}}$ which is divisible by $x_j$ and therefore $\{s\} \in E(H(\mathcal {D}))$ with label $\{ x_j, y_{j,\ell } \mid 1\le \ell \le w_j-1 \}.$

On the other hand, if $x_j$ is not a leaf, then by assumption since $x_j$ is not a source, either $w_j \ge 2$ or $x_i$ is a leaf. If $x_i$ is a leaf then as above $m_s$ is the only minimal generator of $I(D)^{\text {pol}}$ which is divisible by $x_i$ and $\{s\}$ is in $E(H(\mathcal {D})).$ If $w_j \ge 2$, then $m_s = x_ix_j\prod _{\ell = 1}^{w_j-1}y_{j, \ell }$. In particular, $m_s$ is divisible by $y_{j,1}.$ The assumption that there is at most one edge oriented into the vertex $x_j$ means that $y_{j,1}$ does not divide any other generator of $I(\mathcal {D})^{\text {pol}}$. Thus in this case, $\{s\} \in E(H(\mathcal {D}))$ with label $\{ y_{j,\ell } \mid 1\le \ell \le w_j-1 \}.$

Since $\{s\} \in E(H(\mathcal {D}))$ for all $1\le s \le r$, by Proposition 1

$$\begin{aligned} {{\,\mathrm{reg}\,}}(\mathcal {D}) = |X(H(\mathcal {D}))| - |V(H(\mathcal {D}))| = \sum _{i = 1}^n w_i - |E(\mathcal {D})| \end{aligned}$$

and

$$\begin{aligned} {{\,\mathrm{pd}\,}}(\mathcal {D}) = |V(H(\mathcal {D}))| = |E(\mathcal {D})|. \end{aligned}$$

As a direct consequence of Corollary 1, one can immediately obtain the regularity and projective dimension of a large class of weighted oriented graphs such as naturally oriented paths, naturally oriented cycles, rooted forests, and unicyclic graphs with a naturally oriented unique cycle. Thus, we recover the results in [18].

Example 2

Let ${\mathcal P}$ be the naturally oriented path on the vertices $\{x_1, x_2,x_3,x_4\}$ with the edge ideal $I({\mathcal P}) =(x_1x_2^3,x_2x_3^4,x_3x_4^2).$ Since ${\mathcal P}$ is a path with non-trivial weights at each non-source vertex, we have ${{\,\mathrm{reg}\,}}({\mathcal P}) =1+3+4+2-3=7\text { and } {{\,\mathrm{pd}\,}}({\mathcal P})=3$ by Corollary 1. However, if there exists at least one non-source vertex with trivial weight, we cannot apply the formula given in Corollary 1. For instance, suppose instead that vertex $x_3$ in ${\mathcal P}$ has trivial weight so that $I({\mathcal P})=(x_1x_2^3,x_2x_3,x_3x_4^2).$ Computing via Macaulay2 [6] shows that ${{\,\mathrm{reg}\,}}({\mathcal P})=3$, whereas applying the formula in Corollary 1 would give a result of 4.

In light of the above example, one needs to consider the existence of trivial weights in order to be able to provide a general formula for the regularity and projective dimension of any weighted oriented path and cycle. As an immediate result of applying Construction 2 to weighted oriented paths and cycles one can see that their associated labeled hypergraphs preserve the path and cycle structures. Following the terminology introduced in [12], we see that the labeled hypergraph of a weighted oriented path is a string hypergraph, and the labeled hypergraph of a weighted oriented cycle is a cycle hypergraph (see [12, Definitions 2.13 and 4.1] for string and cycle hypergraphs). Since formulas for the projective dimension of string and cycle hypergraphs are given in [12], we focus on expressing their results in terms of weighted oriented graphs. We conclude this section by giving a complete picture of the projective dimension of weighted naturally oriented paths and cycles.

The projective dimension formulas given in [12] use the notion of modularity for string and cycle hypergraphs. For convenience, we translate their definition of modularity into the language of weighted naturally oriented paths and cycles.

Definition 2

Let ${\mathcal P}$ be a weighted naturally oriented path on the vertices $x_1,\ldots , x_n$ (in order) with directed edges $(x_1, x_2),$ $(x_2, x_3),$ $\ldots ,(x_{n-1}, x_n)$ such that vertex $x_i$ has weight $w_i$ for each $i \in \{ 1, \ldots , n\}.$ Further suppose that $2\le p_1< p_2\le \cdots <p_k\le n$ are the positions of non-trivial weights in ${\mathcal P}$ for $k\ge 1.$ We call $p=\left( p_1,\ldots , p_k\right)$ the weight sequence of ${\mathcal P}.$

Definition 3

Let ${\mathcal P}$ be a weighted naturally oriented path on n vertices with weight sequence $p=\left( p_1,\ldots , p_k\right)$ where $k \ge 1$. If $p_1 \ne 2$ and/or $p_k \ne n$ then extend the sequence $(p_1, \dots , p_k)$ by appending 2 to its beginning and/or n to its end. Denote this new sequence by $(q_0, \dots , q_{s})$ and call it the extended weighted sequence. Note that the extended weighted sequence is equal to the weight sequence if $p_1=2$ and $p_k=n$. For each $i \in \{0, \ldots , s-2\}$ let $\displaystyle \Gamma _{i,\ell }=\Gamma (q_i, \ldots , q_{i+\ell })$ denote the weighted naturally oriented induced path of ${\mathcal P}$ on the vertices $x_{q_i-1}, \ldots , x_{q_{i+\ell }}$ where $\ell \ge 2$.

Let $\Gamma$ be the collection of special induced paths defined by

$$\begin{aligned}&\Gamma =\Big \{\Gamma _{i,\ell } ~|~ 0\le i\le s-2,\, q_{i+1} -q_i \equiv q_{i+\ell } - q_{i+\ell -1} \equiv 2\\&\quad \pmod 3,\, q_{j+1} -q_{j} \equiv 0 \pmod 3 \text { for } i< j < i+\ell -1 \Big \}. \end{aligned}$$

Note that for each $i\in \{0,\dots ,s-2\}$ there is at most one $\ell \ge 2$ such that $\Gamma _{i,\ell }\in \Gamma$.

Thus, we may simplify notation and drop the second index $\ell$, $\Gamma _i=\Gamma _{i,\ell }\in \Gamma .$

The modularity of ${\mathcal P}$ is the maximal number of induced paths in $\Gamma$ that overlap in at most one edge. Symbolically, we have

$$\begin{aligned} M({\mathcal P})= \max _{i_1<i_2 \cdots< i_t} \Big \{ |\{\Gamma _{i_1}, \ldots , \Gamma _{i_t}\}| ~:~ | E(\Gamma _{i_j}) \cap E(\Gamma _{i_{j+1}}) | \le 1 \text { for } 1 \le j <t, \Gamma _i \in \Gamma \Big \}. \end{aligned}$$

It follows from the definition that $M({\mathcal P})= 0$ if $\Gamma = \emptyset .$

Example 3

Let ${\mathcal P}_1$ be a weighted naturally oriented path on the vertices $x_1,\ldots , x_9$ with non-trivial weights at vertices $x_4$ and $x_7,$ i.e., $p_1=4$ and $p_2=7.$ By following the convention of Definition 3, we set $q_0=2,q_1=4,q_2=7$, and $q_3=9.$ The only induced path of ${\mathcal P}_1$ satisfying the conditions given in the definition of $\Gamma$ is $\Gamma (2,4,7,9).$ Thus, the modularity of ${\mathcal P}_1$ is 1.

Let ${\mathcal P}_2$ be a weighted naturally oriented path on the vertices $x_1,\ldots , x_9$ with non-trivial at vertices $x_3,x_4, x_6,$ i.e., $p_1=3, p_2=4,p_3=6.$ By setting $q_0=2,q_1=3,q_2=4,q_3=6$, and $q_4=9,$ one can see that there exists no induced path of ${\mathcal P}_2$ satisfying the conditions in the definition of $\Gamma .$ Thus, $M({\mathcal P}_2)=0.$

Let ${\mathcal P}_3$ be a weighted naturally oriented path on the vertices $x_1,\ldots , x_{14}$ with non-trivial weights at vertices $x_3, x_5,x_7,x_9,x_{12},$ i.e., $p_1=3, p_2=5, p_3=7, p_4=9, p_5=12.$ By setting $q_0=2,q_1=3,q_2=5,q_3=7,q_4=9,q_5=12$, and $q_6=14,$ one can see that there are two induced paths of ${\mathcal P}_3$ satisfying conditions in the definition of $\Gamma$ and sharing $\{x_6,x_7\}$ as the common edge: $\Gamma (3,5,7)$ and $\Gamma (7,9,12,14).$ Thus, $M({\mathcal P}_3)=2.$

The next result is obtained by rephrasing the statement of [12, Theorem 3.4] for weighted naturally oriented paths.

Theorem 3

Let $\mathcal {P}$ be a weighted naturally oriented path on n vertices with the weight sequence $p=\left( p_1,\ldots , p_k\right)$ where $k\ge 1.$ Its extended weighted sequence defined in Definition  3 is $(q_0,\ldots ,q_s)$. Then,

$$\begin{aligned} {{\,\mathrm{pd}\,}}(\mathcal {P})=n-1-\sum _{i=0}^{s-1}\left\lfloor \frac{q_{i+1}-q_{i}+1}{3}\right\rfloor +M({\mathcal P}). \end{aligned}$$

Proof

Since the associated labeled hypergraph of a weighted oriented path is a string hypergraph on $n-1$ vertices, the statement holds by translating each expression appearing in [12, Theorem 3.4] to the language of weighted oriented paths.

Definition 4

Let $\mathcal {C}$ be a weighted naturally oriented cycle on the vertices $x_1,\ldots , x_n$ (in order) with directed edges $(x_1, x_2),$ $(x_2, x_3),$ $\ldots ,(x_{n-1}, x_n), (x_n, x_1)$ such that vertex $x_i$ has weight $w_i$ for each $i \in \{ 1, \ldots , n\}.$ Let $1\le p_1< p_2 \ldots <p_k\le n$ be the positions of non-trivial weights in $\mathcal {C}.$ Similar to the weight-sequence definition introduced in Definition 2, we call $(p_1,\ldots , p_k)$ the weight sequence of $\mathcal {C}.$

In general, the modularity of the weighted naturally oriented cycle is defined similarly to that of the path, in that we are counting the ways we can cover the cycle with induced paths that satisfy certain conditions. We do not fully translate the results from [12] because it is more technical, and we encourage the interested reader to refer to their paper for details. However, it should be noted that there are two main differences between the modularity of the cycle and that of the path. The positions of the non-trivial weights in $\mathcal {C}$ can start at any vertex with a non-trivial weight. By reordering the vertices of the cycle, we may assume that $1= p_1< \ldots <p_k \le n$ where $p_1, \ldots , p_k$ are the positions of non-trivial weights in $\mathcal {C}.$ Secondly, when we define the cycle analogue to $\Gamma$ in Definition 3, it is possible that one of its elements has overlapping initial and terminal edges. In this case, the modularity would be equal to 1.

Now, we are ready to rephrase the projective dimension formula of cycle hypergraphs from [12, Theorem 4.3] in terms of weighted naturally oriented cycles.

Theorem 4

Let $\mathcal {C}$ be a weighted naturally oriented cycle on n vertices and $1= p_{1}<p_{2}<\cdots <p_{k}\le n$ be the positions of non-trivial weights in $\mathcal {C}$ where $k\ge 1$. Then,

$$\begin{aligned} {{\,\mathrm{pd}\,}}(\mathcal {C})=n-\left( \sum _{i=1}^{k-1}\left\lfloor \frac{p_{i+1}-p_{i}+1}{3}\right\rfloor +\left\lfloor \frac{n+p_{1}-p_{k}}{3}\right\rfloor \right) +M(\mathcal {C}) \end{aligned}$$

Proof

Since the associated labeled hypergraph of a weighted naturally oriented cycle is a cycle hypergraph on n vertices, statement holds by [12, Theorem 4.3].

Remark 2

As a consequence of the theorems above, one can obtain the depth formulas for weighted naturally oriented paths and cycles using Auslander–Buchsbaum formula. Let ${\mathcal P}$ be a weighted naturally oriented path and $\mathcal {C}$ be a weighted naturally oriented cycle on n vertices. Then,

$$\begin{aligned} {{\,\mathrm{depth}\,}}({\mathcal P})= & {} 1+\sum _{i=0}^{s-1}\left\lfloor \frac{q_{i+1}-q_{i}+1}{3}\right\rfloor -M({\mathcal P}), \text { and } \\ {{\,\mathrm{depth}\,}}(\mathcal {C})= & {} \sum _{i=1}^{k-1}\left\lfloor \frac{p_{i+1}-p_{i}+1}{3}\right\rfloor +\left\lfloor \frac{n+p_{1}-p_{k}}{3}\right\rfloor -M(\mathcal {C}). \end{aligned}$$

4 Betti splitting

A common strategy used in the study of monomial ideals I in R is to decompose the monomial ideal into smaller ideals and recover the invariants of I using the invariants of the smaller pieces. Eliahou and Kervaire used this strategy in [3] when they introduced the notion of a Betti splitting of a monomial ideal. The idea was developed further by Francisco, Hà, and Van Tuyl in [4], where the authors studied when a monomial ideal has a Betti splitting. We recall the definition of this notion along with relevant important results from [4]. We then provide a large class of Betti splittings of edge ideals of weighted oriented graphs to be used in later sections.

Given a monomial ideal I, we denote by ${\mathcal G}(I)$ the set of minimal monomial generators of I.

Definition 5

Let I, J,  and K be monomial ideals such that ${\mathcal G}(I)$ is the disjoint union of ${\mathcal G}(J)$ and ${\mathcal G}(K).$ Then, $I = J + K$ is a Betti splitting if

$$\begin{aligned} \beta _{i,j} (R/I)= \beta _{i,j} (R/J)+\beta _{i,j} (R/K)+\beta _{i-1,j} (R/ J \cap K) \end{aligned}$$

for all $i,j > 1$.

Theorem 5

[4, Corollary 2.7] Suppose that $I= J + K$ where ${\mathcal G}(J)$ contains all the generators of I divisible by some variable $x_i$ and ${\mathcal G}(K)$ is a nonempty set containing the remaining generators of I. If J has a linear resolution, then $I = J+K$ is a Betti splitting.

When $I = J + K$ is a Betti splitting, important homological invariants of I are indeed related to the corresponding invariants of the smaller ideals J, K. The following corollary is a direct consequence of the formulas for the Betti numbers.

Corollary 2

Let $I = J + K$ be a Betti splitting. Then,

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/I)= & {} \max \{ {{\,\mathrm{reg}\,}}(R/J),{{\,\mathrm{reg}\,}}(R/K),{{\,\mathrm{reg}\,}}(R /J \cap K)-1\}\\ {{\,\mathrm{pd}\,}}(R/I)= & {} \max \{ {{\,\mathrm{pd}\,}}(R/J), {{\,\mathrm{pd}\,}}(R/K), {{\,\mathrm{pd}\,}}(R/ J \cap K)+1\}. \end{aligned}$$

One can generalize the notion of splitting edge of a graph from [4] to splitting edge of a weighted oriented graph. Let $e=(x_i,x_j)$ be an edge in a weighted oriented graph $\mathcal {D}.$ If $I(\mathcal {D})=J+K$ is a Betti splitting when $J=(x_ix_j^{w_j})$ is the monomial ideal associated with e, the edge e is called a splitting edge of $\mathcal {D}.$ The edge $(x_i,x_j)$ in Proposition 2 is a splitting edge of $\mathcal {D}.$

Proposition 2

Let $\mathcal {D}$ be a weighted oriented graph on vertex set $\{x_1 \ldots x_n\}$. Suppose that $w_j >1$ and that $(x_i, x_j)$ is the only edge of $\mathcal {D}$ oriented into the vertex $x_j$. Let $J = (x_ix_j^{w_j})$ and let K be the ideal generated by ${\mathcal G}(I(\mathcal {D})) {\setminus } \{x_ix_j^{w_j}\}$. Then, $I(\mathcal {D}) = J+K$ is a Betti splitting and further

$$\begin{aligned} {{\,\mathrm{reg}\,}}(\mathcal {D})= & {} \max \left\{ w_j, {{\,\mathrm{reg}\,}}(R/K), {{\,\mathrm{reg}\,}}(R/(J\cap K))-1\right\} ,\\ {{\,\mathrm{pd}\,}}(\mathcal {D})= & {} \max \left\{ {{\,\mathrm{pd}\,}}(R/K), {{\,\mathrm{pd}\,}}(R/(J\cap K))+1\right\} . \end{aligned}$$

Proof

Let $I(\mathcal {D})$ be the edge ideal of $\mathcal {D}$ and let $I(\mathcal {D})^{\text {pol }}$ be its polarization. The polarization of the generator $x_ix_j^{w_j}$ of $I(\mathcal {D})$ is $m = x_ix_j \prod _{\ell = 1}^{w_j-1}y_{j,\ell }$. Since $w_j \ge 2$, m is divisible by $y_{j,1}$. In particular, since $(x_i, x_j)$ is the only edge which is oriented into $x_j$, m is the only minimal generator of $I(\mathcal {D})^{\text {pol}}$ which is divisible by $y_{j,1}$. Thus by Theorem 5, $I(\mathcal {D})^{\text {pol}} = J' + K'$ is a Betti splitting where $J' = (m)$ and $K'$ is the ideal generated by ${\mathcal G}(I(\mathcal {D})^{\text {pol}}) {\setminus } \{m\}$. Note that $J' = J^{\text {pol}}$ and $K' = K^{\text {pol}}$ where $J = (x_ix_j^{w_j})$ and K is the ideal generated by ${\mathcal G}(I(\mathcal {D})) {\setminus } \{x_ix_j^{w_j}\}$. Furthermore, $(J \cap K )^{{{\,\mathrm{pol}\,}}} = J' \cap K'$ as both J and K are monomial ideals. Since polarization preserves Betti numbers by Lemma 4, this implies that $I = J+K$ is a Betti splitting.

The formulas for regularity and projective dimension are a direct application of Corollary 2 since ${{\,\mathrm{reg}\,}}(R/J) = w_j$ and ${{\,\mathrm{pd}\,}}(R/J) = 1.$

Corollary 3

Let $\mathcal {D}$ be a weighted naturally oriented path or cycle on vertex set $\left\{ x_1 \ldots x_n\right\}$. Let $x_i$ be a vertex in $\mathcal {D}$ with $w_i>1$. Let $J=(x_{i-1}x_{i}^{w_i})$ and K be the ideal generated by ${\mathcal G}(I(\mathcal {D})) {\setminus } \{x_{i-1}x_{i}^{w_i}\}.$ Then, $I(\mathcal {D}) = J+K$ is a Betti splitting and

$$\begin{aligned} {{\,\mathrm{reg}\,}}(\mathcal {D})=\max \left\{ w_i, {{\,\mathrm{reg}\,}}(R/K), {{\,\mathrm{reg}\,}}(R/(J\cap K))-1\right\} . \end{aligned}$$

Proof

This follows immediately from Proposition 2 since $(x_{i-1},x_i)$ is the only edge oriented into the vertex $x_i$ in a weighted naturally oriented path or cycle.

Remark 3

If $J\cap K=JL$ for some ideal L such that J and L have disjoint supports, then, by Lemma 3, ${{\,\mathrm{reg}\,}}(R/J\cap K)-1={{\,\mathrm{reg}\,}}(R/J)+{{\,\mathrm{reg}\,}}(R/L).$

5 Weighted oriented paths

In this section, we focus on computing the regularity of weighted naturally oriented paths. If the weight of each vertex is trivial, the edge ideal of a weighted naturally oriented path is the same as the edge ideal of an unweighted path and its regularity is given in Theorem 1. At the other extreme, if the weight of each vertex is non-trivial, the regularity and projective dimension of a path ${\mathcal P}$ can be computed explicitly via the labeled hypergraph of ${\mathcal P}$ as observed in Corollary 1. Our main result in this section is Theorem 7 which gives a formula for the regularity of a weighted naturally oriented path with any combination of trivial and non-trivial weights. This formula depends both on the weights of the vertices and the distances between successive non-trivial weights.

Before proving our main result, we introduce two lemmas which give the regularity of naturally oriented paths with special arrangements of non-trivial weights.

Lemma 5

Let ${\mathcal P}$ denote the weighted naturally oriented path on n vertices $x_1,\ldots , x_n$ such that $w_p=w \ge 2$ for some $p \in \left\{ 2,\ldots , n\right\}$ and $w_i=1$ for $i\ne p,$ $1 \le i \le n.$ Then

$$\begin{aligned} {{\,\mathrm{reg}\,}}({\mathcal P})= w+{\Big \lfloor }{\frac{n-p}{3}{\Big \rfloor }}+{\Big \lfloor }{\frac{p+1}{3}{\Big \rfloor }}-1. \end{aligned}$$

Proof

By Corollary 3, $J=(x_{p-1}x_p^{w})$ and $K=(x_{1}x_{2},\ldots ,x_{p-2}x_{p-1},x_{p}x_{p+1},\ldots ,x_{n-1}x_{n})$ is a Betti splitting of $I({\mathcal P})$. We can view the ideal K as the edge ideal of the disjoint union of two paths with trivial weights. Thus by Theorem 1, we have

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/K)={\Big \lfloor }{\frac{p-1+1}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-(p-1)+1}{3}{\Big \rfloor }} ={\Big \lfloor }{\frac{p}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-p+2}{3}{\Big \rfloor }}. \end{aligned}$$

Let $L=(x_{1}x_{2},\ldots ,x_{p-4}x_{p-3},x_{p-2},x_{p+1},x_{p+2}x_{p+3},\ldots ,x_{n-1}x_{n})$, then $J\cap K= JL$. Since L can be viewed as the sum of an edge ideal of the disjoint union of two paths and an ideal generated by variables not in those paths, by Remark 1, we have

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/L) ={\Big \lfloor }{\frac{p-3+1}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-(p+1)+1}{3}{\Big \rfloor }} ={\Big \lfloor }{\frac{p-2}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-p}{3}{\Big \rfloor }}. \end{aligned}$$

Thus by Remark 3, $\displaystyle {{\,\mathrm{reg}\,}}(R/(J\cap K))-1= w+{\Big \lfloor }{\frac{p-2}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-p}{3}{\Big \rfloor }}$ since ${{\,\mathrm{reg}\,}}(R/J)=w.$ Observe that

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/J\cap K)-1= & {} w+{\Big \lfloor }{\frac{p-2}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-p}{3}{\Big \rfloor }} \\\ge & {} {\Big \lfloor }{\frac{p}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-p+2}{3}{\Big \rfloor }} ={{\,\mathrm{reg}\,}}(R/K). \end{aligned}$$

Therefore, $\displaystyle {{\,\mathrm{reg}\,}}({\mathcal P}) ={{\,\mathrm{reg}\,}}(R/J\cap K)-1 =w+{\Big \lfloor }{\frac{p-2}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-p}{3}{\Big \rfloor }}$ by Corollary 3. Since $\displaystyle w+{\Big \lfloor }{\frac{p-2}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-p}{3}{\Big \rfloor }}=w+{\Big \lfloor }{\frac{p+1}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{n-p}{3}{\Big \rfloor }}-1$, the lemma is proved.

Lemma 6

Let ${\mathcal P}$ be a weighted naturally oriented path on n-vertices with $w_1 = w_2 = \cdots = w_{\ell -1} = 1$ and $w_j>1$ for all $\ell \le j \le n-1$. Then,

$$\begin{aligned} {{\,\mathrm{reg}\,}}({\mathcal P}) = {\Big \lfloor }\frac{\ell +1}{3}{\Big \rfloor }+ \sum _{i=\ell }^n w_i-(n-l+1). \end{aligned}$$

Proof

The edge ideal of ${\mathcal P}$ is $I({\mathcal P}) = (x_1x_2, \dots , x_{\ell -2}x_{\ell -1}, x_{\ell -1}x_\ell ^{w_\ell }, x_{\ell }x_{\ell +1}^{w_{\ell +1}}, \dots , x_{n-1}x_n^{w_n})$. Let $J=(x_{\ell -1}x_{\ell }^{w_{\ell }})$ and and $K=(x_1x_2, \ldots , x_{\ell -2}x_{\ell -1}, x_{\ell }x_{\ell +1}^{w_{\ell +1}}, \ldots , x_{n-1}x_n^{w_n}).$ By Corollary 3, one can see that $I({\mathcal P}) = J + K$ is a Betti splitting and therefore ${{\,\mathrm{reg}\,}}({\mathcal P}) = \max \{{{\,\mathrm{reg}\,}}(R/J), {{\,\mathrm{reg}\,}}(R/K), {{\,\mathrm{reg}\,}}(R/(J\cap K))-1\}$.

The ideal K is the sum of the edge ideal of a path on $(\ell -1)$ vertices with trivial weights and a weighted naturally oriented path on $(n-\ell +1)$ vertices where the weights of all non-leaf vertices are non-trivial. Then, by Lemma 3, Theorem 1, and Corollary 1, we get

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/K)= {\Big \lfloor }{\frac{\ell }{3}{\Big \rfloor }} + 1 + \sum _{i=\ell +1}^n w_{i}- (n-\ell ). \end{aligned}$$

Let $L= (x_1x_2, \ldots ,x_{\ell -4}x_{\ell -3}, x_{\ell -2}, x_{\ell +1}^{w_{\ell +1}}, x_{\ell +1}x_{\ell +2}^{w_{\ell +2}}, \ldots , x_{n-1}x_n^{w_n})$, then $J \cap K = JL$.

The ideal L is the sum of the ideal $L_1=(x_{\ell +1}^{w_{\ell +1}}, x_{\ell +1}x_{\ell +2}^{w_{\ell +2}}, \ldots , x_{n-1}x_n^{w_n}),$ the edge ideal of a path on $(\ell -3)$ vertices with trivial weights which has no variables in common with $L_1$, and a variable $x_{\ell -2}$. Further, the generator $x_{\ell -2}$ does not effect the regularity of R/L by Remark 1. The ideal $L_1$ has the same polarization as the ideal $(x_{\ell }x_{\ell +1}^{w_{\ell +1}-1}, x_{\ell +1}x_{\ell +2}^{w_{\ell +2}}, \ldots , x_{n-1}x_n^{w_n})$ after a relabeling of the variables. The regularity of this latter ideal can be computed using Corollary 1 and thus ${{\,\mathrm{reg}\,}}(R/L_1) = \sum _{i=\ell +1}^n w_{p_i}-(n-\ell )$. It follows from Lemma 3 that

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/L)= {\Big \lfloor }\frac{\ell -2}{3}{\Big \rfloor }+ \sum _{i=\ell +1}^n w_{p_i}-(n-\ell ). \end{aligned}$$

By Remark 3, we have

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/(J \cap K))-1= & {} w_{\ell }+ {\Big \lfloor }{\frac{\ell -2}{3}{\Big \rfloor }}+\sum _{i=\ell +1}^n w_i-(n-\ell )\\= & {} {\Big \lfloor }{\frac{\ell -2}{3}{\Big \rfloor }}+1-1+ w_\ell + \sum _{i=\ell +1}^n w_i-(n-\ell ) \\= & {} {\Big \lfloor }{\frac{\ell +1}{3}{\Big \rfloor }}+(w_\ell -1)+\sum _{i=\ell +1}^n w_i-(n-\ell )\\\ge & {} {\Big \lfloor }{\frac{\ell }{3}{\Big \rfloor }} + 1 + \sum _{i=\ell +1}^n w_{i}- (n-\ell ) \\= & {} {{\,\mathrm{reg}\,}}(R/K) \end{aligned}$$

where the last inequality follows from the assumption that $w_{\ell } \ge 2.$ One can see that ${{\,\mathrm{reg}\,}}(R/(J\cap K))-1 \ge {{\,\mathrm{reg}\,}}(R/J) = w_\ell$. Therefore, ${{\,\mathrm{reg}\,}}({\mathcal P})={{\,\mathrm{reg}\,}}(R/(J \cap K))-1$ by Corollary 3, and the desired equality holds.

Our next result is general in the sense that we consider weighted naturally oriented paths with arbitrary numbers of non-trivial weights. Both the values of the weights and their positions factor into our formula for the regularity of a path, motivating the following definition.

Notation 6

Let ${\mathcal P}$ be a weighted naturally oriented path on n-vertices with the weight sequence $\left( p_1,\ldots , p_k\right)$. In what follows we will abuse notation and write $(q_1, \ldots , q_t) \subseteq (p_1, \ldots , p_k)$ to mean that $(q_1, \ldots , q_t)$ is a subsequence of $(p_1, \ldots , p_k)$.

Let $\mathcal {S}$ be the collection of subsequences of the weight sequence $\left( p_1,\ldots , p_k\right)$ where the difference between any consecutive elements of the subsequence is not equal to two, i.e.,

$$\begin{aligned} \mathcal {S}= \left\{ \left( q_1,\ldots , q_t\right) \subseteq \left( p_1,\ldots , p_k\right) ~:~ q_{i+1}-q_i \ne 2\text { for each } i \in \left\{ 1, \ldots , t-1\right\} \right\} . \end{aligned}$$

Example 4

Let ${\mathcal P}_1$ be a path on the vertices $x_1,\ldots , x_7$ and (2, 3, 5, 6) be the weight sequence of ${\mathcal P}_1,$ i.e., $w_2,w_3,w_5,w_6 \ge 2$ and $w_4,w_7=1.$ In what follows, we are interested in the elements of $\mathcal {S}$ which are maximal with respect to inclusion. The maximal elements of $\mathcal {S}$ are

$$\begin{aligned} \left\{ \left( 2,3,6\right) , \left( 2,5,6\right) \right\} . \end{aligned}$$

Let ${\mathcal P}_2$ be a path on the vertices $x_1,\ldots , x_7$ and (2, 4, 6, 7) be the weight sequence of ${\mathcal P}_2,$ i.e., $w_2,w_4,w_6,w_7 \ge 2$ and $w_3,w_5=1.$ Then, the maximal elements of $\mathcal {S}$ are

$$\begin{aligned} \left\{ \left( 2,6,7\right) ,\left( 4,7\right) \right\} . \end{aligned}$$

As the previous example illustrates, the maximal elements of the set $\mathcal {S}$ always begin with $p_1$ or $p_1+2$ with the latter only occuring if $p_2 = p_1+2$.

Definition 6

For a weighted naturally oriented path ${\mathcal P}$ on n-vertices with the weight sequence $(p_1,\ldots , p_k),$ we define weight-position sum of $\mathbf{q} =\left( q_1,\ldots , q_t\right) \in \mathcal {S}$ as follows:

$$\begin{aligned} \sum \mathbf{q} = \sum (q_1,\ldots , q_t) := \sum _{i=1}^t w_{q_i} + \sum _{i=1}^{t-1} {{\Big \lfloor }{\frac{q_{i+1}-q_i}{3}}{\Big \rfloor }} -t. \end{aligned}$$

We will be interested in the largest element of the set $\left\{ \sum \mathbf{q}+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }} \mid \mathbf{q}\in \mathcal {S}\right\}$. To simplify the proof of our main result Theorem 7, we present the following lemma which states that the maximum element of this set always occurs at a maximal (with respect to inclusion) element of $\mathcal {S}$.

Lemma 7

If ${\mathcal P}$ is a weighted naturally oriented path with weight sequence $\mathbf{p}$ and $\mathbf{q}\subseteq \mathbf{q'}$ are elements of $\mathcal {S},$ then

$$\begin{aligned} \sum \mathbf{q} +{\Big \lfloor }\frac{n-q_t}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{q_1+1}{3}{\Big \rfloor }\le \sum \mathbf{q'}+ {\Big \lfloor }\frac{n-q'_{t'}}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{q'_1+1}{3}{\Big \rfloor }. \end{aligned}$$

Moreover,

$$\begin{aligned} \max _\mathbf{q \in \mathcal {S}} \left\{ \sum \mathbf{q}+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }}\right\} = \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 = p_1, p_1+2 \end{array}} \left\{ \sum \mathbf{q}+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }}\right\} . \end{aligned}$$

Proof

First note that if $\mathbf{q} = (q_1, \dots , q_t) \subseteq \mathbf{q'} = (q_1, \dots , q_j, r, q_{j+1}, \dots , q_t) \subseteq \mathbf{p}$ then since r is a position of a non-trivial weight of ${\mathcal P}$, we have $w_r-1 \ge 1.$ In addition, it follows from the properties of floor functions that ${\Big \lfloor }\frac{q_{j+1}-q_j}{3}{\Big \rfloor }\le {\Big \lfloor }\frac{q_{j+1}-r}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{r-q_j}{3}{\Big \rfloor }+ 1.$ Therefore

$$\begin{aligned} \sum \mathbf{q}= & {} \sum _{i = 1}^t w_{q_i} + \sum _{i =1}^{j-1}{\Big \lfloor }\frac{q_{i+1}-q_i}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{q_{j+1}-q_j}{3}{\Big \rfloor }+ \sum _{i =j+1}^{t-1}{\Big \lfloor }\frac{q_{i+1}-q_i}{3}{\Big \rfloor }-t \\\le & {} \sum _{i = 1}^t w_{q_i} + w_r -1 + \sum _{i =1}^{j-1}{\Big \lfloor }\frac{q_{i+1}-q_i}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{q_{j+1}-r}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{r-q_j}{3}{\Big \rfloor }+ \sum _{i =j+1}^{t-1}{\Big \lfloor }\frac{q_{i+1}-q_i}{3}{\Big \rfloor }-t \\= & {} \sum _{i = 1}^t w_{q_i} {+} w_r {+} \sum _{i =1}^{j-1}{\Big \lfloor }\frac{q_{i+1}{-}q_i}{3}{\Big \rfloor }{+} {\Big \lfloor }\frac{q_{j+1}-r}{3}{\Big \rfloor }{+} {\Big \lfloor }\frac{r-q_j}{3}{\Big \rfloor }+ \sum _{i =j+1}^{t-1}{\Big \lfloor }\frac{q_{i+1}-q_i}{3}{\Big \rfloor }-(t+1)\\= & {} \sum \mathbf{q'} \end{aligned}$$

Then, for any such $\mathbf{q}, \mathbf{q}' \in \mathcal {S},$ we have

$$\begin{aligned} \sum \mathbf{q} + {\Big \lfloor }\frac{n-q_t}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{q_1+1}{3}{\Big \rfloor }\le \sum \mathbf{q'} + {\Big \lfloor }\frac{n-q_t}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{q_1+1}{3}{\Big \rfloor }. \end{aligned}$$

Similar arguments can be made when $\mathbf{q'} = (r, q_1, \dots , q_t)$ and when $\mathbf{q'} = (q_1, \dots , q_t, r)$.

Extending this idea we can see that if $\mathbf{q}=(q_1,\ldots , q_t)$ and $\mathbf{q'}=(q'_1,\ldots , q'_s)$ are any elements of $\mathcal {S}$ with $\mathbf{q\subseteq q'}$ then

$$\begin{aligned} \sum \mathbf{q} +{\Big \lfloor }\frac{n-q_t}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{q_1+1}{3}{\Big \rfloor }\le \sum \mathbf{q'}+ {\Big \lfloor }\frac{n-q'_s}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{q'_1+1}{3}{\Big \rfloor }. \end{aligned}$$

The final part of the lemma follows from the above inequality and the observation that the maximal elements of the set $\mathcal {S}$ begin with $p_1$ or $p_1+2$ where the latter occurs if $p_2=p_1+2.$

Example 5

Let ${\mathcal P}_1$ and ${\mathcal P}_2$ be as shown in Fig. 2.

Fig. 2

Same weight sequence, different weight functions

These graphs have the same weight sequence (2, 4, 5, 8) and the same total weight sum. Note that since the two graphs have the same weight sequence, the set $\mathcal {S}$ as defined in Notation 6 will be the same for both graphs.

Given $\mathbf{q}\in \mathcal {S}$ define $f(\mathbf{q})=\sum \mathbf{q}+{\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1+1}{3}{\Big \rfloor },$ the expression introduced in Lemma 7. For each of the graphs ${\mathcal P}_1$ and ${\mathcal P}_2$, the following tables provides the value of $f(\mathbf{q})$ for each maximal element $\mathbf{q}\in \mathcal {S}$.

$$\begin{aligned} {\mathcal P}_1: ~\begin{array}{r|cc} \mathbf{q}&{} (2,5,8) &{} (4,5,8) \\ f(\mathbf{q}) &{} 10 &{} 7 \end{array} {\mathcal P}_2: ~\begin{array}{r|cc} \mathbf{q}&{} (2,5,8) &{} (4,5,8)\\ f(\mathbf{q}) &{} 8 &{} 9 \end{array} \end{aligned}$$

Here, we see that the maximum of value of $\sum \mathbf{q}+{\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1+1}{3}{\Big \rfloor }$ could come from $q_1=p_1=2$ as in ${\mathcal P}_1$ or from $q_1=p_1+2=4$ as in ${\mathcal P}_2$.

Furthermore, using Macaulay 2 [6], we see that ${{\,\mathrm{reg}\,}}({\mathcal P}_1)=10$ and ${{\,\mathrm{reg}\,}}({\mathcal P}_2)=9$, providing evidence that the regularity of the graphs is given by $f(\mathbf{q})$ which, in turn, depends on both the positions of weighted sequence and the values of the weights.

Theorem 7

Let ${\mathcal P}$ be a weighted naturally oriented path on n-vertices $x_1,\ldots , x_n$ with the weight sequence $(p_1,\ldots , p_k).$ Then

$$\begin{aligned} {{\,\mathrm{reg}\,}}({\mathcal P}) = \max _\mathbf{q \in \mathcal {S}} \left\{ \sum (q_1,\ldots , q_t)+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }}\right\} . \end{aligned}$$

Before we proceed to the proof of the main theorem, we present examples to show that the formula of regularity depends not only on the weights of the vertices but also on the weight sequence.

Example 6

Let ${\mathcal P}_1$ and ${\mathcal P}_2$ as shown in Fig. 3. These two paths each have four vertices with the same weight values 5, 4, 3, 4,  but at different positions. Their weight sequences are (2, 5, 9, 12) and (2, 4, 8, 12),  respectively. Define $f(\mathbf{q})=f(q_1,\dots ,q_t)$ as in Example 5. Using Macaulay 2 [6], one can calculate ${{\,\mathrm{reg}\,}}({\mathcal P}_1)=16$ and ${{\,\mathrm{reg}\,}}({\mathcal P}_2)=13$. We can see that $16=f(2,5,9,12)$, i.e., the regularity for ${\mathcal P}_1$ comes from the entire weight sequence. On the other hand, regularity for ${\mathcal P}_2$ is given by $13= f(2,8,12)$ where (2, 8, 12) and (4, 8, 12) are the maximal elements of $\mathcal {S}$ for ${\mathcal P}_2$ with values $f(2,8,12) =13\ge f(4,8,12)=11.$

Fig. 3

Two weighted oriented paths with the same non-trivial weight values and different weight sequences

Proof

of Theorem 7

We proceed by induction on the number of non-trivial weights k. The base case $k=1$ is proved in Lemma 5. Recall that by Lemma 7 that the maximal element of the set

$$ \left\{ \sum (q_1,\ldots , q_t)+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }}\right\} $$

will occur at a maximal (with respect to inclusion) element of $\mathcal {S}$. Suppose $k >1.$ If $w_i \ge 2$ for each $i \in \{2,\ldots , n\},$ the statement holds by Corollary 1. If $w_i = 1$ for all $1 \le i \le m$ and $w_i \ge 2$ for all $m+1\le i\le n-1$, the statement holds by Lemma 6. Thus, we may assume that there exists a non-trivial weight at position $p_j$ for some $j \in \{1,\ldots , k\}$ such that $w_{p_j+1} = 1$. Let $p_\ell$ be the smallest such position in the weight sequence. Note that it is possible that $\ell =1$. These assumptions imply that $p_{\ell +1} \ge p_\ell +2$ if $\ell \ne k$ and $p_{\ell -i} = p_\ell -i$ for each $i \in \{1,\ldots , \ell -1\}.$

Under these assumptions, the edge ideal of ${\mathcal P}$ is

$$\begin{aligned} I({\mathcal P})= (x_1x_2^{w_2}, \ldots , x_{p_\ell -1}x_{p_\ell }^{w_{p_\ell }}, x_{p_\ell }x_{p_\ell +1},x_{p_\ell +1}x_{p_\ell +2}^{w_{p_\ell +2}}, \ldots , x_{n-1}x_n^{w_n}) \end{aligned}$$

where $w_2, \dots , w_{p_\ell } \ge 2$ and $w_{p_{\ell +2}}, \dots , w_{p_n}$ may be anything.

By Lemma 1 and 2, we can bound ${{\,\mathrm{reg}\,}}({\mathcal P})$ from above and below with the following inequalities

$$\begin{aligned}&\max \{ {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell })) , {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell +1}))\} \le {{\,\mathrm{reg}\,}}({\mathcal P}) \\&\quad \le \max \{ {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell })) , {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}):x_{p_\ell }))+1\}. \end{aligned}$$

The remainder of the proof will consist of proving that these upper and lower bounds coincide by showing that ${{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell +1}))= {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}):x_{p_\ell }))+1$. We will then conclude by showing that $\max \{ {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell })) , {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell +1}))\}$ has the desired form.

To see that ${{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell +1}))= {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}):x_{p_\ell }))+1$ note that

$$\begin{aligned} (I({\mathcal P}),x_{p_\ell +1}) = (x_1x_2^{w_2}, \ldots , x_{p_\ell -1}x_{p_\ell }^{w_{p_\ell }})+ (x_{p_\ell +1})+(x_{p_\ell +2}x_{p_\ell +3}^{w_{p_\ell +3}}, \ldots , x_{n-1}x_n^{w_n}) \end{aligned}$$

and

$$\begin{aligned} I({\mathcal P}):x_{p_\ell } = (x_1x_2^{w_2}, \ldots , x_{p_\ell -1}x_{p_\ell }^{w_{p_\ell }-1}) + (x_{p_\ell +1}) + (x_{p_\ell +2}x_{p_\ell +3}^{w_{p_\ell +3}}, \ldots , x_{n-1}x_n^{w_n}). \end{aligned}$$

Since each of these ideals is the sum of three ideals whose generators have disjoint supports, we can calculate their regularities by summing the regularities of the component ideals by Lemma 3. The regularity of $(x_1x_2^{w_2}, \ldots , x_{p_\ell -1}x_{p_\ell }^{w_{p_\ell }})$ and $(x_1x_2^{w_2}, \ldots , x_{p_\ell -1}x_{p_\ell }^{w_{p_\ell }-1})$ can be calculated using Lemma 6, and since the only difference between these ideals is the exponent of $x_{p_\ell }$, it is easy to see that ${{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell +1}))= {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}):x_{p_\ell }))+1$. Thus, ${{\,\mathrm{reg}\,}}({\mathcal P}) = \max \{ {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell })) , {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}), x_{p_\ell +1}))\}$. It remains to show that this maximum is of the form given in the statement of the theorem. To do this we must consider several cases.

Case 1 First suppose that $\ell = k$. In this case, by our assumptions on $\ell$, $p_{i+1}-p_i = 1$ for all $1 \le i \le k-1$ and it is clear that $\displaystyle \max _{\mathbf{q} \in \mathcal {S}} \left\{ \sum (q_1,\ldots , q_t)+{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }+{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }\right\}$ will occur when $(q_1, \dots , q_t) = (p_1, \dots p_k)$. Thus we wish to show that $\displaystyle {{\,\mathrm{reg}\,}}({\mathcal P}) = \sum _{i = 1}^k w_{p_i} + \sum _{i = 1}^{k-1}{\Big \lfloor }\frac{p_{i+1}-p_i}{3}{\Big \rfloor }-k +{\Big \lfloor }\frac{n-p_k}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{p_1+1}{3}{\Big \rfloor }$.

Note that the ideals

$$\begin{aligned} (I, x_{p_k}) = (x_1x_2^{w_2}, \dots , x_{p_k-2}x_{p_k-1}^{w_{p_k-1}})+(x_{p_k})+(x_{p_k+1}x_{p_k+2}, \dots , x_{n-1}x_n) \end{aligned}$$

and

$$\begin{aligned} (I, x_{p_k+1}) = (x_1x_2^{w_2}, \dots , x_{p_k-1}x_{p_k}^{w_{p_k}})+(x_{p_k+1})+( x_{p_k+2}x_{p_k+3}, \dots , x_{n-1}x_n) \end{aligned}$$

are both written as the sum of the edge ideal of a weighted naturally oriented path as in Lemma 6, the edge ideal of a path with trivial weights, and the ideal generated by a variable where the supports of all three ideals are disjoint. We can then use Remark 1, Lemma 6 and Theorem 1 to obtain

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/(I, x_{p_k}))= & {} \sum _{i = 1}^{k-1} w_{p_i}+ {\Big \lfloor }\frac{p_1+1}{3} {\Big \rfloor }-(k-1) + {\Big \lfloor }\frac{n-p_k+1}{3} {\Big \rfloor }\\\le & {} \sum _{i = 1}^{k-1} w_{p_i}+ {\Big \lfloor }\frac{p_1+1}{3} {\Big \rfloor }-k + 1 + {\Big \lfloor }\frac{n-p_k}{3} {\Big \rfloor }+1\\\le & {} \sum _{i = 1}^{k-1} w_{p_i}+ {\Big \lfloor }\frac{p_1+1}{3} {\Big \rfloor }-k + {\Big \lfloor }\frac{n-p_k}{3} {\Big \rfloor }+ w_{p_k}\\= & {} {{\,\mathrm{reg}\,}}(R/(I, x_{p_k+1})). \end{aligned}$$

Therefore, $\displaystyle {{\,\mathrm{reg}\,}}({\mathcal P}) = {{\,\mathrm{reg}\,}}(R/(I, x_{p_k+1})) = \sum _{i = 1}^{k} w_{p_i}+ {\Big \lfloor }\frac{p_1+1}{3} {\Big \rfloor }-k + {\Big \lfloor }\frac{n-p_k}{3} {\Big \rfloor }$ as desired.

Case 2 Now suppose that $1<\ell <k$. Then, this means that $p_2 = p_1+1$ and therefore every maximal element of $\mathcal {S}$ has $p_1$ as it’s first element. In this case,

$$\begin{aligned} (I({\mathcal P}),x_{p_\ell })= (x_1x_2^{w_2}, \ldots , x_{p_\ell -2}x_{p_\ell -1}^{w_{p_\ell -1}})+( x_{p_\ell })+(x_{p_\ell +1}x_{p_\ell +2}^{w_{p_\ell +2}}, \ldots , x_{n-1}x_n^{w_n}) \end{aligned}$$

is the sum of an ideal of the form of Lemma 6 and the edge ideal of a naturally oriented path with fewer than k non-trivial weights. By Lemma 6 and the induction hypothesis, we have

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell }))= & {} \sum _{i=1}^{\ell -1}w_{p_i}+{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }}-(\ell -1)\\+ & {} \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_\ell +2 \end{array}} \left\{ \sum (q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1-p_l+1}{3}}{\Big \rfloor }}\right\} \\= & {} \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_\ell +2 \end{array}} \left\{ \sum (p_1,\ldots , p_\ell -1,q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }} \right\} \\= & {} \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_\ell +2 \end{array}} \left\{ \sum (p_1,\ldots , p_{\ell -1},q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }} \right\} , \end{aligned}$$

where the equalities use the fact that $p_{\ell -1}=p_{\ell }-1$ Similarly,

$$\begin{aligned} (I({\mathcal P}),x_{p_\ell +1}) = (x_1x_2^{w_2}, \ldots , x_{p_\ell -1}x_{p_\ell }^{w_{p_\ell }}) + (x_{p_\ell +1}) + (x_{p_\ell +2}x_{p_\ell +3}^{w_{p_\ell +3}}, \ldots , x_{n-1}x_n^{w_n}) \end{aligned}$$

is also the sum of an ideal of the type in Lemma 6 and the edge ideal of a naturally oriented path with fewer than k non-trivial weights. Thus, again by Lemma 6 and the induction hypothesis,

$$\begin{aligned}&{{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_l+1}))\\&\quad = \sum _{i=1}^{l}w_{p_i}+{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }}-l\\&\qquad + \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_\ell +3 \end{array}} \left\{ \sum (q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1-p_l-1+1}{3}}{\Big \rfloor }} \right\} \\&\quad = \sum _{i=1}^{l}w_{p_i}+{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }}-l+ \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_\ell +3 \end{array}} \left\{ \sum (q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1-p_l}{3}}{\Big \rfloor }} \right\} \\&\quad = \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_\ell +3 \end{array}} \left\{ \sum (p_1,\ldots , p_l,q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }} \right\} . \end{aligned}$$

Observe that for any $\mathbf{q} \in \mathcal {S},$ we must have $q_i= p_i$ for each $1\le i \le \ell -1$ and either $q_\ell =p_\ell$ (which implies that $q_{\ell +1} \ge p_\ell +3$ since our choice of $\ell$ implies that $q_{\ell +1}\ne p_\ell +1$ and the definition of $\mathcal {S}$ then implies that $q_{\ell +1}\ne p_\ell +2$) or $q_{\ell } \ge p_\ell +2$. Hence, the maximal elements of the set $\mathcal {S}$ are contained in the set

$$\begin{aligned}&\left\{ ( p_1,\ldots , p_\ell ,q_1,\ldots , q_t) ~:~\mathbf{q} \in \mathcal {S}, q_1 \ge p_\ell +3 \right\} \\&\quad \cup \left\{ (p_1,\ldots , p_{\ell -1},q_1,\ldots , q_t) ~:~\mathbf{q} \in \mathcal {S}, q_1 \ge p_\ell +2 \right\} \end{aligned}$$

and we deduce that

$$\begin{aligned}&\max \{{{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell })), {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_\ell +1})) \}\\&\quad = \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S} \end{array}} \left\{ \sum (q_1,\ldots q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }} \right\} . \end{aligned}$$

Case 3 Suppose finally that $\ell =1.$ Then, $p_2 \ge p_1+2$ by our assumptions. Then,

$$\begin{aligned} (I({\mathcal P}),x_{p_1}) = (x_1x_2, \ldots , x_{p_1-2}x_{p_1-1}, x_{p_1},x_{p_1+1}x_{p_1+2}^{w_{p_1+2}}, \ldots , x_{n-1}x_n^{w_n}) \end{aligned}$$

and by Lemma 3 and the induction hypothesis

$$\begin{aligned}&{{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_1}))\\&\quad = {{\Big \lfloor }{\frac{p_1-1+1}{3}}{\Big \rfloor }} + \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_1+2 \end{array}} \left\{ \sum (q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1-p_1+1}{3}}{\Big \rfloor }} \right\} \\&\quad = {{\Big \lfloor }{\frac{p_1}{3}}{\Big \rfloor }} + \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_1+2 \end{array}} \left\{ \sum (q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1-p_1+1}{3}}{\Big \rfloor }} \right\} . \end{aligned}$$

Similarly, for the ideal

$$\begin{aligned} (I({\mathcal P}),x_{p_1+1})= (x_1x_2, \ldots , x_{p_1-2}x_{p_1-1}, x_{p_1-1}x_{p_1}^{w_{p_1}}, x_{p_1+1},x_{p_1+2}x_{p_1+3}^{w_{p_1+3}}, \ldots , x_{n-1}x_n^{w_n}) \end{aligned}$$

again by Lemma 3, 5, and the induction hypothesis, we have

$$\begin{aligned}&{{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_1+1})) = w_{p_1}+{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }}-1\\&\qquad + \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_1+3 \end{array}} \left\{ \sum (q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1-p_1-1+1}{3}}{\Big \rfloor }} \right\} \\&\quad = \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_1+3 \end{array}} \left\{ \sum (p_1, q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }} \right\} . \end{aligned}$$

Since $p_2 \ge p_1+2,$ observe that any maximal element $\mathbf{q}$ of $\mathcal {S}$ with $q_1=p_1$ must have $q_2 \ge p_1+3$. Thus, we get

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_1+1}))=\max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 = p_1 \end{array}} \left\{ \sum (q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }} \right\} . \end{aligned}$$

Our goal is to show that the maximum of the above expressions obtained for ${{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_1+1}))$ and ${{\,\mathrm{reg}\,}}(R/(I({\mathcal P}),x_{p_1}))$ is of the desired form. We make the following useful observations to achieve this goal. If $p_2= p_1+2,$ for any $\mathbf{q}= (q_1, \ldots , q_t) \in \mathcal {S}$ where $q_1=p_2,$ observe that

$$\begin{aligned}&{{\Big \lfloor }{\frac{p_1}{3}}{\Big \rfloor }} + \sum \mathbf{q}+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1-p_1+1}{3}}{\Big \rfloor }}\\&\quad = {{\Big \lfloor }{\frac{p_2-2}{3}}{\Big \rfloor }} + \sum (p_2,q_2,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{p_2-p_1+1}{3}}{\Big \rfloor }}\\&\quad = {{\Big \lfloor }{\frac{p_2-2}{3}}{\Big \rfloor }} + \sum (p_2,q_2,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+1\\&\quad = \sum (p_2, q_2,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+ {{\Big \lfloor }{\frac{p_2+1}{3}}{\Big \rfloor }}. \end{aligned}$$

If $p_2> p_1+2,$ then for any $(q_1,\ldots , q_t) \in \mathcal {S}$ where $q_1 > p_1+2,$ we have

$$\begin{aligned}&{{\Big \lfloor }{\frac{p_1}{3}}{\Big \rfloor }} + \sum \mathbf{q}+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1-p_1+1}{3}}{\Big \rfloor }}\\&\quad \le w_{p_1}+ {{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }}-1+ \sum \mathbf{q}+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }} +{{\Big \lfloor }{\frac{q_1-p_1}{3}}{\Big \rfloor }}\\&\quad = \sum (p_1, q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }} +{{\Big \lfloor }{\frac{p_1+1}{3}}{\Big \rfloor }} \end{aligned}$$

since $w_{p_1}\ge 2.$ Therefore, by putting all of the observations together, we see that

$$\begin{aligned} {{\,\mathrm{reg}\,}}({\mathcal P})= & {} \max \left\{ {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}), x_{p_1+1})), {{\,\mathrm{reg}\,}}(R/(I({\mathcal P}), x_{p_1}))\right\} \\= & {} \max \left\{ \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 = p_1 \end{array}} \left\{ \sum \mathbf{q}+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }} \right\} ,\right. \\&\left. \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 \ge p_2 \end{array}} \left\{ {\Big \lfloor }\frac{p_1}{3}{\Big \rfloor }+\sum \mathbf{q} + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{q_1 - p_1+1}{3}{\Big \rfloor }\right\} \right\} \\= & {} \max \left\{ \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 = p_1 \end{array}} \left\{ \sum \mathbf{q}+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }} \right\} , \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 = p_2 \end{array}} \left\{ \sum \mathbf{q}+{{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }}+{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }} \right\} \right\} \\= & {} \max _{\begin{array}{c} \mathbf{q} \in \mathcal {S}\\ q_1 = p_1, p_2 \end{array}} \left\{ \sum \mathbf{q} + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{p_1+1}{3}{\Big \rfloor }\right\} \end{aligned}$$

where $q_1=p_2$ occurs only when $p_2=p_1+2.$

Corollary 4

Let ${\mathcal P}$ be a weighted naturally oriented path on vertices $x_1,\ldots , x_n$ with the weight sequence $(p_1,\ldots , p_k).$ If $p_{i+1}-p_i \ne 2$ for each $i \in \left\{ 1, \ldots , k-1\right\} ,$ then

$$\begin{aligned} {{\,\mathrm{reg}\,}}({\mathcal P})= \sum _{i=1}^k w_{p_i} + \sum _{i=1}^{k-1} {{\Big \lfloor }{\frac{p_{i+1}-p_i}{3}}{\Big \rfloor }}+{\Big \lfloor }{\frac{n-p_k}{3}{\Big \rfloor }} +{\Big \lfloor }{\frac{p_1+1}{3}{\Big \rfloor }}-k \end{aligned}$$

where $k \ge 1.$

Proof

Since $p_{i+1}-p_i \ne 2$ for each $i \in \left\{ 1, \ldots , k-1\right\} ,$ the maximal element under containment of sets in $\mathcal {S}$ is $(p_1,\ldots , p_k)$ and the statement holds by Theorem 7.

Example 7

This example serves to illustrate that changing the positions of the nontrivial weights can change the regularity of the graph. Let ${\mathcal P}_3, {\mathcal P}_4$ be the weighted oriented paths pictured below in Fig. 4 where the two graphs each have three vertices with the same nontrivial weight values but in different positions in the graphs.

Fig. 4

Two paths with the same total weights but different weight sequences

By using the formula in Corollary 4, we can compute ${{\,\mathrm{reg}\,}}({\mathcal P}_3)=7$, while ${{\,\mathrm{reg}\,}}({\mathcal P}_4)=8$. Here, the added distance between the nontrivial weights in ${\mathcal P}_4$ results in the regularity going up by one.

The following lemma is a consequence of the previous theorem and will be used in Section 6. In this lemma, our objects are ideals obtained by taking the sum of an edge ideal of a weighted naturally oriented path on n vertices $x_1,\ldots , x_n$ and monomial ideal $(x_1^{w_1})$ where $w_1>1.$ Even though we introduce the term weight sequence for weighted oriented paths, we can adopt this notion for these special ideals as they can be seen as an extension of edge ideals of weighted oriented paths. Let $I=(x_1^{w_1})+I({\mathcal P})$ be a monomial ideal where $w_1 >1$ and ${\mathcal P}$ is a weighted naturally oriented path. We call $(1=p_1,p_2,\ldots , p_k)$ the weight sequence of the ideal I where $(p_2, \ldots , p_k)$ is the weight sequence of ${\mathcal P}.$ By abusing notation, we can define the set $\mathcal {S}$ in a similar way for these type of ideals. In the next lemma, we again take $\mathbf{q} =(q_1,\ldots , q_t)$ to be a subsequence of $(1=p_1,p_2,\ldots , p_k)$ in $\mathcal {S}.$

Lemma 8

Let $L= (x_1^{w_{1}}, x_{1}x_{2}^{w_{2}}, \ldots , x_{n-1}x_n^{w_n})$ be an ideal in R with the weight sequence $(1=p_1,\ldots , p_k).$ Then, we have

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/L)= \max _{q_1 = 1, 3} \left\{ \sum (q_1,\ldots , q_t)+{\Big \lfloor }{\frac{n-q_t}{3}{\Big \rfloor }}+{\Big \lfloor }{\frac{q_1}{3}{\Big \rfloor }}\right\} . \end{aligned}$$

Proof

Let $L' = (x_0x_1^{w_1-1}, x_1x_2^{w_2}, \dots , x_{n-1}x_n^{w_n})$. Note that L and $L'$ have the same polarization (up to a relabeling vertices) and thus have the same Betti numbers. In particular, ${{\,\mathrm{reg}\,}}(R/L) = {{\,\mathrm{reg}\,}}(R/L')$ and we can use Theorem 7 to calculate the regularity of $R/L'$. The ideal $L'$ is the edge ideal of a weighted naturally oriented path on $n+1$ vertices with weight sequence $p_1+1, \dots , p_k+1$ if $w_1 \ne 2$, and with weight sequence $p_2+1, \dots , p_k+1$ if $w_1 = 2$. We therefore have two cases to consider.

Case 1 Suppose first that $w_1 \ne 2$. Then by Theorem 7, we have

$$\begin{aligned}&{{\,\mathrm{reg}\,}}(R/L') = \max \left\{ \begin{array}{ll} \displaystyle \max _{q_1 =3}\left\{ \sum q + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }\right\} ,\\ \displaystyle \max _{q_1 = 1}\left\{ w_1-1 +\sum _{i = 2}^t w_{q_i}+\sum _{i = 1}^{t-1}{\Big \lfloor }\frac{q_{i+1}-q_i}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }-t\right\} \end{array} \right\} \\&\quad = \max \left\{ \begin{array}{ll} \displaystyle \max _{q_1 =3}\left\{ \sum q + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }\right\} ,\\ \displaystyle \max _{q_1 = 1}\left\{ \sum _{i = 1}^t w_{q_i}+\sum _{i = 1}^{t-1}{\Big \lfloor }\frac{q_{i+1}-q_i}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1-1}{3}{\Big \rfloor }-t\right\} \end{array} \right\} \\&\quad = \max \left\{ \max _{q_1 =3}\left\{ \sum q + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }\right\} ,\max _{q_1 = 1}\left\{ \sum q + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1-1}{3}{\Big \rfloor }\right\} \right\} \\ \end{aligned}$$

Note that if $q_1 = 1$ then ${\Big \lfloor }\frac{q_1 - 1}{3} {\Big \rfloor }= {\Big \lfloor }\frac{q_1}{3}{\Big \rfloor }$ and if $q_1 = 3$ then ${\Big \lfloor }\frac{q_1+2}{3} {\Big \rfloor }= {\Big \lfloor }\frac{q_1}{3}{\Big \rfloor }$. So

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/L') = \max _{q_1 = 1, 3}\left\{ \sum q + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{q_1}{3}{\Big \rfloor }\right\} . \end{aligned}$$

Case 2 Suppose now that $w_1 = 2$. Then, $L'$ is a path of length $n+1$ with weighted sequence $p_2+1, \dots , p_k+1$. By Theorem 7

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/L') = \max _{q_1 = p_2, p_2+2}\left\{ \sum q + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }\right\} \end{aligned}$$

If $(q_1, \dots , q_t) \in S$ with $q_1 \ne 3$ then $(1, q_1, \dots , q_t)$ is in S also. Recalling that in this case $w_1 = 2$, we have

$$\begin{aligned}&\sum _{i = 1}^t w_{q_i}+ \sum _{i = 1}^{t-1} {\Big \lfloor }\frac{q_{i+1}-q_1}{3}{\Big \rfloor }-t + {\Big \lfloor }\frac{n-q_t}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }\\&\quad = \sum _{i = 1}^t w_{q_i}+ \sum _{i = 1}^{t-1} {\Big \lfloor }\frac{q_{i+1}-q_1}{3}{\Big \rfloor }-t + {\Big \lfloor }\frac{n-q_t}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }+ w_1-2\\&\quad = w_1+ \sum _{i = 1}^t w_{q_i}+ \sum _{i = 1}^{t-1} {\Big \lfloor }\frac{q_{i+1}-q_1}{3}{\Big \rfloor }-t + {\Big \lfloor }\frac{n-q_t}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{q_1-1}{3}{\Big \rfloor }-1\\&\quad = w_1+ \sum _{i = 1}^t w_{q_i}+ \sum _{i = 1}^{t-1} {\Big \lfloor }\frac{q_{i+1}-q_1}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{q_1-1}{3}{\Big \rfloor }-(t+1) + {\Big \lfloor }\frac{n-q_t}{3} {\Big \rfloor }+ {\Big \lfloor }\frac{1}{3}{\Big \rfloor }.\\ \end{aligned}$$

Further, if $q_1 = 3$ then, as before, ${\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }= {\Big \lfloor }\frac{q_1}{3}{\Big \rfloor }$. Therefore, we have

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/L')= & {} \max _{q_1 = p_2, p_2+2}\left\{ \sum q + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }\right\} \\= & {} \max _{q_1 = 1, 3}\left\{ \sum q + {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{q_1}{3}{\Big \rfloor }\right\} . \end{aligned}$$

6 Weighted oriented cycles

Our main theorem of this section calculates the regularity of the edge ideal of a weighted naturally oriented cycle and presents a formula similar to the one obtained for weighted naturally oriented paths in Theorem 7. We begin with an analogous setup as in the weighted naturally oriented path case.

Let $\mathcal {C}$ be a weighted naturally oriented cycle on the vertices $x_1,\ldots , x_n$ (in order) with directed edges $(x_1, x_2),$ $(x_2, x_3),$ $\ldots ,(x_{n-1}, x_n), (x_n, x_1)$ such that vertex $x_i$ has weight $w_i$ for each $i \in \{ 1, \ldots , n\}.$ If all the weights of $\mathcal {C}$ are trivial, i.e., $w_i=1$ for each $i \in \{1,\ldots , n\},$ then studying $I(\mathcal {C})$ is the same as studying the edge ideal of the unoriented cycle $I(\mathcal {C})$ for which the regularity is known, as discussed in Theorem 1. Thus, we shall assume that $w_i\ge 2$ for some i.

In contrast to the path case, one has more freedom when it comes to determining the positions of non-trivial weights of a weighted oriented cycle as one can reorder the vertices of the cycle without changing the structure of the graph. Thus, without loss of generality, when the cycle contains at least one non-trivial weight, we assume that $p_1=1$ for the remainder of the paper.

Notation 8

Similar to the path case, our formula for the regularity of the cycle will be given in terms of subsequences of the weight sequence in which no two consecutive entries are distance two apart. Due to the structure of the cycle, we modify the set we previously called $\mathcal {S}$ as follows:

$$\begin{aligned}&\dot{\mathcal {S}}= \{ (q_1,\ldots , q_t) \subseteq (p_1,\ldots , p_k) ~:~ q_{i+1}-q_i \ne 2 \text { for each } i \in \{1, \ldots , t-1\} ,\\&\qquad \quad \text { and }q_t-q_1\ne n-2\}. \end{aligned}$$

We are again using the subset symbol to denote the subsequence relation.

The formula for the regularity of the cycle will be quite similar to that of the path and will include the weight-position sum defined in Definition 6 where instead we take $\mathbf{q}\in \dot{\mathcal {S}}$:

$$\begin{aligned} \sum \mathbf{q}=\sum (q_1,\dots ,q_t):=\sum _{i=1}^tw_{q_i}+\sum _{i=1}^{t-1}{\Big \lfloor }{\frac{q_{i+1}-q_i}{3}}{\Big \rfloor }-t. \end{aligned}$$

(6.1)

The formula for the regularity of the weighted oriented cycle will differ from the weighted oriented path as one needs to take into account the difference between the positions of the first and last non-trivial weights for weighted oriented cycles.

Example 8

Let $\mathcal {C}_1$ and $\mathcal {C}_2$ be weighted oriented cycles as shown in Fig. 5, with the weight sequences (1, 3, 4, 6, 7, 9) and (1, 2, 4, 6, 7, 9), respectively. Denote by $\dot{\mathcal {S}}_1$ and $\dot{\mathcal {S}}_2$ their corresponding sets as defined in Notation 8.

Fig. 5

Two naturally oriented weighted cycles on 10 vertices

Then, the maximal elements with respect to inclusion of $\mathcal {C}_1$ in $\dot{\mathcal {S}}_1$ are

$$\begin{aligned} \{(1,4,7), (1,6,7), (3,4,7), (3,4,9), (3,6,7), (3,6,9)\}. \end{aligned}$$

Note that each of the maximal elements satisfy either $q_1=1,$ or $q_1=3$. On the other hand, the maximal elements of $\mathcal {C}_2$ in $\dot{\mathcal {S}}_2$ are

$$\begin{aligned} \{(1,2,6,7), (1,4,7), (2,6,9), (4,9) \}. \end{aligned}$$

Here, we see that each of the maximal elements satisfies either $q_1=1$ or $q_t=9$. Furthermore, we see how different $\dot{\mathcal {S}}_1$ is from $\dot{\mathcal {S}}_2$ although their weight sequences differ by only one entry.

Theorem 9

Let $\mathcal {C}$ be a weighted naturally oriented cycle on n-vertices $x_1,\ldots , x_n$ with the weight sequence $(p_1,\ldots , p_k).$ Then,

$$\begin{aligned} {{\,\mathrm{reg}\,}}(\mathcal {C}) = \max _{q\in \dot{\mathcal {S}}} \left\{ \sum (q_1,\ldots , q_t)+{{\Big \lfloor }{\frac{n+q_1-q_t}{3}}{\Big \rfloor }} \right\} . \end{aligned}$$

Before we prove the theorem, we begin with a lemma analogous to Lemma 7.

Lemma 9

If $\mathcal {C}$ is a weighted naturally oriented cycle with weight sequence $\mathbf{p}$ and $\mathbf{q}\subseteq \mathbf{q}'\in \dot{\mathcal {S}}$ then

$$\begin{aligned} \sum \mathbf{q}+{{\Big \lfloor }{\frac{n+q_1-q_t}{3}}{\Big \rfloor }}\le \sum \mathbf{q}'+{{\Big \lfloor }{\frac{n+q_1'-q_t'}{3}}{\Big \rfloor }.} \end{aligned}$$

Moreover, we have

$$\begin{aligned} \max _{\mathbf{q}\in \dot{\mathcal {S}}}\left\{ \sum \mathbf{q}+{\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }\right\} =\max _{\begin{array}{c} \mathbf{q}\in \dot{\mathcal {S}}\\ q_1=1\text { or }q_1= 3\\ \text {or }q_t=n-1 \end{array}}\left\{ \sum \mathbf{q}+{\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }\right\} . \end{aligned}$$

(6.2)

Proof

We again first consider the situation with $\mathbf{q}=(q_1,\dots ,q_t)\subseteq (q_1,\dots ,q_j,r,q_{j+1},\dots ,q_t)\in \dot{\mathcal {S}}.$ If $q_1<r<q_t$, then the proof proceeds exactly as in the proof of Lemma 7 so that

$$\begin{aligned} \sum \mathbf{q}+{\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }\le \sum \mathbf{q}'+{\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }. \end{aligned}$$

For the case where $r<q_1$ the proof follows from the fact that ${\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }\le {\Big \lfloor }\frac{n+r-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1-r}{3}{\Big \rfloor }+1.$ Similarly, when $r>q_t$, we have ${\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }\le {\Big \lfloor }\frac{n+q_1-r}{3}{\Big \rfloor }+{\Big \lfloor }\frac{r-q_t}{3}{\Big \rfloor }+1.$

Extending this idea, we again see that the maximum element of $\left\{ \sum \mathbf{q}+{\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }~|~\mathbf{q}\in \dot{\mathcal {S}}\right\}$ will be attained at an element of $\dot{\mathcal {S}}$ of maximal length. Let us now consider when $(q_1,\dots ,q_t)\in \dot{\mathcal {S}}$ is of maximal length. Suppose $q_t\ne n-1$ and $q_1\ne 3$ then we have $(1,q_1,\dots ,q_t)\in \dot{\mathcal {S}}$ as $q_1-1\ne 2$ and $q_t-1\ne n-2.$ Thus, we see that sequence $q\in \dot{\mathcal {S}}$ of maximal length will satisfy $q_1=1$, $q_1=3,$ or $q_t=n-1.$

Example 9

Let $\mathcal {C}_1$ and $\mathcal {C}_2$ be weighted oriented cycles with corresponding sequence sets $\dot{\mathcal {S}}_1$ and $\dot{\mathcal {S}}_2$ as defined in Example 8. These cycles have the same number of vertices, orientation, and total weight sum with their only difference being that the weight of vertex $x_3$ in $\mathcal {C}_1$ is moved to vertex $x_2$ in $\mathcal {C}_2$.

Given $\mathbf{q}=(q_1,\ldots , q_t)\in \dot{\mathcal {S}}_i$ for $i=1,2,$ define $g(\mathbf{q})=\sum \mathbf{q}+{\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor },$ the expression introduced in Lemma 9. For each of the graphs $\mathcal {C}_1$ and $\mathcal {C}_2$, the following tables provides the value of $g(\mathbf{q})$ for each maximal element of $\mathbf{q}\in \mathcal {S}_i$ for $i=1,2$.

$$\begin{aligned} \mathcal {C}_1: ~\begin{array}{r|cccccc} \mathbf{q}&{}(1,4,7) &{} (1,6,7) &{} \mathbf (3,4,7) &{} \mathbf (3,4,9) &{} (3,6,7) &{} (3,6,9) \\ g(\mathbf{q}) &{} 11 &{} 7 &{} \mathbf{12} &{} \mathbf{12} &{} 9 &{} 10 \end{array} \end{aligned}$$

$$\begin{aligned} \mathcal {C}_2: ~\begin{array}{r|cccc} \mathbf{q}&{} (1,2,6,7) &{} \mathbf (1,4,7) &{} (2,6,9) &{} (4,9) \\ g(\mathbf{q}) &{} 10 &{} \mathbf{11} &{} 10 &{} 9 \end{array} \end{aligned}$$

Here, we see that the maximum value of $\sum \mathbf{q}+{\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }$ for $\mathcal {C}_1$ comes from two maximal subsequences, namely (3, 4, 7) and (3, 4, 9). The maximum value of $g(\mathbf{q} )$ comes from the subsequence (1, 4, 7) for $\mathcal {C}_2$. Using Macaulay 2 [6], we see that ${{\,\mathrm{reg}\,}}(\mathcal {C}_1)=12$ and ${{\,\mathrm{reg}\,}}(\mathcal {C}_2)=11$, providing evidence that the regularity of the graphs is given by $g(\mathbf{q})$ which, as in the path case, depends on both the weight sequence and the values of the weights.

We now prove the main theorem of this section.

Proof

of Theorem 9 If $w_i \ge 2$ for all $1\le i \le n,$ then the statement holds from Corollary 1. Suppose that there exists at least one $j \in \{2,\ldots , n\}$ such that $w_j=1.$ Since $k\ge 1,$ we can always find at least one pair of consecutive vertices on the cycle such that one has trivial weight, and the other has nontrivial weight. Without loss of generality, let $x_n,$ and $x_1$ be such a pair with $w_n=1$, and $w_1 \ge 2.$

We proceed by using a Betti splitting to calculate the regularity of the cycle. Taking $i=1$ in the statement of Corollary 3 results with a Betti splitting where $J=(x_nx_1^{w_1})$ and $K=(x_1x_2^{w_2},\ldots , x_{n-2}x_{n-1}^{w_{n-1}}, x_{n-1}x_n)$. Then,

$$\begin{aligned} {{\,\mathrm{reg}\,}}(\mathcal {C})=\max \{w_1, {{\,\mathrm{reg}\,}}(R/K), {{\,\mathrm{reg}\,}}(R/(J\cap K))-1\}. \end{aligned}$$

Our goal is to show that maximum of $w_1,$ ${{\,\mathrm{reg}\,}}(R/K)$, and ${{\,\mathrm{reg}\,}}(R/(J\cap K))-1$ is equal to

$$\begin{aligned} \max _{\begin{array}{c} \mathbf{q}\in \dot{\mathcal {S}}\\ q_1=1 \text { or } q_1 =3\\ \text { or } q_t =n-1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n+q_1-q_t}{3}}{\Big \rfloor }} \right\} . \end{aligned}$$

It can be immediately verified that $J\cap K = J L$ where

$$\begin{aligned} L= {\left\{ \begin{array}{ll} (x_2^{w_2},x_2x_3^{w_3},\ldots ,x_{n-3}x_{n-2}^{w_{n-2}},x_{n-1}) &{}\text{ if } w_2 \ne 1\\ (x_2,x_3x_4^{w_4},\ldots ,x_{n-3}x_{n-2}^{w_{n-2}},x_{n-1}) &{}\text{ if } w_2 =1 \end{array}\right. }. \end{aligned}$$

By Lemma 3, we have

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/(J\cap K))-1= w_1+{{\,\mathrm{reg}\,}}(R/L). \end{aligned}$$

(6.3)

Note at this point we have that ${{\,\mathrm{reg}\,}}(R/(J\cap K))-1\ge w_1$ and thus

$$\begin{aligned} {{\,\mathrm{reg}\,}}(\mathcal {C})=\max \{{{\,\mathrm{reg}\,}}(R/K),{{\,\mathrm{reg}\,}}(R/(J\cap K)-1\}. \end{aligned}$$

We first focus on ${{\,\mathrm{reg}\,}}(R/(J\cap K))-1.$ By Remark 1, we can ignore the single variable generators and compute ${{\,\mathrm{reg}\,}}(R/L)$ by Lemma 8 when $w_2 \ne 1$, i.e., $p_2=2$, and by Theorem 7 when $w_2=1$, i.e., $p_2\ge 3$. Then, by Eq. 6.3, we have

$$\begin{aligned}&{{\,\mathrm{reg}\,}}(R/(J\cap K))-1\\&\quad = w_1+ {\left\{ \begin{array}{ll} \displaystyle \max _{\begin{array}{c} (q_1\dots ,q_t)\in \dot{\mathcal {S}}\\ q_1\ge p_2 \text { and } q_t\ne n-1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n-3-(q_t-1)}{3}}{\Big \rfloor }} +{{\Big \lfloor }{\frac{q_1-1}{3}}{\Big \rfloor }}\right\} &{} \text {if } p_2 =2\\ \displaystyle \max _{\begin{array}{c} (q_1,\dots ,q_t)\in \dot{\mathcal {S}}\\ q_1\ge p_2 \text { and } q_t\ne n-1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n-4-(q_t-2)}{3}}{\Big \rfloor }} +{{\Big \lfloor }{\frac{q_1-2+1}{3}}{\Big \rfloor }}\right\} &{} \text {if }p_2>3\\ \displaystyle \max _{\begin{array}{c} (q_1,\dots ,q_t)\in \dot{\mathcal {S}}\\ q_1\ge p_3 \text { and } q_t\ne n-1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n-4-(q_t-2)}{3}}{\Big \rfloor }} +{{\Big \lfloor }{\frac{q_1-2+1}{3}}{\Big \rfloor }}\right\}&\text {if }p_2 =3 \end{array}\right. }\\&\quad = {\left\{ \begin{array}{ll} \displaystyle \max _{\begin{array}{c} (q_1,\dots ,q_t)\in \dot{\mathcal {S}}\\ q_1\ge p_2 \text { and } q_t\ne n-1 \end{array}} \left\{ w_1+ \sum \mathbf{q}+{\Big \lfloor }\frac{n-2-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_t-1}{3}{\Big \rfloor }\right\} &{} \text {if } p_2\ne 3\\ \displaystyle \max _{\begin{array}{c} (q_1,\dots ,q_t)\in \dot{\mathcal {S}}\\ q_1\ge p_3 \text { and } q_t\ne n-1 \end{array}} \left\{ w_1 +\sum \mathbf{q}+{\Big \lfloor }\frac{n-2-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_t-1}{3}{\Big \rfloor }\right\}&\text {if } p_2= 3 \end{array}\right. } \end{aligned}$$

Note that above expressions of which the maximums are taken are identical. Furthermore, none of the $(q_1, \ldots , q_t) \in \dot{\mathcal {S}}$ over which the maximums are taken can have $q_1 =3$ nor can they have $q_t=n-1,$ which is equivalent to saying $(1,q_1, \ldots , q_t) \in \dot{\mathcal {S}}$. By expanding the weight-sum formula in Equation 6.1 for any $(q_1,\ldots , q_t) \in \dot{\mathcal {S}}$ where $q_1 \ne 3$ and $q_t \ne n-1$ (so that $(1,q_1,\dots ,q_t)\in \dot{\mathcal {S}}$), one can verify the following equality.

$$\begin{aligned}&w_1+\sum (q_1,\ldots , q_t) + {{\Big \lfloor }{\frac{n-2-q_t}{3}}{\Big \rfloor }} +{{\Big \lfloor }{\frac{q_1-1}{3}}{\Big \rfloor }}\nonumber \\&\quad = \sum (1,q_1,\ldots , q_t) +{{\Big \lfloor }{\frac{n+1-q_t}{3}}{\Big \rfloor }} \end{aligned}$$

(6.4)

Thus, we can simplify ${{\,\mathrm{reg}\,}}(R/(J\cap K))-1$ to the following desired form

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/(J\cap K))-1 = \max _{\begin{array}{c} \mathbf{q}\in \dot{\mathcal {S}}\\ q_1=1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n+1-q_t}{3}}{\Big \rfloor }} \right\} . \end{aligned}$$

We now consider ${{\,\mathrm{reg}\,}}(R/K)$. Since K is the edge ideal of a weighted oriented path on n vertices with the weight sequence $(p_2,\ldots , p_k),$ by Theorem 7, we get

$$\begin{aligned} {{\,\mathrm{reg}\,}}(R/K)= \max _{\begin{array}{c} \mathbf{q}\in \dot{\text {S}}\\ q_1 \ge p_2 \end{array}} \left\{ \sum (q_1,\ldots , q_t) + {{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }} +{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }}\right\} \end{aligned}$$

(6.5)

where $q_t = n-1$ is possible.

Next, we show that maximums of the expressions computing ${{\,\mathrm{reg}\,}}(R/K)$ and ${{\,\mathrm{reg}\,}}(R/(J \cap K))-1$ yield the desired form as in the statement of the theorem. In order to do that we consider the following expressions:

$$\begin{aligned}&\sum \mathbf{q}+ {\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }\text { with } q_1=1,\text { and }\\&\sum \mathbf{q}+ {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+ {\Big \lfloor }\frac{q_1+1}{3}{\Big \rfloor }\text { with } q_1\ge p_2 \end{aligned}$$

where $\mathbf{q}\in \dot{\mathcal {S}}$ and $q_t=n-1$ is possible in the second form. Again note that the first expression is already of the desired form. If $q_1\ge p_2$ but $q_t\ne n-1$ then it is possible that $(1,q_1,\dots ,q_t)\in \dot{\mathcal {S}}$ as long as $p_2\ne 3$. In this case, Case 2(a) below, we can directly compare the two expressions and show that the larger of the two is of the desired form. In each of the other cases where the expressions are not directly comparable (Case 1 being $q_t=n-1$ and Case 2(b) being $p_2=3$ with $q_t\ne n-1$), we show that the second expression can also be written in the desired form.

Case 1 Suppose $\mathbf{q}\in \dot{\mathcal {S}}$ such that $q_t=n-1$. In this case, we see that $\displaystyle {\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }={\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }$ and $\displaystyle {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }=0$ giving us

$$\begin{aligned} \sum \mathbf{q}+{\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1+1}{3}{\Big \rfloor }=\sum \mathbf{q}+{\Big \lfloor }\frac{n+q_1-q_t}{3}{\Big \rfloor }. \end{aligned}$$

Case 2 Suppose $\mathbf{q}\in \dot{\mathcal {S}}$ such that $q_t\ne n-1$.

Case 2(a) We first consider the subcase $p_2\ne 3$.

Note that $(q_1,\ldots , q_t) \in \dot{\mathcal {S}}$ where $q_1\ge p_2$ and $q_t \ne n-1$ is equivalent to $(1,q_1,\ldots , q_t) \in \dot{\mathcal {S}}$ and

$$\begin{aligned} \sum \mathbf{q}+ {\Big \lfloor }\frac{n-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1+1}{3}{\Big \rfloor }\le & {} \sum \mathbf{q}+ {\Big \lfloor }\frac{n-q_t+1}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1+2}{3}{\Big \rfloor }\\= & {} \sum \mathbf{q}+ {\Big \lfloor }\frac{n+1-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1-1}{3}{\Big \rfloor }+1 \\\le & {} \sum \mathbf{q}+ {\Big \lfloor }\frac{n+1-q_t}{3}{\Big \rfloor }+{\Big \lfloor }\frac{q_1-1}{3}{\Big \rfloor }+w_1-1\\= & {} \sum ( 1, q_1,\ldots , q_t) + {\Big \lfloor }\frac{n+1-q_t}{3}{\Big \rfloor }\end{aligned}$$

where the last inequality follows from the assumption that $w_1 \ge 2.$

Case 2(b) We next consider the subcase $p_2 =3$. Then, for $(q_1,\ldots , q_t) \in \dot{\mathcal {S}}$ where $q_1 = p_2=3,$ we have

$$\begin{aligned} \sum (q_1,\ldots , q_t) + {{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }} +{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }} = \sum (q_1,\ldots , q_t) + {{\Big \lfloor }{\frac{n+3-q_t}{3}}{\Big \rfloor }}. \end{aligned}$$

All the cases are now completed and we conclude the following:

$$\begin{aligned} {{\,\mathrm{reg}\,}}(\mathcal {C})&= \max \{{{\,\mathrm{reg}\,}}(R/K), {{\,\mathrm{reg}\,}}(R/(J\cap K))-1 \}\\&= \max \left\{ \max _{\begin{array}{c} \mathbf{q}\in \dot{\mathcal {S}}\\ q_1=1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n+1-q_t}{3}}{\Big \rfloor }} \right\} , \max _{\begin{array}{c} q\in \dot{\text {S}}\\ q_1 \ge p_2 \end{array}} \left\{ \sum (q_1,\ldots , q_t) + {{\Big \lfloor }{\frac{n-q_t}{3}}{\Big \rfloor }} +{{\Big \lfloor }{\frac{q_1+1}{3}}{\Big \rfloor }}\right\} \right\} \\&= \max \left\{ \max _{\begin{array}{c} \mathbf{q}\in \dot{\mathcal {S}}\\ q_1=1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n+1-q_t}{3}}{\Big \rfloor }} \right\} , \max _{\begin{array}{c} \mathbf{q}\in \dot{\mathcal {S}}\\ q_t=n-1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n+q_1-q_t}{3}}{\Big \rfloor }} \right\} , \max _{\begin{array}{c} \mathbf{q}\in \dot{\mathcal {S}}\\ q_1=3\\ q_t \ne n-1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n+3-q_t}{3}}{\Big \rfloor }} \right\} \right\} \\&= \max _{\begin{array}{c} \mathbf{q}\in \dot{\mathcal {S}}\\ q_1=1 \text { or } q_1 =3\\ \text { or } q_t =n-1 \end{array}} \left\{ \sum \mathbf{q}+ {{\Big \lfloor }{\frac{n+q_1-q_t}{3}}{\Big \rfloor }} \right\} , \end{aligned}$$

thus completing the proof.

Computer experiments suggest that it is a difficult task to provide a closed formula for the regularity and projective dimension of the edge ideal for an arbitrary weighted oriented graph. All evidence indicates that the positions of the non-trivial weights and the orientation of the graph play essential roles in obtaining formulas for these invariants. Even if we restrict to weighted oriented paths and cycles, but allow any orientation, the problem remains a difficult one.