ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.63088 J. Algebra Comb. Discrete Appl. 4(1) • 23–35 Received: 19 February 2016 Accepted: 12 April 2016 0 Journal of Algebra Combinatorics Discrete Structures and Applications A constructive approach to minimal free resolutions of path ideals of trees Research Article Rachelle R. Bouchat, Tricia Muldoon Brown Abstract: For a rooted tree Γ, we consider path ideals of Γ, which are ideals that are generated by all directed paths of a fixed length in Γ. In this paper, we provide a combinatorial description of the minimal free resolution of these path ideals. In particular, we provide a class of subforests of Γ that are in one-to-one correspondence with the multi-graded Betti numbers of the path ideal as well as providing a method for determining the projective dimension and the Castelnuovo-Mumford regularity of a given path ideal. 2010 MSC: 05E40 Keywords: Betti numbers, Path ideals, Rooted trees, Monomial ideals 1. Introduction Monomial ideals have been studied extensively in the literature and many applications of monomial ideals have been explored. In this paper, we consider a specific class of monomial ideals, known as path ideals. Path ideals are a type of squarefree monomial ideals that are generated in a fixed degree. Edge ideals, a specific class of path ideals, were first studied by Conca and De Negri in [4]. Given a graph Γ = (V,E) having vertex set V and edge set E, we can form the path ideal of length (t− 1) associated to Γ by considering the ideal generated by the monomials corresponding to all (t− 1) length paths in Γ. If V = {x1, . . . ,xn}, this ideal is considered in the polynomial ring R := k[x1, . . . ,xn], where k is a field. In [10], Nagel and Reiner showed in Proposition 6.1 that the Betti numbers of edge ideals of arbitrary graphs can be as complicated as desired. In particular, this proposition implies that the Betti numbers of the edge ideal of an arbitrary graph can depend on the choice of the field, k. For the case of path ideals of directed, rooted trees Bouchat, Há, and O’Keefe showed in Theorem 2.7 of [3] that the Betti Rachelle R. Bouchat; Indiana University of Pennsylvania (email: rbouchat@iup.edu). Tricia Muldoon Brown (Corresponding Author); Armstrong State University (email: patri- cia.brown@armstrong.edu). 23 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 x8 x4 x5 x6 x7 x2 x3 x1 I2(Γ) = (x1x2, x2x4, x4x8, x2x5, x1x3, x3x6, x3x7) I3(Γ) = (x1x2x4, x2x4x8, x1x2x5, x1x3x6, x1x3x7) I4(Γ) = (x1x2x4x8) Figure 1. An example of a graph, Γ, and its associated path ideals numbers of a path ideal associated to a rooted tree are independent of the choice of the field, k. In this paper, we will restrict our focus to the study of path ideals of rooted trees. Recall that a tree is a simple, connected graph containing no loops or multi-edges. Then a rooted tree is a tree together with a fixed vertex, called the root. It is natural to consider a rooted tree as a directed graph in which all edges are assigned the direction going away from the root. It should be noted that xi will denote both the vertex in the graph Γ as well as the monomial in the polynomial ring R. Definition 1.1. Given a directed, rooted tree Γ and t ≥ 2, the path ideal of length (t− 1) of Γ is: It(Γ) := (xi1xi2 · · ·xit | {xi1,xi2, . . . ,xit} forms a directed path in Γ) . Thus, for a given directed, rooted tree Γ there can be more than one path ideal associated to Γ as illustrated in Figure 1. For a given tree Γ, we can successively remove any leaves that occur at level less than (t− 1) when considering the path ideal It(Γ), as these vertices cannot contribute to a minimal generator in It(Γ). A tree that has had successive removal of all leaves ocurring at level less than (t− 1) will be said to be in clean form. The minimal free resolutions of path ideals of trees have been studied by many authors, including Há and Van Tuyl in [7], Katzman in [8], and Kummini in [9]. The basic tools and decompositions that will be used in this paper were introduced by Faridi and Alilooee in [1]. The aim of this paper is to give a constructive description of the multi-graded Betti numbers for path ideals of rooted trees. This constructive description of the Betti numbers corresponding to a path ideal of a rooted tree will also provide a method to compute the projective dimension as well as the Castelnuovo-Mumford regularity. 2. Basic definitions We begin with the background concepts from commutative algebra. Let M be a finitely generated graded S-module. Associated to M is a minimal free resolution, which is of the form 0 → ⊕ a S(−a)βp,a(M) δp−→ ⊕ a S(−a)βp−1,a(M) δp−1−→ ··· δ1−→ ⊕ a S(−a)β0,a(M) → M → 0 where the maps δi are exact and where S(−a) denotes the translation of S obtained by shifting the degree of elements of S by a ∈ (N∪{0})n. The numbers βi,a(M) are called the multi-graded Betti numbers (or Nn-graded Betti numbers) of M, and they correspond to the number of minimal generators of degree a occurring in the ith-syzygy module of M. It should be noted that the graded Betti numbers (or N-graded Betti numbers) of M can be defined as βi,j(M) := ⊕ a1+···+an=j βi,a(M) where a = (a1, . . . ,an). 24 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 There are two invariants corresponding to the minimal free resolution of M which measure the “size” of the resolution. Definition 2.1. Let M be a finitely generated graded S-module. 1. The projective dimension of M, denoted pd(M), is the length of the minimal free resolution asso- ciated to M. 2. The Castelnuovo-Mumford regularity (or regularity), denoted reg(M), is reg(M) := max{j − i | βi,j(M) 6= 0}. We also need the following definitions from simplicial topology. Definition 2.2. 1. An abstract simplicial complex, ∆, on a vertex set X = {x1, . . . ,xn} is a collection of subsets of X satisfying: (a) {xi}∈ ∆ for all i, and (b) F ∈ ∆, G ⊂ F =⇒ G ∈ ∆. The elements of ∆ are called faces of ∆, and the maximal faces (under inclusion) are called facets of ∆. The simplicial complex ∆ with faces F1, . . . ,Fs will be denoted by 〈F1, . . . ,Fs〉. 2. If ∆ is an abstract simplicial complex, then a face τ ∈ ∆ is called a free face if it is contained in a unique facet of ∆. 3. For any Y ⊆ X, an induced subcollection of ∆ on Y, denoted by ∆Y, is the simplicial complex whose vertex set is a subset of Y and whose facet set is given by {F | F ⊆Y and F is a facet of ∆}. 4. If F is a face of ∆ = 〈F1, . . . ,Fs〉, the complement of F in ∆ is given by FcX = X \F and ∆cX = 〈(F1) c X , . . . , (Fs) c X〉. It should be noted that if F1, . . . ,Fs are facets in Definition 2.2(1), then 〈F1, . . .Fs〉 is a minimal representation of ∆. In particular, the complementary complex ∆cX , described in the fourth part of Definition 2.2, is heavily utilized within this paper. Definition 2.3. 1. Let ∆ be a simplicial complex with vertex set x1, . . . ,xn. Then the facet ideal of ∆ is defined as I(∆) := (∏ x∈F x | F is a facet of ∆ ) . Moreover, I is an ideal in the polynomial ring R := k[x1, . . . ,xn]. 2. Let I be an ideal in R := k[x1, . . . ,xn] minimally generated by square-free monomials m1, . . . ,ms. The facet complex ∆(I) associated to I has vertex set {x1, . . . ,xn} and is defined by ∆(I) := 〈F1, . . . ,Fs〉 where Fi = {xj | xj|mi , 1 ≤ j ≤ n} for 1 ≤ i ≤ s. 25 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 The above constructions provide a one-to-one correspondence between simplicial complexes on the vertex set {x1, . . . ,xn} and the square-free monomial ideals in R := k[x1, . . . ,xn]. We illustrate this construction with the following example. Example 2.4. Consider the path ideal I3(Γ) = (x1x2x3,x2x3x4,x2x3x5) associated to the tree, Γ, pic- tured below. Then the facet complex associated to Γ with respect to t = 3 is ΓcVert(Γ) = 〈(x1x2x3) c Vert(Γ), (x2x3x4) c Vert(Γ), (x2x3x5) c Vert(Γ)〉 = 〈x4x5,x1x5,x1x4〉 x4 x3 x2 x1 x5 x5 x1 x4 Γ Γc Vert(Γ) The dimension of the reduced homology group of the complementary complex of a path ideal is instrumental in determining the Betti numbers of the corresponding minimal free resolution. We will use a corollary of Theorem 2.8 of Alilooee and Faridi in [1] to help determine the multi-graded Betti numbers for path ideals of rooted trees. This corollary, found below, appears in [2] as Corollary 2.11. Corollary 2.5. Let S = k[x1, . . . ,xn] be a polynomial ring over a field k, and let I be a pure, squarefree monomial ideal in S. Then the multi-graded Betti numbers of I are given by βi,a(I) = dimk H̃i−1 ( ΓcVert(Γ) ) for i ≥ 1 where Γ is an induced subcollection of ∆(I) with Vert(Γ) = {xi | ai = 1} where a = (a1, . . . ,an). It should be noted that the Betti numbers β0,a(I) correspond to the minimal generating set of I. Finally, we will rely upon Lemma 4.1 in [1] of Alilooee and Faridi, which is a tool that allows us to determine the ith reduced homology group of the complementary complex using the (i − 1)st reduced homology group of a smaller complex, which we call the deleted complementary complex, that is, Lemma 2.6 ([Lemma 4.1, Alilooe and Faridi]). Suppose Γ is a tree generated by the paths P1,P2, . . . ,Pk and suppose P1 ∩ (P2 ∪P3 ∪·· ·∪Pk) 6= ∅. Then dimk H̃i (〈Pc1 ,P c 2 , . . . ,P c k〉) = dimk H̃i−1 ( 〈(P2)cVert(Γ)\P1, (P3) c Vert(Γ)\P1, . . . , (Pk) c Vert(Γ)\P1〉 ) . It should further be noted that in Corollary 6.1 of [5], it is shown that the independence complex of graph forests are simple-homotopy equivalent to a vertex or to a sphere. Thus by Corollary 2.5, the multi-graded Betti numbers of path ideals of directed, rooted trees correspond via simple-homotopy equivalence to a vertex or to a sphere. We conclude this section with some graph theoretic definitions before stating our three line graph constructions on directed, rooted trees. Definition 2.7. Let Γ be a rooted tree with root x and vertex set Vert(Γ), and let y ∈ Vert(Γ). 1. The level of y, denoted level(y), is the length of the unique path in Γ from x to y. The height of Γ is the maximal level over all vertices in Γ. 2. The parent vertex of the non-root vertex y is the unique vertex z such that yz forms an edge in Γ and level(z) = level(y) − 1. 26 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 3. A subgraph H of Γ is called an induced subgraph if for every pair of vertices x,y ∈ H the following condition holds: if {x,y} is an edge of Γ, then it is also an edge of H. Now we can define the essential constructions for this paper. Starting with a tree Γ which is composed of generating paths of length (t− 1) in the set {P1,P2, . . . ,Pk}, we assume ΓcVert(Γ) is not contractible, that is, there exists an i ≥ 0 for which dimk H̃i ( Γc Vert(Γ) ) = 1. We create a new tree Γ′ such that all edges and vertices of Γ are also contained in Γ′ as follows. Definition 2.8. Let Γ be a tree with vertex set Vert(Γ)and edge set E(Γ) and assume the vertex set {y1,y2, . . . ,yt+1}∩ Vert(Γ) = ∅. 1. Let Γ′ be the tree whose vertex set is Vert(Γ′) = Vert(Γ) ∪{y1,y2, . . . ,yt+1} and whose edge set is E(Γ′) = E(Γ)∪{(x0,yt+1), (yt+1,yt), (yt,yt−1), . . . , (y2,y1)} for some vertex x0 ∈ Vert(Γ). We say Γ′ is a glue of Γ. 2. Let Γ′ be the tree whose vertex set is Vert(Γ′) = Vert(Γ) ∪{y1,y2, . . . ,yn} for some 1 ≤ n ≤ t and whose edge set is E(Γ′) = E(Γ) ∪{(x0,yn), (yn,yn−1), (yn−1,yn−2), . . . , (y2,y1)} for some vertex x0 ∈ Vert(Γ). If level(y1) = level(x`) for at least one leaf vertex x` ∈ Γ which lies on a directed path from x0, we say Γ′ is a split of Γ. 3. Let Γ′ be the tree whose vertex set is Vert(Γ′) = Vert(Γ) ∪{y1,y2, . . . ,yn} for some 1 ≤ n ≤ t and whose edge set is E(Γ′) = E(Γ) ∪{(x0,yn), (yn,yn−1), (yn−1,yn−2), . . . , (y2,y1)} for some vertex x0 ∈ Vert(Γ). If level(y1) 6= level(x`) for at least one leaf vertex x` ∈ Γ which lies on a directed path from x0, we say Γ′ is a contraction of Γ. Remark 2.9. We will also use the terms glue and split as constructions on the empty graph. Consider t ≥ 2. Starting with the empty graph, a split will result in the line graph having exactly t vertices, and a glue from the empty graph will result in the line graph having exactly t+ 1 vertices. It should be noted that adding less than t new vertices to the empty graph will result in a graph having no minimal generators for the ideal It(Γ). Definition 2.8 along with Lemma 2.6 will allow us to begin with a tree whose complementary complex is homotopic to a sphere in some dimension, adjoin a line graph, and consequently determine the homotopy type of the resulting complementary simplicial complex of the modified tree. In particular, we will show that these three cases, glue, split, and contraction, are the only needed constructions and consequently the new simplicial complex will be homotopic to a sphere in either one or two dimensions higher, or it will be contractible. 3. Constructions and Betti numbers In this section, we will explore how a glue, split, and contraction of a directed graph Γ will determine the non-zero Betti number of top dimension in the corresponding minimal free resolution of the path ideal of the newly constructed graph, Γ′ and consequently will determine the projective dimension. When we create a new tree, Γ′, from Γ by adding n new vertices {y1,y2, . . . ,yn} through a glue, split, or contraction, at most n new generating paths of length (t − 1) will be added to the path ideal of It(Γ); depending on the level of the vertex y1. Let Ei be the unique directed path of length (t − 1) which terminates in vertex yi for 1 ≤ i ≤ j where j = min{level(y1) − t + 2,n}. The number j of new generating paths depends on the level of x0 in the tree Γ and the number of vertices added, as there may not exist a path of length (t− 1) which terminates in vertex yi. Thus Γ′ is generated by the paths {P1, . . . ,Pk,E1, . . . ,Ej}. In each of the following cases we consider the deleted complementary complex that was described in Section 2. Since E1 always contains a leaf of Γ′, the conditions of Lemma 2.6 are satisfied and Γ′ c Vert(Γ′)\E1 = 〈(P1) c Vert(Γ′)\E1, . . . , (Pk) c Vert(Γ′)\E1, (E2) c Vert(Γ′)\E1, . . . , (Ej) c Vert(Γ′)\E1〉. 27 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 We begin with the case of a glue. Proposition 3.1. Let Γ be a tree in clean form with respect to t ≥ 2 such that there exists i ≥ 0 for which βi,a(It(Γ)) = 1, where a = (a1, . . . ,am) and aj = 1 if and only if xj ∈ Γ. Let Γ′ be a glue of Γ, then βi+2,a′(It(Γ ′)) = 1 where a′ = (a1, . . . ,am+t+1) and aj = 1 if and only if xj ∈ Γ′. Before the proof, we illustrate the deletion methods of Lemma 2.6 in the case of a glue with the following example. Example 3.2. Consider the tree Γ1, occurring as a glue of Γ: x4 x3 x1 x5 y4 y3 y2 y1 x2 Then using the deletion method of Lemma 2.6, we set E1 = {y1,y2,y3}, E2 = {y2,y3,y4}, E3 = {x2,y3,y4}, E4 = {x1,x2,y4}, E5 = {x1,x2,x3}, E6 = {x2,x3,x4}, and E7 = {x2,x3,x5}. It follows that: dimk H̃i ( (Γ1) c Vert(Γ1) ) = dimk H̃i−1〈(E2)cVert(Γ1)\E1, . . . , (E7) c Vert(Γ1)\E1〉 = dimk H̃i−1〈x1x2x3x4x5,x1x3x4x5,x3x4x5,x4x5y4,x1x5y4,x1x4y4〉 = dimk H̃i−1〈x1x2x3x4x5,x4x5y4,x1x5y4,x1x4y4〉 After identifying the vertices x2 and x3, the simplicial complex can be visualized as, x1 x4 x2x3 x5 y4 where the tetrahedron labeled by x1x2x3x4x5 is solid, but the tetrahedron labeled by x1x4x5y4 is hol- low. Thus dimk H̃2(〈x1x2x3x4x5,x4x5y4,x1x5y4,x1x4y4〉) = 1, and thus, by Lemma 2.6, we have dimk H̃3 ( (Γ1) c Vert(Γ1) ) = 1. 28 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 Proof of Proposition 3.1. Let Γ′ be a glue of the tree Γ in clean form with respect to t ≥ 2 such that there exists i ≥ 0 for which βi,a(It(Γ)) = 1, where a = (a1, . . . ,am) and ai = 1 if and only if xi ∈ Γ. Further, let E1,E2, . . . ,Ej be the new generating paths of length t−1 that are in Γ′ but not in Γ, where E1 is the directed path E1 = yt . . .y2y1. To proceed, we will delete the path E1 and apply Lemma 2.6. First, the sole vertex in the set Vert(E2) \ Vert(E1) is yn, so 〈(E2)cVert(Γ′)\E1〉 = 〈(yn) c Vert(Γ′\E1)〉. Further yn is a vertex contained in every generating path E3,E4, . . .Ej, thus 〈(yn)cVert(Γ′\E1)〉 contains 〈(Ei)cVert(Γ′)\E1〉 for all 3 ≤ i ≤ j. Therefore, Γ′ c Vert(Γ′)\E1 = 〈(P1) c Vert(Γ′)\E1, . . . , (Pk) c Vert(Γ′)\E1, (yn) c Vert(Γ′\E1)〉. We observe, for all 1 ≤ i ≤ k, the complex 〈(Pi)cVert(Γ′\E1)〉 is equal to the simplicial join 〈(Pi)cVert(Γ) ∗yn〉, and thus yn must be a vertex of the simplex 〈(Pi) c Vert(Γ′)\E1〉. Therefore the complex 〈(P1)cVert(Γ′)\E1, . . . , (Pk) c Vert(Γ′)\E1〉 is exactly the cone of yn over Γ c Vert(Γ) . In particular, because of our as- sumption of a non-zero Betti number in dimension i ≥ 0, there exists a union of faces of Γc Vert(Γ) that is ho- motopic to an i-dimensional sphere, and thus the simplicial complex 〈(P1)cVert(Γ′)\E1, . . . , (Pk) c Vert(Γ′)\E1〉 is homotopic to a cone over an i-dimensional sphere. The complex 〈(yn)cVert(Γ′\E1)〉 is the simplex whose vertices are all the vertices in Vert(Γ). Any vertex in Vert(Γ) that in not contained in the resulting i-dimensional sphere is a free face of the complex Γc Vert(Γ) as well as of the complex Γ′cVert(Γ′)\E1, and hence can be collapsed into the face not containing the vertex yn. In particular it can be retracted to the face whose boundary is contained in the union of faces of Γc Vert(Γ) that is homotopic to an i-dimensional sphere. Therefore Γ′cVert(Γ′)\E1 is homotopic to the cone over an open i-dimensional sphere which has been filled with the simplex 〈(yn)cVert(Γ′\E1)〉, thus creating a sphere of dimension i. We now have dimk H̃i+1((Γ ′)cVert(Γ′)) = dimk H̃i((Γ ′)cVert(Γ′)\E1 ) = 1. Then the complex (Γ′)c Vert(Γ′) is homotopic to a sphere of dimension i + 1; that is, of dimension two more than the sphere describing the complementary complex of Γ and further βi+2,a′(It(Γ ′)) = 1 where a′ = (a1, . . . ,am′) and ai = 1 if and only if xi ∈ Γ′. Next, we consider the split construction from a given tree. Proposition 3.3. Let Γ be a tree in clean form with respect to t ≥ 2 such that there exists i ≥ 0 for which βi,a(It(Γ)) = 1, where a = (a1, . . . ,am) and aj = 1 if and only if xj ∈ Γ. Let Γ′ be a split of Γ, then βi+1,a′(It(Γ ′)) = 1 where a′ = (a1, . . . ,am′) and aj = 1 if and only if xj ∈ Γ′. As before, we illustrate the deletion methods of Lemma 2.6 in the case of a split with the following example before providing the proof. Example 3.4. Consider the tree Γ2, occuring as a split of Γ: x4 x3 x1 x5 y2 y1 x2 29 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 Using the deletion method, we set E1 = {x2,y1,y2}, E2 = {x1,x2,y2}, E3 = {x1,x2,x3}, E4 = {x2,x3,x4}, and E5 = {x2,x3,x5}. It follows that dimk H̃i ( (Γ2) c Vert(Γ2) ) = dimk H̃i−1〈(E2)cVert(Γ2)\E1, . . . , (E5) c Vert(Γ2)\E1〉 = dimk H̃i−1〈x3x4x5,x4x5,x1x5,x1x4〉 = dimk H̃i−1〈x3x4x5,x1x5,x1x4〉. The complex can be visualized as: x5 x1 x4x3 Hence dimk H̃1(〈x3x4x5,x1x5,x1x4〉) = 1, and by Lemma 2.6 dimk H̃2 ( (Γ2) c Vert(Γ2) ) = 1. Proof of Proposition 3.3. Let Γ be a tree in clean form such that βi,a(It(Γ)) = 1 for some i ≥ 0 where a = (a1, . . . ,am) and ai = 1 if and only if x ∈ Vert(Γ), and let Γ′ be a split of Γ. Then Γ′ is formed from Γ by attaching a line graph with vertices yn, . . . ,y1 where n ≤ t via the edge {x0,yn} for some x0 ∈ Vert(Γ). Further there exists a leaf vertex x` of Γ that is on a directed path from x0 such that level(x`) = level(y1). Let Ei be the length t− 1 path in Γ′ terminating at vertex yi while P1, . . . ,Pk will denote the paths of length t− 1 in Γ. If E1 ∩ Vert Γ = ∅, the result follows directly from Lemma 2.6. Suppose to the contrary, and let x be a vertex in the intersection of E1 and Vert(Γ). We note for any 1 ≤ i ≤ k, if x ∈ (Pi)cVert(Γ), then x` ∈ (Pi)cVert(Γ). This is because level(x`) − level(x) ≤ t, so all paths containing x` must also contain x. Thus every face in Γc Vert(Γ) containing x must also contain x`. Hence, vertex x is a free vertex in the complex Γc Vert(Γ) which may be retracted onto x`, and the complex ΓcVert(Γ) is collapsed onto the complex 〈(P1)cVert Γ′\E1, . . . , (Pk) c Vert Γ′\E1〉⊆ (Γ ′)c Vert(Γ′\E1). As retractions preserve homotopy, we have ΓcVert(Γ) ∼〈(P1) c Vert Γ′\E1, . . . , (Pk) c Vert Γ′\E1〉. If Γ′ only contains one additional path when compared to Γ, then the paths making up Γ′ are E1,P1, . . . ,Pk. It follows that βi+1,a′ (It(Γ ′)) = dimk H̃i ( (Γ′)cVert(Γ′) ) = dimk H̃i−1 ( 〈(P1)cVert Γ′\E1, . . . , (Pk) c Vert Γ′\E1〉 ) where a′ = (a1, . . . ,am′) such that ai = 1 if and only if xi ∈ Γ′. It follows that βi,a (It(Γ)) = dimk H̃i−1 ( (Γ)cVert(Γ) ) = 1 and hence the claim is proven. Now assume that Γ′ contains two or more new paths when compared to Γ. It follows that βi+1,a′ (It(Γ ′)) = dimk H̃i ( (Γ′)c Vert(Γ′) ) = dimk H̃i−1 ( 〈(E2)cVert Γ′\E1, . . . , (Ej) c Vert Γ′\E1, (P1) c Vert Γ′\E1, . . . , (Pk) c Vert Γ′\E1〉 ) . Let x′ denote the sole vertex in the set Vert(E2) − Vert(E1). Then (E2)cVert(Γ′)\E1 = (x ′)c Vert(Γ′)\E1. Furthermore, notice that (Ei)cVert(Γ′)\E1 ⊆ (E2) c Vert(Γ′)\E1 for all 3 ≤ i ≤ j. Hence, βi+1,a′ (It(Γ ′)) = dimk H̃i−1 ( 〈(x′)cVert Γ′\E1, (P1) c Vert Γ′\E1, . . . , (Pk) c Vert Γ′\E1〉 ) . 30 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 Furthermore, because the complex 〈(P1)cVert Γ′\E1, . . . , (Pk) c Vert Γ′\E1〉 is just the complex formed by re- tracting the vertices in Vert(E1) ∩ Vert(Γ) onto the leaf vertex x` in the complex ΓcVert(Γ), it is left to check that the face (x′)c Vert(Γ′)\E1 of (Γ ′)c Vert(Γ′\E1) does not close the i-dimensional hole that we know by assumption is in Γc Vert(Γ) . Suppose to the contrary, when the simplex (x′)c Vert(Γ′)\E1 is inserted in the complex 〈(P1)cVert Γ′\E1, . . . , (Pk) c Vert Γ′\E1〉, the newly formed complex (Γ ′)c Vert(Γ′\E1) is contractible. First observe that the height of the subtree rooted at x′ is t. We first assume that Γ′ has exactly two leaves, x` and y1 on directed paths from x′. Therefore, without loss of generality, we assume the directed path from x′ to x` was glued onto some subtree of Γ whose leaves are all at a level less than level(x`). We know from the proof of Proposition 3.1 that in this case, the vertex x′ is on the boundary of the complex homotopic to the i-dimensional sphere formed by the glue. Hence, x′ is not a free vertex and cannot be retracted onto another vertex in the complex. Therefore, the simplex (x′)c Vert(Γ′)\E1 cannot fill this hole and the thus the complex (Γ′)c Vert(Γ′\E1) is not contractible. By extension, if Γ ′ has more than two leaves on directed paths from x′, each additional split still has a face determined by the complement of x′, and hence the complex cannot be contractible. In the final proposition of this section, we consider a contraction of a given tree. Proposition 3.5. Let Γ be a tree in clean form with respect to t ≥ 2 such that there exists i ≥ 0 for which βi,a(It(Γ)) = 1, where a = (a1, . . . ,am) and aj = 1 if and only if xj ∈ Γ. Let Γ′ be a contraction of Γ, then βi,a′(It(Γ ′)) = 0 for all i where a′ = (a1, . . . ,am′) and aj = 1 if and only if xj ∈ Γ′. We precede the proof with an example illustrating the deletion methods of Lemma 2.6 in the case of a contraction. Example 3.6. Consider the tree Γ3, occurring as a contraction of Γ: x4 x2 x1 x5 y2 y1 x3 Then using the deletion method, we set E1 = {x3,y1,y2}, E2 = {x2,x3,y2}, E3 = {x1,x2,x3}, E4 = {x2,x3,x4}, and E5 = {x2,x3,x5}. It follows that: dimk H̃i ( (Γ3) c Vert(Γ3) ) = dimk H̃i−1〈(E2)cVert(Γ3)\E1, . . . , (E5) c Vert(Γ3)\E1〉 = dimk H̃i−1〈x1x4x5,x4x5,x1x5,x1x4〉 = dimk H̃i−1〈x1x4x5〉 The complex can be visualized as: x5 x1 x4 31 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 Notice that dimk H̃i(〈x1x4x5〉) = 0 for all i. Hence, by Lemma 2.6 βi,a (It(Γ)) = 0 for all i. Proof of Proposition 3.5. Let Γ be a tree in clean form with respect to t ≥ 2 such that there exists i ≥ 0 for which βi,a(It(Γ)) = 1, where a = (a1, . . . ,am) and ai = 1 if and only if xi ∈ Γ and let Γ′ be a contraction of Γ, also in clean form. (If Γ′ is not in clean form, the vertices lying on the paths of length less than t− 1 do not contribute to the minimal free resolution and hence trivially βi,a’(It(Γ′)) = 0 for all i where a′ = (a1, . . . ,am′) and ai = 1 if and only if xi ∈ Γ′.) Assume E1,E2, . . . ,Ej are the new paths of length (t−1) found in Γ′ but not in Γ. In this final case, we still assume 1 ≤ n ≤ t, but now let level(y1) 6= level(x) for all leaf vertices x of Γ which lie on a directed path from x0. First we look at the situation where level(y1) < level(x`) for some leaf vertex x`. As before we want to apply Lemma 2.6, but this time we delete the path P = xtxt−1 · · ·x1 which terminates at the leaf x` ∈ Γ which is on a directed path from x0. Let xt+1 be the unique parent vertex of the initial vertex xt of the path P , which must exist because Γ′ is in clean form. Then xt+1xt · · ·x2 = Pm was a generating path of Γ for some m, and so 〈(Pm)cVert(Γ′)\P〉 = 〈(xt+1) c Vert(Γ′)\P〉 is a part of the deleted complementary complex Γ′ c Vert(Γ′)\P = 〈(P1) c Vert(Γ′)\P , . . . , (Pk) c Vert(Γ′)\P , (E1) c Vert(Γ′)\P , . . . , (Ej) c Vert(Γ′)\P〉. Any other generating paths that contain xt+1, will have complementary complexes contained in the simplex 〈(xt+1)cVert(Γ′)\P〉, and because level(y1) < level(x1), this includes all of the new generators E1,E2, . . . ,Ej, so Γ′ c Vert(Γ′)\P = 〈(P1) c Vert(Γ′)\P , . . . , (Pk) c Vert(Γ′)\P〉. Now, the vertex y1 is a vertex of the simplex 〈xct+1〉, but y1 is also a vertex of every simplex generated from the original paths Pc1 ,P c 2 , . . . ,P c k in Γ. Thus (Γ ′)c Vert(Γ′)\P is homotopic to a cone of the vertex y1 over some simplicial complex and hence is contractible. On the other hand, if the level of y1 is greater than the level of some leaf vertex x`, apply Lemma 2.6 and delete the unique path E1 of length t−1 terminating at y1. In this final situation, we must be careful of the case where x0 is a leaf. If x0 is not a leaf, as above, let xt+1 be the parent of the initial vertex of the path E1. Proceeding as before we see Γ′ c Vert(Γ′)\E1 = 〈(P1) c Vert(Γ′)\E1, . . . , (Pk) c Vert(Γ′)\E1〉 and that 〈(Pm)cVert(Γ′)\E1〉 = 〈(xt+1) c Vert(Γ′)\P〉 for some m. This time x` is a vertex of the simplex 〈(xt+1)cVert(Γ′)\P〉 as well as of every other simplex 〈(Pj) c Vert(Γ′)\E1〉 not contained in 〈(xt+1) c Vert(Γ′)\P〉. Therefore (Γ′)c Vert(Γ′)\E1 is a cone over the vertex x`, and thus is contractible. If x0 is a leaf, then y1y2 · · ·yn is a part of a longer line graph containing x0. In this case the attachment of this longer line graph should be considered as whole: as either a glue or a contraction with a different attaching vertex x0 which is not a leaf. In the final section, we state our main result and apply the constructions above to an example, completely determining the Betti numbers of the minimal free resolution of its path ideal. 4. Minimal free resolutions We observe, any tree Γ′ can be constructed from one of its subtrees, Γ, through a sequence of line graph attachments. Therefore, we only need to consider the situation where Γ′ differs from Γ by exactly one line graph. If the line graph consists of an attachment of more than t + 1 vertices, we further decompose the attachment into a sequence of some number of glues as well as possibly either a split or a contraction. We will also impose order on the creation of Γ′ such that when a new line graph is adjoined, the level of x0 (i.e. the level of the glue, split, or contraction) is greater than ht(Γ) − t. Thus, under this 32 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 model, any directed graph Γ′ containing the directed graph Γ as a subgraph, could have been created from Γ through a sequence of glues, splits, and contractions. By extension and given the conventions of a glue and split to an empty graph, any clean graph can be created from a sequence of glues, splits, and contractions starting with an empty graph for some t ≥ 2. As the empty graph trivially satisfies the conditions on Propositions 3.1, 3.3, and 3.5, we have that all clean, directed graphs can be constructed from a sequence of glues, splits, and contractions. Given a subforest Λ of Γ, let g(Λ) and s(Λ) denote the number of glues and splits, respectively, required to construct Λ from an empty graph. Then we have the following theorem. Theorem 4.1. Let Γ be a directed, rooted tree, and let t ≥ 2. Then βi,a (It(Γ)) = 1 precisely when {xj | aj 6= 0} corresponds to the vertex set of an induced subforest, Λ, of Γ constructed from the empty graph by a sequence of only glues and splits. Moreover, in this case i = 2g(Λ) + s(Λ) − 1. Proof. Since multigraded Betti numbers correspond to induced subforests of Γ, the result follows immediately from Propositions 3.1, 3.3, and 3.5. We illustrate Theorem 4.1 with an example. Example 4.2. Consider the tree Γ depicted below. The graded minimal free resolution of I3(Γ) is also provided below and was obtained using Macaulay 2 (see [6]). x1 x2 x3 x4 x5 x6 x8x7 x9 x10 I3(Γ) = (x1x2x3,x2x3x5,x3x5x7,x3x5x8,x5x7x10,x1x2x4,x2x4x6,x4x6x9) 0 → R3(−8) → R(−5) ⊕ R(−6) ⊕ R8(−7) → R8(−4) ⊕ R(−5) ⊕ R5(−6) → R8(−3) → I3(Γ) → 0 The Betti numbers, β0,3(I3(Γ)) correspond to all paths in Γ of length 2, which are all induced sub- forests of Γ formed as a split from the empty graph. The Betti numbers, β1,j(I3(Γ)), correspond to all induced subtrees of Γ formed either by two splits from the empty graph or by one glue from the empty graph. Hence, these Betti numbers correspond to induced subforests of Γ of the following form: Two Splits Two Splits Two Splits One Glue (2 of this type) (1 of this type) (5 of this type) (6 of this type) The Betti numbers, β2,j(I3(Γ)), correspond to all induced subforests of Γ formed either by three splits from the empty graph or by one glue and one split from the empty graph. 33 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 One Glue & One Split One Glue & One Split One Glue & One Split One Glue & One Split (1 of this type) (1 of this type) (2 of this type) (1 of this type) One Glue & One Split One Glue & One Split Three Splits (1 of this type) (3 of this type) (1 of this type) Lastly, the Betti numbers, β3,j(I3(Γ)), correspond to all induced subforests of Γ formed from either four splits, from one glue and two splits, or from two glues. The only possible induced subforests of these types in Γ are depicted below: One Glue & Two Splits Two Glues Two Glues (1 of this type) (1 of this type) (1 of this type) It should be noted that the vertex sets of the induced subforests correspond to the multi-graded Betti numbers in the minimal free resolution of I3(Γ). Theorem 4.1 also implicitly describes the projective dimension and regularity of the It(Γ). We have the following corollaries. Corollary 4.3. Let Γ be a directed, rooted tree and let t ≥ 2, and let C := {Λ | Λ is an induced subforest of Γ constructible from the empty graph using only splits and glues}. Then the projective dimension of It(Γ) is given by pd(It(Γ))) = max{2g(Λ) + s(Λ) | Λ ∈C}− 1. and the Castelnuovo-Mumford regularity of It(Γ) is given by reg(It(Γ)) = max{|Vert(Λ)|− (2g(Λ) + s(Λ)) | Λ ∈C} + 1. 34 R. Bouchat, T. M. Brown / J. Algebra Comb. Discrete Appl. 4(1) (2017) 23–35 References [1] A. Alilooee, S. Faridi, On the resolution of path ideals of cycles, Commun. Algebra 43(12) (2015) 5413–5433. [2] R. R. Bouchat, T. M. Brown, Multi–graded Betti numbers of path ideals of trees, to appear in J. Algebra Appl. [3] R. Bouchat, A. O’Keefe, H. Tài Hà, Path ideals of rooted trees and their graded Betti numbers, J. Combin. Theory Ser. A 118(8) (2011) 2411–2425. [4] A. Conca, E. De Negri, M–sequences, graph ideals, and ladder ideals of linear type, J. Algebra 211(2) (1999) 599–624. [5] R. Ehrenborg, G. Hetyei, The topology of the independence complex, European J. Combin. 27(6) (2006) 906–923. [6] D. Grayson, M. E. Stillman, Macaulay 2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/. [7] H. Tài Hà, A. Van Tuyl, Monomial ideals, edge ideals of hyper graphs, and their graded Betti numbers, J. Algebraic Combin. 27(2) (2008) 215–245. [8] M. Katzman, Characteristic–independence of Betti numbers of graph ideals, J. Combin. Theory Ser. A 113(3) (2006) 435–454. [9] M. Kummini, Regularity, depth and arithmetic rank of bipartite edge ideals, J. Algebraic Combin. 30(4) (2009) 429–445. [10] U. Nagel, V. Reiner, Betti numbers of monomial ideals and shifted skew shapes, Electron. J. Combin. 16(2) (2009) 1–59. 35 http://dx.doi.org/10.1080/00927872.2013.837170 http://dx.doi.org/10.1080/00927872.2013.837170 http://dx.doi.org/10.1142/S0219498817500189 http://dx.doi.org/10.1142/S0219498817500189 http://dx.doi.org/10.1016/j.jcta.2011.06.007 http://dx.doi.org/10.1016/j.jcta.2011.06.007 http://dx.doi.org/10.1006/jabr.1998.7740 http://dx.doi.org/10.1006/jabr.1998.7740 http://dx.doi.org/10.1016/j.ejc.2005.04.010 http://dx.doi.org/10.1016/j.ejc.2005.04.010 http://www.math.uiuc.edu/Macaulay2/ http://www.math.uiuc.edu/Macaulay2/ http://dx.doi.org/10.1007/s10801-007-0079-y http://dx.doi.org/10.1007/s10801-007-0079-y http://dx.doi.org/10.1016/j.jcta.2005.04.005 http://dx.doi.org/10.1016/j.jcta.2005.04.005 http://dx.doi.org/10.1007/s10801-009-0171-6 http://dx.doi.org/10.1007/s10801-009-0171-6 http://www.ams.org/mathscinet-getitem?mr=2515766 http://www.ams.org/mathscinet-getitem?mr=2515766 Introduction Basic definitions Constructions and Betti numbers Minimal free resolutions References