Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Monomial Ideals of Graphs with Loops

Monomial Ideals of Graphs with Loops We investigate, using the notion of linear quotients, significative classes of connected graphs whose monomial edge ideals, not necessarily squarefree, have linear resolution, in order to compute standard algebraic invariants of the polynomial ring related to these graphs modulo such ideals. Moreover we are able to determine the structure of the ideals of vertex covers for the edge ideals associated to the previous classes of graphs which can have loops on any vertex. Lastly, it is shown that these ideals are of linear type. Mathematics Subject Classification 2010: 05C25, 05E40, 13A30, 13C15. Key words: graphs with loops, linear quotients, ideals of vertex covers, ideals of linear type. Introduction In [8] it was first shown how some algebraic properties related to remarkable classes of graphs hold when appropriate loops are put. In this article we are interested in studying standard algebraic properties of monomial ideals arising from the edges of some graphs, the so-called edge ideals, and exposing situations for which such properties are preserved when we add loops to them. The generators of ideals of vertex covers for the edge ideals associated to graphs with loops are also examined, proving that these ideals are of linear type. Let G be a graph on n vertices v1 , . . . , vn . An algebraic object attached to G is the edge ideal I(G), a monomial ideal of the polynomial ring in n variables R = K[X1 , . . . , Xn ], K a field. When G is a loopless graph, I(G) is generated by squarefree monomials of degree two in R, I(G) = {Xi Xj | {vi , vj } is an edge of G } , but if G is a graph having loops {vi , vi }, among the generators of I(G) there are also non-squarefree monomials Xi2 , i = 1, . . . , n. For a relevant class of connected graphs with loops we prove that their edge ideals have linear resolution, by using the technique of studying the linear quotients of such ideals, as previously employed in [9]. More precisely, it is examined a wide class of squarefree edge ideals associated to the connected graphs H, on n vertices, consisting of the union of a complete graph Km , m < n, and star graphs with centers the vertices of Km . By adding loops on some vertices of Km , we introduce a new class of non-squarefree edge ideals associated to the connected graphs K = H {vj , vj }, for some j = 1, . . . , m . We prove that I(H) and I(K) have linear resolution. We also give formulae for standard invariants of R/I(H) and R/I(K) such as dimension, projective dimension, depth, CastelnuovoMumford regularity. In [7] the computation of such invariants is made for the symmetric algebras of subclasses of squarefree edge ideals generated by s-sequences associated to G. Some algebraic aspects linked to the minimal vertex covers for such classes of graphs can be considered. Keeping in mind the one to one correspondence between minimal vertex covers of any graph and minimal prime ideals of its edge ideal, we generalize to a graph with loops the notion of ideal of (minimal) vertex covers and determine the structure of the ideals of vertex covers Ic (H) and Ic (K ) for the classes of edge ideals associated to H and K = H {vi , vi }, for some i = 1, . . . , n . We may observe that K is larger than K because loops on K stay also on vertices that don't belong to Km . Moreover we prove that the symmetric and the Rees algebras of Ic (H) and Ic (K ) over R are isomorphic, namely such ideals are of linear type. The work is subdivided as follows. In section 1 the classes of graphs H, K and their edge ideals are analyzed. In particular, starting from H, we introduce K and consider its edge ideal whose ordered generators are X1 Xm+1 , X1 Xm+2 , ..., X1 Xm+i1 , X1 X2 , X2 Xm+i1 +1 , . . . , X2 Xm+i1 +i2 , X2 X3 , X1 X3 , X3 Xm+i1 +i2 +1 , ..., X3 Xm+i1 +i2 +i3 , X3 X4 , X2 X4 , 2 2 X1 X4 , ..., Xm Xm+i1 +...+im-1 +1 , ..., Xm Xm+i1 +...+im , Xt1 , . . . , Xtl , where {t1 , . . . , tl } {1, . . . , m} and n = m + i1 + . . . + im . According to results that characterize monomial ideals with linear quotients ([2, 4]), it is shown that the edge ideals of H and K have linear resolution. As an application, standard algebraic invariants are calculated. In section 2 we examine the structure of the ideals of vertex covers for the classes of edge ideals associated to H and K using the description of the ideals of vertex covers for the edge ideals associated to the complete graphs and the star graphs that make them up. We remark that the ideal of vertex covers of I(K ), when K has loops on all its n vertices, has the unique generator X1 · · · Xm · · · Xn . In section 3 we investigate the Rees algebra of Ic (H) and Ic (K ). We recall that if I = (f1 , . . . , fs ) is an ideal of R, the Rees algebra (I) of i I is defined to be the R-graded algebra i 0 I . Let : R[T1 , . . . , Ts ] (I) = R[f1 t, . . . , fs t] be an epimorphism of graded R-algebras defined by (Ti ) = fi t , i = 1, . . . , s , and N = ker be the ideal of presentation of (I). If N is generated by linear relations, namely R-homogeneous elements of degree 1, then I is said of linear type. Several classes of ideals of R of linear type are known. For instance, ideals generated by d-sequences and M -sequences are of linear type ([1, 6, 10]). We show that the ideals of vertex covers Ic (H) and Ic (K ) are of linear type. 1. Linear resolutions and invariants Let R = K[X1 , . . . , Xn ] be the polynomial ring in n variables over a field K with deg Xi = 1, for all i = 1, . . . , n. For a monomial ideal I R we denote by G(I) its unique minimal set of monomial generators. Definition 1.1. A vertex cover of a monomial ideal I R is a subset C of {X1 , . . . , Xn } such that each u G(I) is divided by some Xi C. The vertex cover C is called minimal if no proper subset of C is a vertex cover of I. Let h(I) denote the minimal cardinality of the vertex covers of I. Definition 1.2. A monomial ideal I R is said to have linear quotients if there is an ordering u1 , . . . , ut of monomials belonging to G(I) with deg(u1 ) ··· deg(ut ) such that the colon ideal (u1 , . . . , uj-1 ) : (uj ) is generated by a subset of {X1 , . . . , Xn }, for 2 j t . Remark 1.1. A monomial ideal I of R generated in one degree that has linear quotients admits a linear resolution ([2], Lemma 4.1). For a monomial ideal I of R having linear quotients with respect to the ordering u1 , . . . , ut of the monomials of G(I), let qj (I) denote the number of the variables which is required to generate the ideal (u1 , . . . , uj-1 ) : (uj ) , and set q(I) = max2 j t qj (I). Remark 1.2. The integer q(I) is independent on the choice of the ordering of the generators that gives linear quotients ([5]). In this section we study classes of monomial ideals generated in degree two arising from graphs that have linear quotients, that is equivalent to say that they have linear resolution ([4]). Let's introduce some preliminary notions. Let G be a graph and V (G) = {v1 , . . . , vn } be the set of its vertices. We put E(G) = {{vi , vj }|vi = vj , vi , vj V (G)} the set of edges of G and L(G) = {{vi , vi }| vi V (G)} the set of loops of G. Hence {vi , vj } is an edge joining vi to vj and {vi , vi } is a loop of the vertex vi . Set W (G) = E(G) L(G). If L(G) = , the graph G is said simple or loopless, otherwise G is a graph with loops. A graph G on n vertices v1 , . . . , vn is complete if there exists an edge for all pairs {vi , vj } of vertices of G. It is denoted by Kn . If V (G) = {v1 , . . . , vn } and R = K[X1 , . . . , Xn ] is the polynomial ring over a field K such that each variable Xi corresponds to the vertex vi , the edge ideal I(G) associated to G is the ideal {Xi Xj | {vi , vj } W (G)} R . Note that the non-zero edge ideals are those generated by monomials of degree 2. This implies that I(G) is a graded ideal of R of initial degree 2, that is I(G) = i 2 (I(G)i ) . If W (G) = , then I(G) = (0) . First it is examined a relevant wide class of squarefree edge ideals associated to connected graphs H on n vertices, consisting of the union of a complete graph Km , m < n, and star graphs in the vertices of Km . More precisely, H = Km starj (k), where Km is the complete graph on m vertices v1 , . . . , vm , m < n, and starj (k) is the star graph on k vertices with center vj , for some j = 1, . . . , m, k n-m. One has: I(H) = (X1 Xm+1 , X1 Xm+2 , . . . , X1 Xm+i1 , X1 X2 , X2 Xm+i1 +1 , X2 Xm+i1 +2 , . . . , X2 Xm+i1 +i2 , X2 X3 , X1 X3 , X3 Xm+i1 +i2 +1 , X3 Xm+i1 +i2 +2 , . . . , X3 Xm+i1 +i2 +i3 , X3 X4 , X2 X4 , X1 X4 , . . . , Xm Xm+i1 +i2 +···+im-1 +1 , Xm Xm+i1 +i2 +···+im-1 +2 , . . . , Xm Xm+i1 +i2 +···+im-1 +im ) R. |G(I(H))| = i1 + i2 + · · · + im + m(m-1) . 2 Proposition 1.1. I(H) has a linear resolution. Proof. I(H) is the edge ideal of the graph H with n = m+i1 +i2 +· · ·+ im vertices and = i1 +i2 +· · ·+im + m(m-1) = n-m+ m(m-1) = n+ m(m-3) 2 2 2 edges. Set f1 , . . . , f the squarefree monomial generators of I(H). It results: (f1 ) : (f2 ) = (Xm+1 ), (f1 , f2 ) : (f3 ) = (Xm+1 , Xm+2 ), ..................................., (f1 , . . . , fi1 -1 ) : (fi1 ) = (Xm+1 , Xm+2 , . . . , Xm+i1 -1 ), (f1 , . . . , fi1 ) : (fi1 +1 ) = (Xm+1 , Xm+2 , . . . , Xm+i1 ), (f1 , . . . , fi1 +1 ) : (fi1 +2 ) = (X1 Xm+1 , X1 Xm+2 , . . . , X1 Xm+i1 , X1 ) = (X1 ), (f1 , . . . , fi1 +2 ) : (fi1 +3 ) = (X1 , Xm+i1 +1 ), ..................................., (f1 , . . . , fi1 +i2 +1 ) : (fi1 +i2 +2 ) = (X1 , Xm+i1 +1 , . . . , Xm+i1 +i2 ), (f1 , . . . , fi1 +i2 +2 ) : (fi1 +i2 +3 ) = (Xm+1 , Xm+2 , . . . , Xm+i1 , X2 ), (f1 , . . . , fi1 +i2 +3 ) : (fi1 +i2 +4 ) = (X2 , X1 ), ..................................., (f1 , . . . , fi1 +i2 +i3 +2 ):(fi1 +i2 +i3 +3 )=(X2 , X1 , Xm+i1 +i2 +1 , . . . , Xm+i1 +i2 +i3 ), and so on up to (f1 , . . . , f-1 ) : (f ) = (X1 , . . . , Xm-1 , Xm+i1 +i2 +···+im-1 +1 , . . . , Xm+i1 +i2 +···+im -1 ). Hence I(H) has linear quotients. According to results in [4] about monomial ideals with linear quotients, it follows that the edge ideal I(H) has a linear resolution. Remark 1.3. R. Fr¨berg proved that the edge ideal of a simple graph o has a linear resolution if and only if its complementary graph is chordal ([4], Theorem 9.2.3). By using such a characterization, it is possible to show that the edge ideal I(H) of Proposition 1.1 has a linear resolution. The study of the linear quotients is useful in order to investigate algebraic invariants of R/I(H): the dimension, dimR (R/I(H)), the depth, depth(R/I(H)), the projective dimension, pdR (R/I(H)) and the Castelnuovo-Mumford regularity, regR (R/I(H)). Lemma 1.1. Let R=K[X1 , . . . , Xn ] and I(H) R. Then h(I(H))=m. Proof. The minimal cardinality of the vertex covers of I(H) is h(I(H)) = m, being C = {X1 , . . . , Xm } a minimal vertex cover of I(H) by construction. Lemma 1.2. Let R = K[X1 , . . . , Xn ] and I(H) R. Then: q(I(H)) = m + max ij - 2 . 1 j m Proof. By the computation of the linear quotients (Proposition 1.1), the maximum number of the variables which is required to generate the ideal (f1 , . . . , fh-1 ) : (fh ), for h = 1, . . . , , is given by (m - 1) + max1 j m ij - 1. It follows that q(I(H)) = m + max1 j m ij - 2 . Theorem 1.1. Let R = K[X1 , . . . , Xn ] and I(H) R. Then: 1) dimR (R/I(H)) = n - m . 2) pdR (R/I(H)) = m + max1 j m ij - 1. j m ij 3) depthR (R/I(H)) = n - m - max1 4) regR (R/I(H)) = 1 . + 1. Proof. 1) One has dimR (R/I(H)) = dimR R - h(I(H)) ([3]). Hence, by Lemma 1.1 , dimR (R/I(H)) = n - m . 2) The length of the minimal free resolution of R/I(H) over R is equal to q(I(H))+1 ([5], Corollary 1.6). Then pdR (R/I(H)) = m+max1 j m ij -1. 3) As a consequence of 2), by Auslander-Buchsbaum formula, one has depthR (R/I(H)) = n - pdR (R/I(H)) = n - m - max1 j m ij + 1. 4) I(H) has a linear resolution, then regR (R/I(H)) = 1. Starting from the class of edge ideals associated to H and adding loops on some vertices of Km , we now analyze a larger class of non-squarefree edge ideals associated to connected graphs K = H {vj , vj }, for some j = 1, . . . , m . Let K be the connected graph with n vertices v1 , . . . , vn and Km , m < n, be the complete subgraph of K with vertices v1 , . . . , vm , such that I(K) = X1 Xm+1 , X1 Xm+2 , . . . , X1 Xm+i1 , X1 X2 , X2 Xm+i1 +1 , X2 Xm+i1 +2 , . . . , X2 Xm+i1 +i2 , X2 X3 , X1 X3 , X3 Xm+i1 +i2 +1 , X3 Xm+i1 +i2 +2 , . . . , X3 Xm+i1 +i2 +i3 , X3 X4 , X2 X4 , X1 X4 , . . . , Xm Xm+i1 +i2 +···+im-1 +1 , Xm Xm+i1 +i2 +···+im-1 +2 , . . . , 2 2 Xm Xm+i1 +i2 +···+im-1 +im , Xt1 , . . . , Xtl R = K[X1 , . . . , Xn ], with {t1 , . . . , tl } {1, . . . , m} and n = m + i1 + · · · + im . |G(I(K))| = n - (m - l) + m(m-1) . 2 Taking in account the notion of linear quotients, it is proved that the edge ideal I(K) has still a linear resolution. Proposition 1.2. I(K) has a linear resolution. Proof. I(K) is the edge ideal of the graph K with n = m+i1 +i2 +· · ·+im vertices, = i1 + i2 + · · · + im + m(m-1) = n - m + m(m-1) = n + m(m-3) 2 2 2 edges and l m loops {vt1 , vt1 }, . . . , {vtl , vtl }. Set f1 , . . . , f , f+1 , . . . , f+l the monomial generators of I(K), of which the last l are not squarefree. The ideals (f1 , . . . , fh-1 ) : (fh ), for h = 1, . . . , , have been computed in Proposition 1.1. Moreover, it results: (f1 , . . . , f ) : (f+1 ) = (X2 , . . . , Xm , Xm+1 , . . . , Xm+i1 ), if v1 has a loop, (f1 , . . . , f ) : (f+1 ) = (X1 , . . . , Xt1 -1 , Xt1 +1 , . . . , Xm , Xm+i1 +...+it1 -1 +1 , . . . , Xm+i1 +...+it1 -1 +it1 ), if {vt1 , vt1 } = {v1 , v1 }; ..................................., (f1 , . . . , f+l-1 ):(f+l )=(X1 , . . . , Xtl -1 , Xtl +1 , . . . , Xm , Xm+i1 +...+itl -1 +1 , . . . , Xm+i1 +...+itl -1 +itl ), if {vtl , vtl } = {vm , vm }, (f1 , . . . , f+l-1 ) : (f+l ) = (X1 , . . . , Xm-1 ,m+i1 +...+im-1 +1 , . . . , Xm+i1 +...+im ), if vm has a loop. Hence I(K) has linear quotients, that is equivalent to say that I(K) has a linear resolution ([4]). The study of the linear quotients as in Proposition 1.2 is useful in order to investigate algebraic invariants of R/I(K). Lemma 1.3. Let R = K[X1 , . . . , Xn ] and I(K) R. Then: h(I(K)) = m . Proof. The minimal cardinality of the vertex covers of I(K) is h(I(K)) = m, being C={X1 , . . ., Xm } a minimal vertex cover of I(K) by construction. Lemma 1.4. Let R = K[X1 , . . . , Xn ] and I(K) R. Then: q(I(K)) = m + max ij - 1, µ t1 j tµ m. Proof. By the computation of the linear quotients (Proposition 1.2), the maximum number of the variables which is required to generate the ideal (f1 , . . . , fk-1 ) : (fk ), for k = 1, . . . , + µ, µ m, is given by (m - 1) + max t1 j tµ ij . It follows that q(I(K)) = m + max t1 j tµ ij - 1 . Theorem 1.2. Let R = K[X1 , . . . , Xn ] and I(K) R. Then: 1) dimR (R/I(K)) = n - m . 2) pdR (R/I(K)) = m + max t1 4) regR (R/I(K)) = 1 . Proof. 1) One has dimR (R/I(K)) = dimR R - h(I(K)) ([3]). Hence, by Lemma 1.3 , dimR (R/I(K)) = n - m . 2) The length of the minimal free resolution of R/I(K)) over R is equal to q(I(K))+1 ([5], Corollary 1.6). Then pdR (R/I(K)) = m+max t1 j tµ ij , µ m. 3) As a consequence of 2), by Auslander-Buchsbaum formula, one has depthR (R/I(K)) = n - pdR (R/I(K)) = n - m - max t1 j tµ ij , µ m. 4) I(K) has a linear resolution, then regR (R/I(K)) = 1. Remark 1.4. When the graph K has at least a loop on a vertex that don't belong to Km , then its edge ideal has not linear quotients. In fact, it can be verified there is no ordering of the monomials f1 , . . . , fs G(I(K)) , s = n - (m - l) + m(m-1) , such that (f1 , . . . , fj-1 ) : (fj ) is gen2 erated by a subset of {X1 , . . . , Xn }, for 2 j s. 2. Ideals of vertex covers Definition 2.1. Let G be a graph with vertex set V (G) = {v1 , . . . , vn }. A subset C of V (G) is said a minimal vertex cover for G if: (1) every edge of G is incident with one vertex in C; (2) there is no proper subset of C with this property. If C satisfies condition (1) only, then C is called a vertex cover of G and C is said to cover all the edges of G. The smallest number of vertices in any minimal vertex cover of G is said vertex covering number. We denote it by 0 (G). We consider some algebraic aspects linked to the minimal vertex covers of a graph G with set of edges E(G) and set of loops L(G). Let I(G)=({Xi Xj |{vi , vj }W (G)=E(G) L(G)}) be the edge ideal associated to G. A loop {vi , vi }L(G), such that vi belongs to a vertex cover of G, can be thought to have a double covering that preserves the minimality. j tµ ij , µ j tµ m. ij , µ m. 3) depthR (R/I(K)) = n - m - max t1 There exists a one to one correspondence between the minimal vertex covers of G and the minimal prime ideals of I(G). In fact, is a minimal prime ideal of I(G) if and only if =(C), for some minimal vertex cover C of G ([11], Prop. 6.1.16). Hence ht (I(G))=0 (G). Thus the primary decomposition of the edge ideal of G is given by I(G) = (C1 ) · · · (Cp ), where C1 , . . . , Cp are the minimal vertex covers of G. Definition 2.2. Let I R = K[X1 , . . . , Xn ] be a monomial ideal. The ideal of (minimal) covers of I, denoted by Ic , is the ideal of R generated by all monomials Xi1 · · · Xik such that (Xi1 , . . . , Xik ) is an associated (minimal) prime ideal of I. If I(G) is the edge ideal of a graph G, we call Ic (G) the ideal of vertex covers of I(G). Property 2.1. Ic (G) = i=j (Xi , Xj ) Xk | {vk , vk } L(G), k = i, j . {vi ,v }E(G) j We want to examine the structure of the ideals of vertex covers for the class of squarefree edge ideals associated to H. In the sequel, we rename v1 , . . . , vm the vertices of the complete graph Km , 1 1 < 2 < . . . < m = n, and 1 = 1 if there is not the star graph with center v1 . The following two lemmas give explicitly the generators of the ideals of vertex covers for the edge ideals of a complete graph and a star graph, respectively. Their proofs are an easy application of Property 2.1 . Lemma 2.1. The ideal of vertex covers of I(Km ) is generated by m monomials and it is Ic (Km ) = (X2 X3 · · · Xm , X1 X3 · · · Xm , . . . , X1 X2 · · · Xm-1 ). Lemma 2.2. The ideal of vertex covers of I(starj (k)) is generated by two monomials, namely X1 · · · Xj-1 Xj+1 · · · Xk , Xj . Let's study the structure of the ideal of vertex covers of I(H) when at least a vertex of Km has degree m - 1. Proposition 2.1. Let H be the connected graph with n vertices v1 , . . . , vn formed by the union of a complete graph Km , m < n, with vertices v1 , . . . , vm , 1 1 < 2 < . . . < m = n, and of a star graph star1 (1 ) on vertices v1 , . . . , v1 , or a star graph stari (i - i-1 ) with center vi , for some i = 2, . . . , m . The ideal of vertex covers Ic (H) has m monomial squarefree generators and it is: (X1 ··· X1 -1 X2 ··· Xm , X1 X3 ··· Xm , . . . , X1 ··· Xm-1 ), if i = 1, (X2···Xm , . . . , X1···Xi-1 Xi-1 +1···Xi+1 -1 Xi+1···Xm , . . . , X1···Xm-1 ), otherwise. Proof. Because of the one to one correspondence between minimal vertex covers of a graph and minimal prime ideals of its edge ideal, for the complete graph Km it follows that I(Km ) = m Pi , where Pi = i=1 (X1 , . . . , Xi-1 , Xi+1 , . . . , Xm ). The vertex covers of the graph H will be: · m - 1 vertex covers of Km , but {v1 , . . . , vi-1 , vi+1 , . . . , vm }, by Lemma 2.1; · two vertex covers related to stari (i -i-1 ), {v1 , . . . , vi-1 , vi-1 +1 , . . . , vi+1 -1 , vi+1 , . . . , vm }, {v1 , . . . , vm }, for some i = 1 , as a consequence of Lemma 2.2 . For the last ones, let Pi =(X1 , . . . , Xi-1 , Xi-1 +1 , . . . , Xi+1 -1 , Xi+1 , . . . , Xm ), P = (X1 , . . . , Xm ), respectively, be the associated minimal prime ideals but P Pj , j = i. So I(H) = P1 . . . Pi-1 Pi Pi+1 . . . Pm . On the other hand, it is clear what P1 denotes. Hence the thesis follows. Remark 2.1. Proposition 2.1 can be generalized by considering two or more star graphs with centers as many vertices of Km . It is sufficient to iterate that procedure for each pair of vertex covers related to the star graphs which are present. Finally, let's consider the structure of the ideal of vertex covers of I(H) when all the vertices of Km have degree at least m. Theorem 2.1. Let H be the connected graph with n vertices v1 , . . . , vn formed by the union of a complete graph Km , m < n, with vertices v1 , . . . , vm , 1 < 1 < 2 < . . . < m = n, and of m star graphs with centers each of the vertices of Km . The ideal of vertex covers of I(H) has m + 1 monomial squarefree generators and it is Ic (H) = X1 X2 ··· Xm , X1 ··· X1 -1 X2 ··· Xm , X1 X1 +1 ··· X2 -1 X3 ··· Xm , . . . , X1 ··· Xm-2 Xm-2 +1 ··· Xm-1 -1 Xm , X1 ··· Xm-1 Xm-1 +1 ··· Xm -1 . Proof. A minimal vertex cover of H must be {v1 , . . . , vm } and there cannot exist minimal vertex covers with a smaller number of vertices. So 0 (H) = m. Other minimal vertex covers of H are those related to star graphs on 1 and i - i-1 vertices, star1 (1 ) and stari (i - i-1 ) respectively, for any i = 2, . . . , m , in which the centers are missing. With the notations of Proposition 2.1, let P = (X1 , . . . , Xm ), P1 = (X1 , . . . , X1 -1 , X2 , . . . , Xm ), Pi = (X1 , . . . , Xi-1 , Xi-1 +1 , . . . , Xi -1 , Xi+1 , . . . , Xm ), for any i = 2, . . . , m , be the associated minimal prime ideals. Then I(H) = P ( m Pi ) , and ht I(H) = m . Thus i=1 Ic (H) = X1 · · · Xm , X1 · · · X1 -1 X2 · · · Xm , . . . , X1 · · · Xm-1 Xm-1 +1 · · · Xm -1 , and the thesis follows. Example 2.1. Let H be the connected graph with V (H) = {v1 , . . . , v4 , . . . , v11 } given by K4 star1 (2) star2 (4) star3 (2) star4 (3) . The ideal of vertex covers is Ic (H) = (X1 X2 X3 X4 , X2 X3 X4 X5 , X1 X3 X4 X6 X7 X8 , X1 X2 X4 X9 , X1 X2 X3 X10 X11 ). Let's now analyze the structure of the ideals of vertex covers for the class of non-squarefree edge ideals associated to the connected graphs on n vertices K = H {vi , vi }, for some i = 1, . . . , n . Note that the class K is larger than K because K may have loops on vertices that don't belong to Km . First let's enunciate two lemmas that give the generators of the ideals of vertex covers for the edge ideals of a complete graph with loops and a star graph with loops, respectively. Their proofs are a direct consequence of Property 2.1 . Lemma 2.3. Let Km be the complete graph with loops having vertices v1 , . . . , vm . The ideal of vertex covers of I(Km ) is generated at most by m - 1 monomials. In particular, (a) if there are loops in all the vertices, Ic (Km ) = (X1 X2 · · · Xm ), (b) if there are loops in r<m vertices, vt1 , . . . , vtr , {t1 , . . . , tr }{1, . . . , m}, Ic (Km ) has m-r generators and it is {X1 · · ·Xm-1 | j = tj , j = 1, . . . , r; i {1, . . . , m}\ {t1 , . . . , tr }, i = j} . Lemma 2.4. Let star (n) be the star graph with loops having vern tices v1 , . . . , vn . The ideal of vertex covers of I(star (n)) has at most 2 n generators. In particular, (a) if the loops are in the vertices v1 , . . . , vn-1 , Ic (star (n))=(X1 · · · Xn-1 ), n (b) if the loops are in v3 , vn-2 , Ic (star (n)) = (X1 · · · Xn-1 , X3 Xn-2 Xn ), n (c) if there are loops in the center and in the vertices vt1 , . . ., vts , {t1 , . . ., ts } {1, . . . , n-1}, Ic (star (n)) = (Xt1 · · · Xts Xn ). n The structure of the ideal of vertex covers of I(K ) is well described by the following: Theorem 2.2. Let K be the connected graph with n vertices v1 , . . . , vn formed by the union of: (i) the complete graph Km , m < n, with vertices v1 , . . . , vm , 1 1 < 2 < . . . < m = n ; (ii) star graphs stari (i -i-1 ) on vertices vi-1 +1 , . . . , vi , i=1, . . . , m, and the index 0 indicates 0 ; (iii) loops in some vertices, say v2 , v4 , v5 , vm-3 , vm-1 , vi-1 +j1 , . . . , vi-1 +jpi , where {j1 , . . . , jpi } {1, . . . , i -i-1 -1} . The ideal of vertex covers of I(K ) has at most m + 1 monomial generators and it is Ic (K ) = Xj1 ··· Xjp1 X1 X1 +j1 ··· X1 +jp2 X2 X2 +j1 ··· Xm-1 +jpm Xm , X1 ··· X1 -1 X1 +j1 ··· X1 +jp2 X2 X2 +j1 ··· Xm-1 +jpm Xm , Xj1 ··· Xjp1 X1 X1 +1 ··· X2 -1 X2 X2 +j1 ··· Xm-1 +jpm Xm , . . . , Xj1 ··· Xm-3 +jpm-2 Xm-2 Xm-2 +1 ··· Xm-1 -1 Xm-1 Xm-1 +j1 ··· Xm-1 +jpm Xm , Xj1 ··· Xm-2 +jpm-1 Xm-1 Xm-1 +1 ··· Xm -1 . Proof. The correspondence between minimal vertex covers of the graph H and minimal prime ideals of the edge ideal of H extends to the graph K . So the number of minimal prime ideals of I(K ) is the same than that of minimal primes of I(H). Moreover, by Property 2.1, the generators of the prime ideals are those related to H multiplied by monomials Xi whenever Xi , i = 1, . . . , n. The latter monomials represent the vertices with loops / of K for which the corresponding variables are missing in . The assertion holds through some computation taking in consideration Theorem 2.1. Significative particular cases concern the graphs of the class such that: (a) some star graphs are missing, (b) the loops lie only on the vertices of Km , and (c) the loops lie only on the vertices not belonging to Km . Corollary 2.1. Let K be as in Theorem 2.2, but there are in it less than m star graphs stari (i - i-1 ), suppose for i = 2, 3, 6, m-3, m-2, m . The ideal of vertex covers of I(K ) has at most m monomial generators and it is Ic (K )=(X1 +j1 ··· X1 +jp2 X2 X2 +j1 ··· X2 +jp3 X3 X4 ··· Xm-1 +jpm Xm , X1 X1 +1 ··· X2 -1 X2 X2 +j1 ··· X2 +jp3 X3 X4 ··· Xm-1 +jpm Xm , . . . , X1 ··· Xm-3 +jpm-2 Xm-2 Xm-1 Xm-1 +j1 ·· · Xm-1 +jpm Xm , X1 ··· Xm-3 +jpm-2 Xm-2 Xm-1 Xm-1 +1 ··· Xm -1 ). Corollary 2.2. Let K be the subgraph of K having loops only in the vertices of Km . The ideal of vertex covers of I(K) has at most m+1 monomial generators. For instance, if the loops lie on v2 , v4 , v5 , vm-3 , vm-1 , it is: Ic (K) = X1 ··· Xm , X1 ··· X1 -1 X2 ··· Xm , X1 X1 +1 ··· X2 -1 X2 X3 ··· Xm , . . . , X1 ··· Xm-2 Xm-2 +1 ··· Xm-1 -1 Xm-1 Xm , X1 ··· Xm-1 Xm-1 +1 ··· Xm -1 . Corollary 2.3. Let H {vh , vh } be the connected graph on n vertices v1 , . . ., vm , . . ., vn , h=m+1, . . ., n. The ideal of vertex covers for the edge ideal of H{vh , vh } is generated by the m monomials X2 X3 . . .Xm Xm+1 . . .Xn , X1 X3 . . . Xm Xm+1 . . . Xn , . . . , X1 X2 . . . Xm-1 Xm+1 . . . Xn . Example 2.2. Let K be the connected graph with V (K ) = {v1 , v2 , v3 , . . . , v11 } given by K3 star1 (4) star2 (4) star3 (3) {v3 , v3 } {v5 , v5 } {v7 , v7 } {v9 , v9 } . The ideal of vertex covers is Ic (K ) = (X1 X2 X3 X5 X7 X9 , X2 X3 X4 X5 X6 X7 X9 , X1 X3 X5 X7 X8 X9 ). 3. Ideals of vertex covers of linear type Let R be a noetherian ring and let I = (f1 , . . . , fs ) be an ideal of R. The Rees algebra (I) of I is defined to be the R-graded algebra i 0 I i . It can be identified with the R-subalgebra of R[t] generated by It, where t is an indeterminate on R. Let we consider the epimorphism of graded Ralgebras : R[T1 , . . . , Ts ] (I) = R[f1 t, . . . , fs t] defined by (Ti ) = fi t, i = 1, . . . , s. The ideal N = ker of R[T1 , . . . , Ts ] is R-homogeneous and we denote Ni the R-homogeneous component of degree i of N . The elements of N1 are called linear relations. If A = (aij ), i = 1, . . . , r, j = 1, . . . , s is the relation matrix of I, then gi = s aij Tj , i = 1, . . . , r, belong to N and j=1 R[T1 , . . . , Ts ]/J, with J = (g1 , . . . , gr ), is isomorphic to the symmetric algebra SymR (I) of I. The generators gi of J are all linear in the variables Tj . The natural map : SymR (I) (I) is a surjective homomorphism of R-algebras. I is called of linear type if is an isomorphism, that is N = J. Now, let K be a field, R = K[X1 , . . . , Xn ] be the polynomial ring, I R be a graded ideal whose generators f1 , . . . , fs are all of the same degree. Let S = R[T1 , . . . , Ts ] be the polynomial ring over R in the variables T1 , . . . , Ts . Then we define a bigrading of S by setting deg(Xi ) = (1, 0) for i = 1, . . . , n and deg(Tj ) = (0, 1) for j = 1, . . . , s. Consider the presentation : R[T1 , . . . , Ts ] (I), (Ti ) = fi t, i = 1, . . . , s. If I = (f1 , . . . , fs ) R fi is a monomial ideal, for all 1 i < j s we set fij = GCD(fi ,fj ) and gij = fij Tj - fji Ti , then J is generated by {gij }1 i<j s . Our aim is to investigate classes of monomial ideals arising from graphs for which the linear relations gij form a system of generators for N , i.e. N =J. Consider the ideals of vertex covers Ic (H) and Ic (K ) . Theorem 3.1. Let R = K[X1 , . . . , Xm , . . . , Xn ]. Ic (H) is of linear type. Proof. Let f1 , . . . , fm+1 be the minimal system of monomial generators of Ic (H), where f1 = X1 X2 ··· Xm , f2 = X1··· X1 -1 X2 ··· Xm , . . . , fm = X1···Xm-2 Xm-2 +1···Xm-1 -1 Xm , fm+1 = X1···Xm-1 Xm-1 +1···Xm -1 (Theorem 2.1). We prove that the linear relations gij = fij Tj - fji Ti form a Gr¨bner o basis of N with respect to a monomial order on the polynomial ring R[T1 , . . . , Tm+1 ]. Denote by H the ideal (fij Tj : 1 i < j m+1). To show that gij are a Gr¨bner basis of N we suppose that the claim is false. Since o the binomial relations are known to be a Gr¨bner basis of N , there exists a o a b a b a a b binomial X T - X T N , where X = X1 1 · · · Xnn , X b = X11 · · · Xnn , m+1 m+1 1 1 a T =T1 · · · Tm+1 , T =T1 · · · Tm+1 , and the initial monomial of X T - X b T is not in H. More precisely, we assume that T , T have no common factors and that both X a T and X b T are not in H. Let i be the smallest index such that Ti appears in T or in T . Since a X T - X b T N , then fi divides X b (T ), where (Ti ) = fi t. If fi |X b , then let Tj be any of the variables of T . One has fij Tj |fi Tj |X b T for i < j. / This is a contradiction by assumption (because X b T H). b Hence fi X . Let Xi1 . . . Xis be a total term order on the variables of fi , and let fi = Xi1 · · · Xis . Let ik1 , . . . , ikt {i1 , . . . , is } be the indices such that Xik1 , . . . , Xikt don't divide X b and ik1 be the minimum of the indices such that Xik1 does not divide X b . Then gi = fi /Xik1 · · · Xikt divides X b . Since Xik1 divides X b (T ) (because fi |X b (T )), then there exists j such that Tj appears in T and Xik1 |fj . By the structure of the generators f1 , . . . , fm+1 of Ic (H) (see Theorem 2.1) if Xik1 |fi and Xik1 |fj with j such that Tj is in T , then fij |gi . Hence fij divides X b and, as a consequence, fij Tj divides X b T , that is a contradiction (because X b T H). It follows / that N = (gij : 1 i < j m + 1), hence Ic (H) is of linear type. Theorem 3.2. Let R=K[X1 , . . ., Xm , . . . , Xn ]. Ic (K ) is of linear type. Proof. Let f1 , . . . , f for m + 1 be the minimal system of monomial generators of Ic (K ) described in Theorem 2.2. We prove that the linear relations gij = fij Tj - fji Ti , 1 i<j , form a Gr¨bner basis of N . We suppose that the claim is false. Using the o same notation of Theorem 3.1 there exists a binomial X a T - X b T N and in (X a T - X b T ) is not in H = (fij Tj : 1 i < j , m + 1). Let i be the smallest index such that Ti appears in T or in T . Since a X T - X b T N , then fi divides X b (T ), where (Ti ) = fi t. If fi |X b , then fij Tj |fi Tj |X b T , i < j and Tj any of the variables of T . This is a contradiction. Hence fi X b . Let fi = Xi1 . . . Xis , ik1 , . . . , ikt {i1 , . . . , is } be the indices such that Xik1 , . . . , Xikt don't divide X b and ik1 be the minimum of the indices such that Xik1 does not divide X b . Set gi = fi /Xik1 · · · Xikt . Since Xik1 divides X b (T ), then there exists j such that Tj appears in T and Xik1 |fj . By the structure of the monomials f1 , . . . , f (Theorem 2.2) if Xik1 |fi and Xik1 |fj with j such that Tj is in T , then fij |gi . Hence fij |X b and, as a consequence, fij Tj |X b T , that is a contradiction. Hence N = (gij : 1 i<j m + 1). The thesis follows. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Annals of the Alexandru Ioan Cuza University - Mathematics de Gruyter

Monomial Ideals of Graphs with Loops

Download PDF
16 pages

Loading next page...
 
/lp/de-gruyter/monomial-ideals-of-graphs-with-loops-RGLtRkorg0
Publisher
de Gruyter
Copyright
Copyright © 2014 by the
ISSN
1221-8421
eISSN
1221-8421
DOI
10.2478/aicu-2013-0010
Publisher site
See Article on Publisher Site

Abstract

We investigate, using the notion of linear quotients, significative classes of connected graphs whose monomial edge ideals, not necessarily squarefree, have linear resolution, in order to compute standard algebraic invariants of the polynomial ring related to these graphs modulo such ideals. Moreover we are able to determine the structure of the ideals of vertex covers for the edge ideals associated to the previous classes of graphs which can have loops on any vertex. Lastly, it is shown that these ideals are of linear type. Mathematics Subject Classification 2010: 05C25, 05E40, 13A30, 13C15. Key words: graphs with loops, linear quotients, ideals of vertex covers, ideals of linear type. Introduction In [8] it was first shown how some algebraic properties related to remarkable classes of graphs hold when appropriate loops are put. In this article we are interested in studying standard algebraic properties of monomial ideals arising from the edges of some graphs, the so-called edge ideals, and exposing situations for which such properties are preserved when we add loops to them. The generators of ideals of vertex covers for the edge ideals associated to graphs with loops are also examined, proving that these ideals are of linear type. Let G be a graph on n vertices v1 , . . . , vn . An algebraic object attached to G is the edge ideal I(G), a monomial ideal of the polynomial ring in n variables R = K[X1 , . . . , Xn ], K a field. When G is a loopless graph, I(G) is generated by squarefree monomials of degree two in R, I(G) = {Xi Xj | {vi , vj } is an edge of G } , but if G is a graph having loops {vi , vi }, among the generators of I(G) there are also non-squarefree monomials Xi2 , i = 1, . . . , n. For a relevant class of connected graphs with loops we prove that their edge ideals have linear resolution, by using the technique of studying the linear quotients of such ideals, as previously employed in [9]. More precisely, it is examined a wide class of squarefree edge ideals associated to the connected graphs H, on n vertices, consisting of the union of a complete graph Km , m < n, and star graphs with centers the vertices of Km . By adding loops on some vertices of Km , we introduce a new class of non-squarefree edge ideals associated to the connected graphs K = H {vj , vj }, for some j = 1, . . . , m . We prove that I(H) and I(K) have linear resolution. We also give formulae for standard invariants of R/I(H) and R/I(K) such as dimension, projective dimension, depth, CastelnuovoMumford regularity. In [7] the computation of such invariants is made for the symmetric algebras of subclasses of squarefree edge ideals generated by s-sequences associated to G. Some algebraic aspects linked to the minimal vertex covers for such classes of graphs can be considered. Keeping in mind the one to one correspondence between minimal vertex covers of any graph and minimal prime ideals of its edge ideal, we generalize to a graph with loops the notion of ideal of (minimal) vertex covers and determine the structure of the ideals of vertex covers Ic (H) and Ic (K ) for the classes of edge ideals associated to H and K = H {vi , vi }, for some i = 1, . . . , n . We may observe that K is larger than K because loops on K stay also on vertices that don't belong to Km . Moreover we prove that the symmetric and the Rees algebras of Ic (H) and Ic (K ) over R are isomorphic, namely such ideals are of linear type. The work is subdivided as follows. In section 1 the classes of graphs H, K and their edge ideals are analyzed. In particular, starting from H, we introduce K and consider its edge ideal whose ordered generators are X1 Xm+1 , X1 Xm+2 , ..., X1 Xm+i1 , X1 X2 , X2 Xm+i1 +1 , . . . , X2 Xm+i1 +i2 , X2 X3 , X1 X3 , X3 Xm+i1 +i2 +1 , ..., X3 Xm+i1 +i2 +i3 , X3 X4 , X2 X4 , 2 2 X1 X4 , ..., Xm Xm+i1 +...+im-1 +1 , ..., Xm Xm+i1 +...+im , Xt1 , . . . , Xtl , where {t1 , . . . , tl } {1, . . . , m} and n = m + i1 + . . . + im . According to results that characterize monomial ideals with linear quotients ([2, 4]), it is shown that the edge ideals of H and K have linear resolution. As an application, standard algebraic invariants are calculated. In section 2 we examine the structure of the ideals of vertex covers for the classes of edge ideals associated to H and K using the description of the ideals of vertex covers for the edge ideals associated to the complete graphs and the star graphs that make them up. We remark that the ideal of vertex covers of I(K ), when K has loops on all its n vertices, has the unique generator X1 · · · Xm · · · Xn . In section 3 we investigate the Rees algebra of Ic (H) and Ic (K ). We recall that if I = (f1 , . . . , fs ) is an ideal of R, the Rees algebra (I) of i I is defined to be the R-graded algebra i 0 I . Let : R[T1 , . . . , Ts ] (I) = R[f1 t, . . . , fs t] be an epimorphism of graded R-algebras defined by (Ti ) = fi t , i = 1, . . . , s , and N = ker be the ideal of presentation of (I). If N is generated by linear relations, namely R-homogeneous elements of degree 1, then I is said of linear type. Several classes of ideals of R of linear type are known. For instance, ideals generated by d-sequences and M -sequences are of linear type ([1, 6, 10]). We show that the ideals of vertex covers Ic (H) and Ic (K ) are of linear type. 1. Linear resolutions and invariants Let R = K[X1 , . . . , Xn ] be the polynomial ring in n variables over a field K with deg Xi = 1, for all i = 1, . . . , n. For a monomial ideal I R we denote by G(I) its unique minimal set of monomial generators. Definition 1.1. A vertex cover of a monomial ideal I R is a subset C of {X1 , . . . , Xn } such that each u G(I) is divided by some Xi C. The vertex cover C is called minimal if no proper subset of C is a vertex cover of I. Let h(I) denote the minimal cardinality of the vertex covers of I. Definition 1.2. A monomial ideal I R is said to have linear quotients if there is an ordering u1 , . . . , ut of monomials belonging to G(I) with deg(u1 ) ··· deg(ut ) such that the colon ideal (u1 , . . . , uj-1 ) : (uj ) is generated by a subset of {X1 , . . . , Xn }, for 2 j t . Remark 1.1. A monomial ideal I of R generated in one degree that has linear quotients admits a linear resolution ([2], Lemma 4.1). For a monomial ideal I of R having linear quotients with respect to the ordering u1 , . . . , ut of the monomials of G(I), let qj (I) denote the number of the variables which is required to generate the ideal (u1 , . . . , uj-1 ) : (uj ) , and set q(I) = max2 j t qj (I). Remark 1.2. The integer q(I) is independent on the choice of the ordering of the generators that gives linear quotients ([5]). In this section we study classes of monomial ideals generated in degree two arising from graphs that have linear quotients, that is equivalent to say that they have linear resolution ([4]). Let's introduce some preliminary notions. Let G be a graph and V (G) = {v1 , . . . , vn } be the set of its vertices. We put E(G) = {{vi , vj }|vi = vj , vi , vj V (G)} the set of edges of G and L(G) = {{vi , vi }| vi V (G)} the set of loops of G. Hence {vi , vj } is an edge joining vi to vj and {vi , vi } is a loop of the vertex vi . Set W (G) = E(G) L(G). If L(G) = , the graph G is said simple or loopless, otherwise G is a graph with loops. A graph G on n vertices v1 , . . . , vn is complete if there exists an edge for all pairs {vi , vj } of vertices of G. It is denoted by Kn . If V (G) = {v1 , . . . , vn } and R = K[X1 , . . . , Xn ] is the polynomial ring over a field K such that each variable Xi corresponds to the vertex vi , the edge ideal I(G) associated to G is the ideal {Xi Xj | {vi , vj } W (G)} R . Note that the non-zero edge ideals are those generated by monomials of degree 2. This implies that I(G) is a graded ideal of R of initial degree 2, that is I(G) = i 2 (I(G)i ) . If W (G) = , then I(G) = (0) . First it is examined a relevant wide class of squarefree edge ideals associated to connected graphs H on n vertices, consisting of the union of a complete graph Km , m < n, and star graphs in the vertices of Km . More precisely, H = Km starj (k), where Km is the complete graph on m vertices v1 , . . . , vm , m < n, and starj (k) is the star graph on k vertices with center vj , for some j = 1, . . . , m, k n-m. One has: I(H) = (X1 Xm+1 , X1 Xm+2 , . . . , X1 Xm+i1 , X1 X2 , X2 Xm+i1 +1 , X2 Xm+i1 +2 , . . . , X2 Xm+i1 +i2 , X2 X3 , X1 X3 , X3 Xm+i1 +i2 +1 , X3 Xm+i1 +i2 +2 , . . . , X3 Xm+i1 +i2 +i3 , X3 X4 , X2 X4 , X1 X4 , . . . , Xm Xm+i1 +i2 +···+im-1 +1 , Xm Xm+i1 +i2 +···+im-1 +2 , . . . , Xm Xm+i1 +i2 +···+im-1 +im ) R. |G(I(H))| = i1 + i2 + · · · + im + m(m-1) . 2 Proposition 1.1. I(H) has a linear resolution. Proof. I(H) is the edge ideal of the graph H with n = m+i1 +i2 +· · ·+ im vertices and = i1 +i2 +· · ·+im + m(m-1) = n-m+ m(m-1) = n+ m(m-3) 2 2 2 edges. Set f1 , . . . , f the squarefree monomial generators of I(H). It results: (f1 ) : (f2 ) = (Xm+1 ), (f1 , f2 ) : (f3 ) = (Xm+1 , Xm+2 ), ..................................., (f1 , . . . , fi1 -1 ) : (fi1 ) = (Xm+1 , Xm+2 , . . . , Xm+i1 -1 ), (f1 , . . . , fi1 ) : (fi1 +1 ) = (Xm+1 , Xm+2 , . . . , Xm+i1 ), (f1 , . . . , fi1 +1 ) : (fi1 +2 ) = (X1 Xm+1 , X1 Xm+2 , . . . , X1 Xm+i1 , X1 ) = (X1 ), (f1 , . . . , fi1 +2 ) : (fi1 +3 ) = (X1 , Xm+i1 +1 ), ..................................., (f1 , . . . , fi1 +i2 +1 ) : (fi1 +i2 +2 ) = (X1 , Xm+i1 +1 , . . . , Xm+i1 +i2 ), (f1 , . . . , fi1 +i2 +2 ) : (fi1 +i2 +3 ) = (Xm+1 , Xm+2 , . . . , Xm+i1 , X2 ), (f1 , . . . , fi1 +i2 +3 ) : (fi1 +i2 +4 ) = (X2 , X1 ), ..................................., (f1 , . . . , fi1 +i2 +i3 +2 ):(fi1 +i2 +i3 +3 )=(X2 , X1 , Xm+i1 +i2 +1 , . . . , Xm+i1 +i2 +i3 ), and so on up to (f1 , . . . , f-1 ) : (f ) = (X1 , . . . , Xm-1 , Xm+i1 +i2 +···+im-1 +1 , . . . , Xm+i1 +i2 +···+im -1 ). Hence I(H) has linear quotients. According to results in [4] about monomial ideals with linear quotients, it follows that the edge ideal I(H) has a linear resolution. Remark 1.3. R. Fr¨berg proved that the edge ideal of a simple graph o has a linear resolution if and only if its complementary graph is chordal ([4], Theorem 9.2.3). By using such a characterization, it is possible to show that the edge ideal I(H) of Proposition 1.1 has a linear resolution. The study of the linear quotients is useful in order to investigate algebraic invariants of R/I(H): the dimension, dimR (R/I(H)), the depth, depth(R/I(H)), the projective dimension, pdR (R/I(H)) and the Castelnuovo-Mumford regularity, regR (R/I(H)). Lemma 1.1. Let R=K[X1 , . . . , Xn ] and I(H) R. Then h(I(H))=m. Proof. The minimal cardinality of the vertex covers of I(H) is h(I(H)) = m, being C = {X1 , . . . , Xm } a minimal vertex cover of I(H) by construction. Lemma 1.2. Let R = K[X1 , . . . , Xn ] and I(H) R. Then: q(I(H)) = m + max ij - 2 . 1 j m Proof. By the computation of the linear quotients (Proposition 1.1), the maximum number of the variables which is required to generate the ideal (f1 , . . . , fh-1 ) : (fh ), for h = 1, . . . , , is given by (m - 1) + max1 j m ij - 1. It follows that q(I(H)) = m + max1 j m ij - 2 . Theorem 1.1. Let R = K[X1 , . . . , Xn ] and I(H) R. Then: 1) dimR (R/I(H)) = n - m . 2) pdR (R/I(H)) = m + max1 j m ij - 1. j m ij 3) depthR (R/I(H)) = n - m - max1 4) regR (R/I(H)) = 1 . + 1. Proof. 1) One has dimR (R/I(H)) = dimR R - h(I(H)) ([3]). Hence, by Lemma 1.1 , dimR (R/I(H)) = n - m . 2) The length of the minimal free resolution of R/I(H) over R is equal to q(I(H))+1 ([5], Corollary 1.6). Then pdR (R/I(H)) = m+max1 j m ij -1. 3) As a consequence of 2), by Auslander-Buchsbaum formula, one has depthR (R/I(H)) = n - pdR (R/I(H)) = n - m - max1 j m ij + 1. 4) I(H) has a linear resolution, then regR (R/I(H)) = 1. Starting from the class of edge ideals associated to H and adding loops on some vertices of Km , we now analyze a larger class of non-squarefree edge ideals associated to connected graphs K = H {vj , vj }, for some j = 1, . . . , m . Let K be the connected graph with n vertices v1 , . . . , vn and Km , m < n, be the complete subgraph of K with vertices v1 , . . . , vm , such that I(K) = X1 Xm+1 , X1 Xm+2 , . . . , X1 Xm+i1 , X1 X2 , X2 Xm+i1 +1 , X2 Xm+i1 +2 , . . . , X2 Xm+i1 +i2 , X2 X3 , X1 X3 , X3 Xm+i1 +i2 +1 , X3 Xm+i1 +i2 +2 , . . . , X3 Xm+i1 +i2 +i3 , X3 X4 , X2 X4 , X1 X4 , . . . , Xm Xm+i1 +i2 +···+im-1 +1 , Xm Xm+i1 +i2 +···+im-1 +2 , . . . , 2 2 Xm Xm+i1 +i2 +···+im-1 +im , Xt1 , . . . , Xtl R = K[X1 , . . . , Xn ], with {t1 , . . . , tl } {1, . . . , m} and n = m + i1 + · · · + im . |G(I(K))| = n - (m - l) + m(m-1) . 2 Taking in account the notion of linear quotients, it is proved that the edge ideal I(K) has still a linear resolution. Proposition 1.2. I(K) has a linear resolution. Proof. I(K) is the edge ideal of the graph K with n = m+i1 +i2 +· · ·+im vertices, = i1 + i2 + · · · + im + m(m-1) = n - m + m(m-1) = n + m(m-3) 2 2 2 edges and l m loops {vt1 , vt1 }, . . . , {vtl , vtl }. Set f1 , . . . , f , f+1 , . . . , f+l the monomial generators of I(K), of which the last l are not squarefree. The ideals (f1 , . . . , fh-1 ) : (fh ), for h = 1, . . . , , have been computed in Proposition 1.1. Moreover, it results: (f1 , . . . , f ) : (f+1 ) = (X2 , . . . , Xm , Xm+1 , . . . , Xm+i1 ), if v1 has a loop, (f1 , . . . , f ) : (f+1 ) = (X1 , . . . , Xt1 -1 , Xt1 +1 , . . . , Xm , Xm+i1 +...+it1 -1 +1 , . . . , Xm+i1 +...+it1 -1 +it1 ), if {vt1 , vt1 } = {v1 , v1 }; ..................................., (f1 , . . . , f+l-1 ):(f+l )=(X1 , . . . , Xtl -1 , Xtl +1 , . . . , Xm , Xm+i1 +...+itl -1 +1 , . . . , Xm+i1 +...+itl -1 +itl ), if {vtl , vtl } = {vm , vm }, (f1 , . . . , f+l-1 ) : (f+l ) = (X1 , . . . , Xm-1 ,m+i1 +...+im-1 +1 , . . . , Xm+i1 +...+im ), if vm has a loop. Hence I(K) has linear quotients, that is equivalent to say that I(K) has a linear resolution ([4]). The study of the linear quotients as in Proposition 1.2 is useful in order to investigate algebraic invariants of R/I(K). Lemma 1.3. Let R = K[X1 , . . . , Xn ] and I(K) R. Then: h(I(K)) = m . Proof. The minimal cardinality of the vertex covers of I(K) is h(I(K)) = m, being C={X1 , . . ., Xm } a minimal vertex cover of I(K) by construction. Lemma 1.4. Let R = K[X1 , . . . , Xn ] and I(K) R. Then: q(I(K)) = m + max ij - 1, µ t1 j tµ m. Proof. By the computation of the linear quotients (Proposition 1.2), the maximum number of the variables which is required to generate the ideal (f1 , . . . , fk-1 ) : (fk ), for k = 1, . . . , + µ, µ m, is given by (m - 1) + max t1 j tµ ij . It follows that q(I(K)) = m + max t1 j tµ ij - 1 . Theorem 1.2. Let R = K[X1 , . . . , Xn ] and I(K) R. Then: 1) dimR (R/I(K)) = n - m . 2) pdR (R/I(K)) = m + max t1 4) regR (R/I(K)) = 1 . Proof. 1) One has dimR (R/I(K)) = dimR R - h(I(K)) ([3]). Hence, by Lemma 1.3 , dimR (R/I(K)) = n - m . 2) The length of the minimal free resolution of R/I(K)) over R is equal to q(I(K))+1 ([5], Corollary 1.6). Then pdR (R/I(K)) = m+max t1 j tµ ij , µ m. 3) As a consequence of 2), by Auslander-Buchsbaum formula, one has depthR (R/I(K)) = n - pdR (R/I(K)) = n - m - max t1 j tµ ij , µ m. 4) I(K) has a linear resolution, then regR (R/I(K)) = 1. Remark 1.4. When the graph K has at least a loop on a vertex that don't belong to Km , then its edge ideal has not linear quotients. In fact, it can be verified there is no ordering of the monomials f1 , . . . , fs G(I(K)) , s = n - (m - l) + m(m-1) , such that (f1 , . . . , fj-1 ) : (fj ) is gen2 erated by a subset of {X1 , . . . , Xn }, for 2 j s. 2. Ideals of vertex covers Definition 2.1. Let G be a graph with vertex set V (G) = {v1 , . . . , vn }. A subset C of V (G) is said a minimal vertex cover for G if: (1) every edge of G is incident with one vertex in C; (2) there is no proper subset of C with this property. If C satisfies condition (1) only, then C is called a vertex cover of G and C is said to cover all the edges of G. The smallest number of vertices in any minimal vertex cover of G is said vertex covering number. We denote it by 0 (G). We consider some algebraic aspects linked to the minimal vertex covers of a graph G with set of edges E(G) and set of loops L(G). Let I(G)=({Xi Xj |{vi , vj }W (G)=E(G) L(G)}) be the edge ideal associated to G. A loop {vi , vi }L(G), such that vi belongs to a vertex cover of G, can be thought to have a double covering that preserves the minimality. j tµ ij , µ j tµ m. ij , µ m. 3) depthR (R/I(K)) = n - m - max t1 There exists a one to one correspondence between the minimal vertex covers of G and the minimal prime ideals of I(G). In fact, is a minimal prime ideal of I(G) if and only if =(C), for some minimal vertex cover C of G ([11], Prop. 6.1.16). Hence ht (I(G))=0 (G). Thus the primary decomposition of the edge ideal of G is given by I(G) = (C1 ) · · · (Cp ), where C1 , . . . , Cp are the minimal vertex covers of G. Definition 2.2. Let I R = K[X1 , . . . , Xn ] be a monomial ideal. The ideal of (minimal) covers of I, denoted by Ic , is the ideal of R generated by all monomials Xi1 · · · Xik such that (Xi1 , . . . , Xik ) is an associated (minimal) prime ideal of I. If I(G) is the edge ideal of a graph G, we call Ic (G) the ideal of vertex covers of I(G). Property 2.1. Ic (G) = i=j (Xi , Xj ) Xk | {vk , vk } L(G), k = i, j . {vi ,v }E(G) j We want to examine the structure of the ideals of vertex covers for the class of squarefree edge ideals associated to H. In the sequel, we rename v1 , . . . , vm the vertices of the complete graph Km , 1 1 < 2 < . . . < m = n, and 1 = 1 if there is not the star graph with center v1 . The following two lemmas give explicitly the generators of the ideals of vertex covers for the edge ideals of a complete graph and a star graph, respectively. Their proofs are an easy application of Property 2.1 . Lemma 2.1. The ideal of vertex covers of I(Km ) is generated by m monomials and it is Ic (Km ) = (X2 X3 · · · Xm , X1 X3 · · · Xm , . . . , X1 X2 · · · Xm-1 ). Lemma 2.2. The ideal of vertex covers of I(starj (k)) is generated by two monomials, namely X1 · · · Xj-1 Xj+1 · · · Xk , Xj . Let's study the structure of the ideal of vertex covers of I(H) when at least a vertex of Km has degree m - 1. Proposition 2.1. Let H be the connected graph with n vertices v1 , . . . , vn formed by the union of a complete graph Km , m < n, with vertices v1 , . . . , vm , 1 1 < 2 < . . . < m = n, and of a star graph star1 (1 ) on vertices v1 , . . . , v1 , or a star graph stari (i - i-1 ) with center vi , for some i = 2, . . . , m . The ideal of vertex covers Ic (H) has m monomial squarefree generators and it is: (X1 ··· X1 -1 X2 ··· Xm , X1 X3 ··· Xm , . . . , X1 ··· Xm-1 ), if i = 1, (X2···Xm , . . . , X1···Xi-1 Xi-1 +1···Xi+1 -1 Xi+1···Xm , . . . , X1···Xm-1 ), otherwise. Proof. Because of the one to one correspondence between minimal vertex covers of a graph and minimal prime ideals of its edge ideal, for the complete graph Km it follows that I(Km ) = m Pi , where Pi = i=1 (X1 , . . . , Xi-1 , Xi+1 , . . . , Xm ). The vertex covers of the graph H will be: · m - 1 vertex covers of Km , but {v1 , . . . , vi-1 , vi+1 , . . . , vm }, by Lemma 2.1; · two vertex covers related to stari (i -i-1 ), {v1 , . . . , vi-1 , vi-1 +1 , . . . , vi+1 -1 , vi+1 , . . . , vm }, {v1 , . . . , vm }, for some i = 1 , as a consequence of Lemma 2.2 . For the last ones, let Pi =(X1 , . . . , Xi-1 , Xi-1 +1 , . . . , Xi+1 -1 , Xi+1 , . . . , Xm ), P = (X1 , . . . , Xm ), respectively, be the associated minimal prime ideals but P Pj , j = i. So I(H) = P1 . . . Pi-1 Pi Pi+1 . . . Pm . On the other hand, it is clear what P1 denotes. Hence the thesis follows. Remark 2.1. Proposition 2.1 can be generalized by considering two or more star graphs with centers as many vertices of Km . It is sufficient to iterate that procedure for each pair of vertex covers related to the star graphs which are present. Finally, let's consider the structure of the ideal of vertex covers of I(H) when all the vertices of Km have degree at least m. Theorem 2.1. Let H be the connected graph with n vertices v1 , . . . , vn formed by the union of a complete graph Km , m < n, with vertices v1 , . . . , vm , 1 < 1 < 2 < . . . < m = n, and of m star graphs with centers each of the vertices of Km . The ideal of vertex covers of I(H) has m + 1 monomial squarefree generators and it is Ic (H) = X1 X2 ··· Xm , X1 ··· X1 -1 X2 ··· Xm , X1 X1 +1 ··· X2 -1 X3 ··· Xm , . . . , X1 ··· Xm-2 Xm-2 +1 ··· Xm-1 -1 Xm , X1 ··· Xm-1 Xm-1 +1 ··· Xm -1 . Proof. A minimal vertex cover of H must be {v1 , . . . , vm } and there cannot exist minimal vertex covers with a smaller number of vertices. So 0 (H) = m. Other minimal vertex covers of H are those related to star graphs on 1 and i - i-1 vertices, star1 (1 ) and stari (i - i-1 ) respectively, for any i = 2, . . . , m , in which the centers are missing. With the notations of Proposition 2.1, let P = (X1 , . . . , Xm ), P1 = (X1 , . . . , X1 -1 , X2 , . . . , Xm ), Pi = (X1 , . . . , Xi-1 , Xi-1 +1 , . . . , Xi -1 , Xi+1 , . . . , Xm ), for any i = 2, . . . , m , be the associated minimal prime ideals. Then I(H) = P ( m Pi ) , and ht I(H) = m . Thus i=1 Ic (H) = X1 · · · Xm , X1 · · · X1 -1 X2 · · · Xm , . . . , X1 · · · Xm-1 Xm-1 +1 · · · Xm -1 , and the thesis follows. Example 2.1. Let H be the connected graph with V (H) = {v1 , . . . , v4 , . . . , v11 } given by K4 star1 (2) star2 (4) star3 (2) star4 (3) . The ideal of vertex covers is Ic (H) = (X1 X2 X3 X4 , X2 X3 X4 X5 , X1 X3 X4 X6 X7 X8 , X1 X2 X4 X9 , X1 X2 X3 X10 X11 ). Let's now analyze the structure of the ideals of vertex covers for the class of non-squarefree edge ideals associated to the connected graphs on n vertices K = H {vi , vi }, for some i = 1, . . . , n . Note that the class K is larger than K because K may have loops on vertices that don't belong to Km . First let's enunciate two lemmas that give the generators of the ideals of vertex covers for the edge ideals of a complete graph with loops and a star graph with loops, respectively. Their proofs are a direct consequence of Property 2.1 . Lemma 2.3. Let Km be the complete graph with loops having vertices v1 , . . . , vm . The ideal of vertex covers of I(Km ) is generated at most by m - 1 monomials. In particular, (a) if there are loops in all the vertices, Ic (Km ) = (X1 X2 · · · Xm ), (b) if there are loops in r<m vertices, vt1 , . . . , vtr , {t1 , . . . , tr }{1, . . . , m}, Ic (Km ) has m-r generators and it is {X1 · · ·Xm-1 | j = tj , j = 1, . . . , r; i {1, . . . , m}\ {t1 , . . . , tr }, i = j} . Lemma 2.4. Let star (n) be the star graph with loops having vern tices v1 , . . . , vn . The ideal of vertex covers of I(star (n)) has at most 2 n generators. In particular, (a) if the loops are in the vertices v1 , . . . , vn-1 , Ic (star (n))=(X1 · · · Xn-1 ), n (b) if the loops are in v3 , vn-2 , Ic (star (n)) = (X1 · · · Xn-1 , X3 Xn-2 Xn ), n (c) if there are loops in the center and in the vertices vt1 , . . ., vts , {t1 , . . ., ts } {1, . . . , n-1}, Ic (star (n)) = (Xt1 · · · Xts Xn ). n The structure of the ideal of vertex covers of I(K ) is well described by the following: Theorem 2.2. Let K be the connected graph with n vertices v1 , . . . , vn formed by the union of: (i) the complete graph Km , m < n, with vertices v1 , . . . , vm , 1 1 < 2 < . . . < m = n ; (ii) star graphs stari (i -i-1 ) on vertices vi-1 +1 , . . . , vi , i=1, . . . , m, and the index 0 indicates 0 ; (iii) loops in some vertices, say v2 , v4 , v5 , vm-3 , vm-1 , vi-1 +j1 , . . . , vi-1 +jpi , where {j1 , . . . , jpi } {1, . . . , i -i-1 -1} . The ideal of vertex covers of I(K ) has at most m + 1 monomial generators and it is Ic (K ) = Xj1 ··· Xjp1 X1 X1 +j1 ··· X1 +jp2 X2 X2 +j1 ··· Xm-1 +jpm Xm , X1 ··· X1 -1 X1 +j1 ··· X1 +jp2 X2 X2 +j1 ··· Xm-1 +jpm Xm , Xj1 ··· Xjp1 X1 X1 +1 ··· X2 -1 X2 X2 +j1 ··· Xm-1 +jpm Xm , . . . , Xj1 ··· Xm-3 +jpm-2 Xm-2 Xm-2 +1 ··· Xm-1 -1 Xm-1 Xm-1 +j1 ··· Xm-1 +jpm Xm , Xj1 ··· Xm-2 +jpm-1 Xm-1 Xm-1 +1 ··· Xm -1 . Proof. The correspondence between minimal vertex covers of the graph H and minimal prime ideals of the edge ideal of H extends to the graph K . So the number of minimal prime ideals of I(K ) is the same than that of minimal primes of I(H). Moreover, by Property 2.1, the generators of the prime ideals are those related to H multiplied by monomials Xi whenever Xi , i = 1, . . . , n. The latter monomials represent the vertices with loops / of K for which the corresponding variables are missing in . The assertion holds through some computation taking in consideration Theorem 2.1. Significative particular cases concern the graphs of the class such that: (a) some star graphs are missing, (b) the loops lie only on the vertices of Km , and (c) the loops lie only on the vertices not belonging to Km . Corollary 2.1. Let K be as in Theorem 2.2, but there are in it less than m star graphs stari (i - i-1 ), suppose for i = 2, 3, 6, m-3, m-2, m . The ideal of vertex covers of I(K ) has at most m monomial generators and it is Ic (K )=(X1 +j1 ··· X1 +jp2 X2 X2 +j1 ··· X2 +jp3 X3 X4 ··· Xm-1 +jpm Xm , X1 X1 +1 ··· X2 -1 X2 X2 +j1 ··· X2 +jp3 X3 X4 ··· Xm-1 +jpm Xm , . . . , X1 ··· Xm-3 +jpm-2 Xm-2 Xm-1 Xm-1 +j1 ·· · Xm-1 +jpm Xm , X1 ··· Xm-3 +jpm-2 Xm-2 Xm-1 Xm-1 +1 ··· Xm -1 ). Corollary 2.2. Let K be the subgraph of K having loops only in the vertices of Km . The ideal of vertex covers of I(K) has at most m+1 monomial generators. For instance, if the loops lie on v2 , v4 , v5 , vm-3 , vm-1 , it is: Ic (K) = X1 ··· Xm , X1 ··· X1 -1 X2 ··· Xm , X1 X1 +1 ··· X2 -1 X2 X3 ··· Xm , . . . , X1 ··· Xm-2 Xm-2 +1 ··· Xm-1 -1 Xm-1 Xm , X1 ··· Xm-1 Xm-1 +1 ··· Xm -1 . Corollary 2.3. Let H {vh , vh } be the connected graph on n vertices v1 , . . ., vm , . . ., vn , h=m+1, . . ., n. The ideal of vertex covers for the edge ideal of H{vh , vh } is generated by the m monomials X2 X3 . . .Xm Xm+1 . . .Xn , X1 X3 . . . Xm Xm+1 . . . Xn , . . . , X1 X2 . . . Xm-1 Xm+1 . . . Xn . Example 2.2. Let K be the connected graph with V (K ) = {v1 , v2 , v3 , . . . , v11 } given by K3 star1 (4) star2 (4) star3 (3) {v3 , v3 } {v5 , v5 } {v7 , v7 } {v9 , v9 } . The ideal of vertex covers is Ic (K ) = (X1 X2 X3 X5 X7 X9 , X2 X3 X4 X5 X6 X7 X9 , X1 X3 X5 X7 X8 X9 ). 3. Ideals of vertex covers of linear type Let R be a noetherian ring and let I = (f1 , . . . , fs ) be an ideal of R. The Rees algebra (I) of I is defined to be the R-graded algebra i 0 I i . It can be identified with the R-subalgebra of R[t] generated by It, where t is an indeterminate on R. Let we consider the epimorphism of graded Ralgebras : R[T1 , . . . , Ts ] (I) = R[f1 t, . . . , fs t] defined by (Ti ) = fi t, i = 1, . . . , s. The ideal N = ker of R[T1 , . . . , Ts ] is R-homogeneous and we denote Ni the R-homogeneous component of degree i of N . The elements of N1 are called linear relations. If A = (aij ), i = 1, . . . , r, j = 1, . . . , s is the relation matrix of I, then gi = s aij Tj , i = 1, . . . , r, belong to N and j=1 R[T1 , . . . , Ts ]/J, with J = (g1 , . . . , gr ), is isomorphic to the symmetric algebra SymR (I) of I. The generators gi of J are all linear in the variables Tj . The natural map : SymR (I) (I) is a surjective homomorphism of R-algebras. I is called of linear type if is an isomorphism, that is N = J. Now, let K be a field, R = K[X1 , . . . , Xn ] be the polynomial ring, I R be a graded ideal whose generators f1 , . . . , fs are all of the same degree. Let S = R[T1 , . . . , Ts ] be the polynomial ring over R in the variables T1 , . . . , Ts . Then we define a bigrading of S by setting deg(Xi ) = (1, 0) for i = 1, . . . , n and deg(Tj ) = (0, 1) for j = 1, . . . , s. Consider the presentation : R[T1 , . . . , Ts ] (I), (Ti ) = fi t, i = 1, . . . , s. If I = (f1 , . . . , fs ) R fi is a monomial ideal, for all 1 i < j s we set fij = GCD(fi ,fj ) and gij = fij Tj - fji Ti , then J is generated by {gij }1 i<j s . Our aim is to investigate classes of monomial ideals arising from graphs for which the linear relations gij form a system of generators for N , i.e. N =J. Consider the ideals of vertex covers Ic (H) and Ic (K ) . Theorem 3.1. Let R = K[X1 , . . . , Xm , . . . , Xn ]. Ic (H) is of linear type. Proof. Let f1 , . . . , fm+1 be the minimal system of monomial generators of Ic (H), where f1 = X1 X2 ··· Xm , f2 = X1··· X1 -1 X2 ··· Xm , . . . , fm = X1···Xm-2 Xm-2 +1···Xm-1 -1 Xm , fm+1 = X1···Xm-1 Xm-1 +1···Xm -1 (Theorem 2.1). We prove that the linear relations gij = fij Tj - fji Ti form a Gr¨bner o basis of N with respect to a monomial order on the polynomial ring R[T1 , . . . , Tm+1 ]. Denote by H the ideal (fij Tj : 1 i < j m+1). To show that gij are a Gr¨bner basis of N we suppose that the claim is false. Since o the binomial relations are known to be a Gr¨bner basis of N , there exists a o a b a b a a b binomial X T - X T N , where X = X1 1 · · · Xnn , X b = X11 · · · Xnn , m+1 m+1 1 1 a T =T1 · · · Tm+1 , T =T1 · · · Tm+1 , and the initial monomial of X T - X b T is not in H. More precisely, we assume that T , T have no common factors and that both X a T and X b T are not in H. Let i be the smallest index such that Ti appears in T or in T . Since a X T - X b T N , then fi divides X b (T ), where (Ti ) = fi t. If fi |X b , then let Tj be any of the variables of T . One has fij Tj |fi Tj |X b T for i < j. / This is a contradiction by assumption (because X b T H). b Hence fi X . Let Xi1 . . . Xis be a total term order on the variables of fi , and let fi = Xi1 · · · Xis . Let ik1 , . . . , ikt {i1 , . . . , is } be the indices such that Xik1 , . . . , Xikt don't divide X b and ik1 be the minimum of the indices such that Xik1 does not divide X b . Then gi = fi /Xik1 · · · Xikt divides X b . Since Xik1 divides X b (T ) (because fi |X b (T )), then there exists j such that Tj appears in T and Xik1 |fj . By the structure of the generators f1 , . . . , fm+1 of Ic (H) (see Theorem 2.1) if Xik1 |fi and Xik1 |fj with j such that Tj is in T , then fij |gi . Hence fij divides X b and, as a consequence, fij Tj divides X b T , that is a contradiction (because X b T H). It follows / that N = (gij : 1 i < j m + 1), hence Ic (H) is of linear type. Theorem 3.2. Let R=K[X1 , . . ., Xm , . . . , Xn ]. Ic (K ) is of linear type. Proof. Let f1 , . . . , f for m + 1 be the minimal system of monomial generators of Ic (K ) described in Theorem 2.2. We prove that the linear relations gij = fij Tj - fji Ti , 1 i<j , form a Gr¨bner basis of N . We suppose that the claim is false. Using the o same notation of Theorem 3.1 there exists a binomial X a T - X b T N and in (X a T - X b T ) is not in H = (fij Tj : 1 i < j , m + 1). Let i be the smallest index such that Ti appears in T or in T . Since a X T - X b T N , then fi divides X b (T ), where (Ti ) = fi t. If fi |X b , then fij Tj |fi Tj |X b T , i < j and Tj any of the variables of T . This is a contradiction. Hence fi X b . Let fi = Xi1 . . . Xis , ik1 , . . . , ikt {i1 , . . . , is } be the indices such that Xik1 , . . . , Xikt don't divide X b and ik1 be the minimum of the indices such that Xik1 does not divide X b . Set gi = fi /Xik1 · · · Xikt . Since Xik1 divides X b (T ), then there exists j such that Tj appears in T and Xik1 |fj . By the structure of the monomials f1 , . . . , f (Theorem 2.2) if Xik1 |fi and Xik1 |fj with j such that Tj is in T , then fij |gi . Hence fij |X b and, as a consequence, fij Tj |X b T , that is a contradiction. Hence N = (gij : 1 i<j m + 1). The thesis follows.

Journal

Annals of the Alexandru Ioan Cuza University - Mathematics – de Gruyter

Published: Nov 24, 2014

There are no references for this article.