• Ingen resultater fundet

ON VERTEX DECOMPOSABLE SIMPLICIAL COMPLEXES AND THEIR ALEXANDER DUALS

N/A
N/A
Info
Hent
Protected

Academic year: 2023

Del "ON VERTEX DECOMPOSABLE SIMPLICIAL COMPLEXES AND THEIR ALEXANDER DUALS"

Copied!
14
0
0

Indlæser.... (se fuldtekst nu)

Hele teksten

(1)

ON VERTEX DECOMPOSABLE SIMPLICIAL COMPLEXES AND THEIR

ALEXANDER DUALS

SOMAYEH MORADIand FAHIMEH KHOSH-AHANG

Abstract

In this paper we study the Alexander dual of a vertex decomposable simplicial complex. We define the concept of a vertex splittable ideal and show that a simplicial complexis vertex decomposable if and only ifIis a vertex splittable ideal. Moreover, the properties of vertex splittable ideals are studied. As the main result, it is proved that any vertex splittable ideal has a Betti splitting and the graded Betti numbers of such ideals are explained with a recursive formula.

As a corollary, recursive formulas for the regularity and projective dimension ofR/I, when is a vertex decomposable simplicial complex, are given. Moreover, for a vertex decomposable graphG, a recursive formula for the graded Betti numbers of its vertex cover ideal is presented.

In special cases, this formula is explained, whenGis chordal or a sequentially Cohen-Macaulay bipartite graph. Finally, among the other things, it is shown that an edge ideal of a graph is vertex splittable if and only if it has linear resolution.

Introduction

There is a natural correspondence between square-free monomial ideals in the polynomial ringR= k[x1, . . . , xn] (over the fieldk) and simplicial com- plexes with vertex set{x1, . . . , xn}via the Stanley-Reisner correspondence. In this regard Alexander duality plays an important role in the study of Stanley- Reisner rings. Finding Alexander dual concepts and translating a property of a simplicial complexin the Alexander dual idealI, are important top- ics in combinatorial commutative algebra. Eagon and Reiner [8] introduced Alexander dual complexes and proved the following interesting result.

Theorem0.1 ([8, Theorem 3]).A simplicial complexis Cohen-Macaulay if and only ifIhas a linear resolution.

Later in [13] and [14] shellable and sequentially Cohen-Macaulay com- plexes were characterized in terms of Alexander duals.

Theorem0.2 ([13, Theorem 1.4]). is a shellable simplicial complex if and only ifIhas linear quotients.

Corresponding author.

Received 31 July 2013, in final form 9 September 2013.

(2)

Theorem0.3 ([14, Theorem 2.1]). is sequentially Cohen-Macaulay if and only ifIis componentwise linear.

Vertex decomposability is another topological combinatorial notion such as shellability, which is related to the algebraic properties of the Stanley-Reisner ring of a simplicial complex. Provan and Billera [18] first introduced the no- tion ofk-decomposable for a pure simplicial complex. Fork= 0, this notion is known as a vertex decomposable simplicial complex. This definition was extended to non-pure complexes by Björner and Wachs in [3], [4]. Defined in a recursive manner, vertex decomposable simplicial complexes form a well- behaved class of simplicial complexes and have been studied in many papers.

In [7], vertex decomposability was used in an interesting way to study the algebraic properties of edge ideals and some nice results on edge ideals were obtained by combinatorial topological techniques. It was proved that the in- dependence complex of a whiskered graph is a pure vertex decomposable simplicial complex, and hence, Cohen-Macaulay. See also [24], in this regard.

More nice results on vertex decomposable simplicial complexes may be found in [1], [2], [5], [15], [17], [22], [24], [25]. The following implications for a simplicial complex are known.

Vertex decomposable⇒Shellable⇒Sequentially Cohen-Macaulay.

So, inspired by the above results in conjunction with the characterizations of shellable, sequentially Cohen-Macaulay and Cohen-Macaulay simplicial complexes by means of Alexander dual ideals, it is natural to ask if something similar can be said about vertex decomposable simplicial complexes. In this paper, we seek a dual concept for this class of simplicial complexes. To this end, we introduce the notion of a vertex splittable ideal, which is shown to be an appropriate dual concept for vertex decomposability and then some nice properties of such ideals are achieved. By exploiting this dual concept, we refine our results for flag complexes and study the minimal free resolution of vertex cover ideal of vertex decomposable graphs.

The paper is organized as follows. In the next section, we recall some definitions and theorems that we use in the sequel. We begin Section 2 with the definition of vertex splittable ideals. Then it is shown thatis a vertex decomposable simplicial complex if and only ifIis a vertex splittable ideal (see Theorem 2.3). Theorem 2.4 illustrates that vertex splittable ideals have linear quotients. So, one may deduce that a vertex splittable ideal generated by monomials in the same degrees has a linear resolution. As another main result, in Theorem 2.8, it is proved that a vertex splittable ideal has a Betti splitting and so a recursive formula for its graded Betti numbers is presented (see Remark 2.10). Hence, it is shown that for a vertex decomposable simplicial

(3)

complex, the regularity and projective dimension ofIcan be computed by inductive formulas. In Section 3, applications of Theorem 2.8 to vertex cover ideal of a vertex decomposable graph are given. In Theorem 3.1 the graded Betti numbers of vertex cover ideal of such graphs are explained by a recursive formula. For two families of vertex decomposable graphs, sequentially Cohen- Macaulay bipartite graphs and chordal graphs, this formula has been stated more precisely. Another application is Theorem 3.6 which states that ifGis a chordal graph, thenI (Gc)is a vertex splittable ideal. Using this fact and the characterization of Fröberg for edge ideals of graphs with linear resolution, it is shown that an edge idealI (G)is vertex splittable if and only ifI (G)has a linear resolution. In Corollary 3.8, a simple argument is given to show that for a flag complexG, the Alexander dual simplicial complexG is vertex decomposable if and only if it is Cohen-Macaulay and these conditions hold if and only ifI (G)is a vertex splittable ideal.

1. Preliminaries

Throughout this paper, we assume thatX = {x1, . . . , xn}, is a simplicial complex on the vertex setX,kis a field,R=k[X] is the ring of polynomials in the variablesx1, . . . , xn andI is a monomial ideal ofR. For a monomial idealI, the unique set of minimal generators ofIis denoted byG(I ).

In this section, we recall some preliminaries which are needed in the sequel.

We begin with definition of a vertex decomposable simplicial complex. To this aim, we need to recall the definition of the link and the deletion of a face in. For a simplicial complexandF, thelinkofF inis defined as

lk(F )= {G:GF = ∅, GF}, and thedeletionofF is the simplicial complex

del(F )= {G:GF = ∅}.

Definition1.1. A simplicial complexis calledvertex decomposableif is a simplex, orcontains a vertexxsuch that

(i) both del(x)and lk(x)are vertex decomposable, and (ii) any facet of del(x)is a facet of.

A vertexxwhich satisfies condition (ii) is called ashedding vertex of. Remark1.2. It is easily seen thatx is a shedding vertex ofif and only if no facet of lk(x)is a facet of del(x).

For a Z-graded R-module M, the Castelnuovo-Mumford regularity (or simply regularity) ofM is defined as

reg(M):=max{ji:βi,j(M) =0},

(4)

and theprojective dimensionofM is defined as

pd(M):=max{i:βi,j(M) =0 for somej}, whereβi,j(M)is the(i, j )-th graded Betti number ofM.

The notion of Betti splitting for monomial ideals was introduced in [10] as follows.

Definition1.3 ([10, Definition 1.1]). LetI,J andKbe monomial ideals inRsuch thatG(I )is the disjoint union ofG(J )andG(K). ThenI =J+K is aBetti splittingif

βi,j(I )=βi,j(J )+βi,j(K)+βi1,j(JK), for alliNand degreesj.

WhenI = J +Kis a Betti splitting, important homological invariants of Iare related to those invariants of the smaller ideals.

Theorem1.4 (See [10, Corollary 2.2]).LetI =J+Kbe a Betti splitting.

Then

(i) reg(I )=max{reg(J ),reg(K),reg(J ∩K)−1}, and (ii) pd(I )=max{pd(J ),pd(K),pd(J ∩K)+1}.

For a square-free monomial idealI = (x11· · ·x1n1, . . . , xt1· · ·xt nt), the Alexander dual idealofI, denoted byI, is defined as

I:=(x11, . . . , x1n1)∩ · · · ∩(xt1, . . . , xt nt).

For a simplicial complexwith vertex setX, theAlexander dual simplicial complexassociated tois defined as

= {X\F :F /}. For a subset CX, byxC we mean the monomial

xCx. The set of all facets of a simplicial complexis denoted byF(). One can see that

(I)=(xFc:FF()),

where I is the Stanley-Reisner ideal associated to and Fc = X \F. Moreover, one can see that(I)=I.

LetGbe a graph with vertex setV (G)and edge setE(G). The edge ideal ofGis defined as the idealI (G)=(xixj :{xi, xj} ∈E(G)). It is easy to see thatI (G)can be viewed as the Stanley-Reisner ideal of the simplicial complex

G= {FV (G):eF,for eacheE(G)},

(5)

i.e., I (G) = IG. The simplicial complex G is called the independence complexofG. Moreover, the Alexander dual ofI (G)is called thevertex cover idealofG.

A gradedR-moduleM is calledsequentially Cohen-Macaulay(overk) if there exists a finite filtration of gradedR-modules

0=M0M1⊂ · · · ⊂Mr =M such that eachMi/Mi1is Cohen-Macaulay and

dim(M1/M0) <dim(M2/M1) <· · ·<dim(Mr/Mr1).

A simplicial complex is called sequentially Cohen-Macaulay if the Stanley-Reisner ringR/I is sequentially Cohen-Macaulay. Also, we call a graphGsequentially Cohen-Macaulay (resp. vertex decomposable), ifGis a sequentially Cohen-Macaulay (resp. vertex decomposable) simplicial com- plex.

The following theorem, proved in [21], is one of our main tools in the study of projective dimension and regularity of the ringR/I.

Theorem1.5 ([21, Theorem 2.1]).LetI be a square-free monomial ideal.

Thenpd(I)=reg(R/I ).

Definition1.6. A monomial idealIin the ringR=k[x1, . . . , xn] haslin- ear quotientsif there exists an orderingf1, . . . , fmon the minimal generators ofI such that the colon ideal(f1, . . . , fi1):(fi)is generated by a subset of {x1, . . . , xn}for all 2≤im. We denote this ordering byf1< . . . < fmand we call it an order of linear quotients onG(I ).

A monomial ideal I generated by monomials of degree d has a linear resolutionifβi,j(I )=0 for allj =i+d. Linear quotients is a strong tool to determine some classes of ideals with linear resolution. The main tool in this way is the following lemma.

Lemma1.7 (See [9, Lemma 5.2]).Let I = (f1, . . . , fm)be a monomial ideal with linear quotients such that allfi’s are of the same degree. ThenI has a linear resolution.

2. Vertex decomposability and vertex splittable ideals

In this section we study the idealI for a vertex decomposable simplicial complex. We introduce the concept of a vertex splittable ideal and show that a simplicial complexis vertex decomposable if and only ifI is a vertex splittable ideal. Also, we prove that vertex splittable ideals have a Betti splitting

(6)

and have linear quotients. This gives us information about some homological invariants ofIsuch as Betti numbers.

Definition2.1. A monomial idealIinR=k[X] is calledvertex splittable if it can be obtained by the following recursive procedure.

(i) Ifuis a monomial andI = (u),I = (0)orI = R, thenI is a vertex splittable ideal.

(ii) If there is a variable xX and vertex splittable ideals I1 and I2 of k[X\ {x}] so thatI = xI1+I2,I2I1andG(I )is the disjoint union ofG(xI1)andG(I2), thenI is a vertex splittable ideal.

With the above notations if I = xI1 +I2 is a vertex splittable ideal, then xI1+I2is called avertex splittingforIandxis called asplitting vertexforI. Recently, the notion of ak-decomposable ideal was introduced in [19] and it was proved that it is the dual concept fork-decomposable simplicial complexes.

In the casek =0, 0-decomposable simplicial complexes are precisely vertex decomposable simplicial complexes. Consideringk =0 in [19, Definition 2.3], one can see that a shedding monomialuin a 0-decomposable idealInecessarily should satisfy the propertyIu = (0), whereIu = (vG(I ) : [u, v] = 1) and [u, v] is the greatest common divisor ofuandv, while in Definition 2.1, it is not the case, i.e., the way that a monomial ideal splits in Definition 2.1 is different from one in [19, Definition 2.3]. For example letI =(xx1, . . . , xxn).

ThenI =x(x1, . . . , xn). SettingI1=(x1, . . . , xn)andI2=(0)with the same notations of the above definition, it is easy to see thatx is a splitting vertex forI, while it is not a shedding monomial in the sense of [19, Definition 2.1], sinceIx =(0).

First we prove the following lemma.

Lemma2.2.Letbe a simplicial complex on the setX,xXbe a shedding vertex of,1=del(x)and2=lk(x). Then

I =xI1 +I2 and I2I1.

Proof. LetF()= {F1, . . . , Fm}andX=X\ {x}. We then haveI = (xX\F1, . . . , xX\Fm).Without loss of generality assume thatF1, . . . , Fk(km) are all the facets ofcontainingx. Sincex is a shedding vertex of, one can see that 1 = Fk+1, . . . , Fm. Also 2 = F1 \ {x}, . . . , Fk \ {x}. Therefore I1 = (xX\Fk+1, . . . , xX\Fm) and any generator of I2 is of the formxX\(Fi\{x}) = xX\Fi for any 1 ≤ ik. SoI2 = (xX\F1, . . . , xX\Fk).

ThusI =xI1 +I2.

To prove the last assertion, letxX\(Fi\{x}) be a generator ofI

2 for some 1≤ik. SinceFi\{x}is not a facet of del(x), there is a facetFjof del(x)

(7)

such thatFi \ {x} ⊆ Fj. HencexX\(Fi\{x})(xX\Fj)I1 which ensures thatI2I1.

The following theorem characterizes when is vertex decomposable in terms of the Alexander dual ofI.

Theorem2.3.A simplicial complexis vertex decomposable if and only ifIis a vertex splittable ideal.

Proof. Assume thatis a vertex decomposable simplicial complex with vertex setX. We use induction onn= |X|. Ifn=1, thenIis clearly vertex splittable. Suppose inductively that the result has been proved for smaller values ofn. In view of Lemma 2.2, we haveI =xI

1+I

2 andI

2I

1, wherexis a shedding vertex of,1=del(x)and2=lk(x). Since1

and2are vertex decomposable simplicial complexes onX\ {x}, inductive hypothesis implies thatI1 andI2 are vertex splittable ideals ink[X\ {x}].

This completes theonly if part.

To prove theifpart, let= F1, . . . , Fm. ThenI=(xX\F1, . . . , xX\Fm).

If I = (u) for some monomial u, I = (0) or I = R, then is either a simplex or empty simplicial complex which is vertex decomposable.

Otherwise, there is a variablexXand vertex splittable idealsI1andI2of k[X\ {x}] so thatI=xI1+I2,I2I1. Suppose inductively that the result is true for any vertex splittable ideal ink[X] with|X|< |X|. We show that xis a shedding vertex of,I1 = Idel(x) andI2 = Ilk(x). Without loss of generality assume thatF1, . . . , Fk (km)are all the facets ofcontaining x. SetX=X\ {x}. Then

I=(xX\F1, . . . , xX\Fk)+(xX\Fk+1, . . . , xX\Fm)

=(xX\(F1\{x}), . . . , xX\(Fk\{x}))+x(xX\Fk+1, . . . , xX\Fm).

Hence I1 = (xX\Fk+1, . . . , xX\Fm) and I2 = (xX\(F1\{x}), . . . , xX\(Fk\{x})).

SinceI2I1, one can see that for any 1≤ik, there is an integerk+1≤ jmsuch thatFi\{x} ⊆Fj. This ensures that del(x)= Fk+1, . . . , Fmand I1=Idel(x). Also, clearly lk(x)= F1\{x}, . . . , Fk\{x},I2=Ilk(x)and every facet of del(x)is a facet of. By the induction hypothesis, del(x)and lk(x)are vertex decomposable. Hence,is vertex decomposable as desired.

In the following, it is shown that vertex splittable ideals have linear quo- tients. Note that whenI is a square-free vertex splittable ideal, the following theorem implies the known fact that any vertex decomposable simplicial com- plex is shellable.

Theorem2.4.Any vertex splittable ideal has linear quotients.

(8)

Proof. LetI be a vertex splittable ideal. IfI = (u)for some monomial u,I =(0)orI =R, then clearly I has linear quotients. Otherwise, there is a variablexXand there are vertex splittable idealsI1andI2ofk[X\{x}] such thatI =xI1+I2andI2I1. By induction onn= |X|we prove the assertion.

Forn=1 the result is clear. By induction assume that for any setXwith|X|<

n, any splittable ideal of the ringk[X] has linear quotients. ThusI1andI2have linear quotients. Letf1 <· · ·< fr andg1< · · ·< gs be the order of linear quotients on the minimal generators ofI1andI2, respectively. We claim that the orderingxf1< · · ·< xfr < g1<· · ·< gs is an order of linear quotients on the minimal generators ofI. For any 1≤ir, the ideal(xf1, . . . , xfi1): (xfi)=(f1, . . . , fi1):(fi)is generated by variables by assumption. For an integer 1≤ is, let(g1, . . . , gi1) : (gi) = (xi1, . . . , xit)and consider the ideal(xf1, . . . , xfr, g1, . . . , gi1):(gi). We know thatxdivides any generator of the colon ideal(xfj) : (gi)for any 1≤ jr. SinceI2I1, there is an integer 1≤r such thatgi(f). Therefore(xf):(gi)=(x). It means that(xf1, . . . , xfr, g1, . . . , gi1) : (gi) = (x, xi1, . . . , xit). ThusI has linear quotients.

The following corollary is an immediate consequence of Lemma 1.7 and Theorem 2.4.

Corollary2.5.LetIbe a vertex splittable ideal generated by monomials in the same degrees. ThenIhas linear resolution.

The next theorem, which is a special case of [20, Corollaryhbox2.7], is our main tool to prove Theorem 2.8. First we need to recall the following definition.

Definition2.6. LetIbe a monomial ideal with linear quotients andf1<

· · ·< fmbe an order of linear quotients on the minimal generators ofI. For any 1≤im, setI(fi)is defined as

setI(fi)= {xk :xk(f1, . . . , fi1):(fi)}.

Theorem2.7 ([20, Corollary 2.7]).LetI be a monomial ideal with linear quotients with the orderingf1 < · · · < fm on the minimal generators ofI. Then

βi,j(I )=

deg(ft)=ji

|setI(ft)| i

.

Now, we are ready to bring one of the main results of this paper.

Theorem2.8.LetI =xI1+I2be a vertex splitting for the monomial ideal I. ThenI =xI1+I2is a Betti splitting.

(9)

Proof. By Theorem 2.4,I,I1andI2have linear quotients. Letf1<· · ·<

frandg1<· · ·< gsbe the order of linear quotients on the minimal generators ofI1 andI2, respectively. As it was shown in the proof of Theorem 2.4 the orderingxf1 < · · · < xfr < g1 < · · · < gs is an order of linear quotients on the minimal generators ofI, setI(xft)= setI1(ft)for any 1≤tr and setI(gk)= {x} ∪setI2(gk)for any 1≤ks. By Theorem 20,

βi,j(I )=

deg(ft)=ji1

|setI(xft)| i

+

deg(gk)=ji

|setI(gk)| i

.

Thus

βi,j(I )=

deg(ft)=ji1

|setI1(ft)| i

+

deg(gk)=ji

|setI2(gk)| +1 i

.

Applying the equality |setI2(gk)| +1

i

=

|setI2(gk)| i

+

|setI2(gk)| i−1

, we have

deg(gk)=ji

|setI2(gk)| +1 i

=

deg(gk)=ji

|setI2(gk)| i

+

deg(gk)=ji

|setI2(gk)| i−1

=βi,j(I2)+βi1,j1(I2).

Also

deg(ft)=ji1

|setI1(ft)| i

=βi,j1(I1).

Therefore

βi,j(I )=βi,j1(I1)+βi,j(I2)+βi1,j1(I2).

MoreoverI2I1implies that xI1I2 = xI2. Using this equality and the equalitiesβi,j1(I1)=βi,j(xI1)andβi1,j1(I2)=βi1,j(xI2), yields to

βi,j(I )=βi,j(xI1)+βi,j(I2)+βi1,j(xI1I2), which completes the proof.

Remark2.9. Francisco, Hà and Van Tuyl in [10] defined the concept of x-partition for a monomial ideal, whenxX. For a monomial ideal I, if

(10)

J is the ideal generated by all elements ofG(I ) divisible byx, andKis the ideal generated by all other elements ofG(I ), thenI = J +Kis called an x-partition. If I = J +K is also a Betti splitting, they call I = J +K anx-splitting. In this regard, every vertex splitting is anx-splitting for some variablexX, considering Theorem 2.8.

Remark2.10. From the proof of Theorem 2.8, one can see that for a vertex splittable idealIwith vertex splittingI =xI1+I2, the graded Betti numbers ofI can be computed by the following recursive formula

βi,j(I )=βi,j1(I1)+βi,j(I2)+βi1,j1(I2).

In the following corollary, the recursive formula is written for the graded Betti numbers ofI, whenis a vertex decomposable simplicial complex and consequently some inductive formulas for the regularity and projective dimension of the ringR/Iare presented. The inductive formula given below for reg(R/I)was also proved in [12] by a different approach.

Corollary2.11.Letbe a vertex decomposable simplicial complex,xa shedding vertex of,1=del(x)and2=lk(x). Then

(i) βi,j(I)=βi,j1(I1)+βi,j(I2)+βi1,j1(I2), (ii) pd(R/I)=max{pd(R/I1)+1,pd(R/I2)},

(iii) (Compare [12, Theorem 4.2].) reg(R/I) = max{reg(R/I1), reg(R/I2)+1}.

Proof. (i) follows from Theorems 2.3 and 2.8. (ii) and (iii) follow from (i), the equalities pd(I)=reg(R/I)and reg(I)=pd(R/I)in conjunction with Theorem 1.4.

3. Applications to vertex cover ideal of a vertex decomposable graph This section is devoted to some applications of the recursive formulas presented in previous section to some special classes of graphs. For a simple graphGby V (G)andE(G)we mean the vertex set and the edge set ofG, respectively.

For a vertex vV (G), set NG(v) = {uV (G) : {u, v} ∈ E(G)} and NG[v]=NG(v)∪{v}. Moreover, the cardinality ofNG(v)is called the degree ofvinGand is denoted by degG(v).

The following is one of our main results which is a consequence of Corol- lary 2.11.

Theorem 3.1. Let G be a vertex decomposable graph, vV (G) be a shedding vertex ofG,G =G\ {v},G=G\NG[v]anddegG(v)=t. Then

βi,j(I (G))=βi,j1(I (G))+βi,jt(I (G))+βi1,jt1(I (G)).

(11)

Proof. Let=G,1=del(v),2=lk(v)andNG(v)= {x1, . . . , xt}. Then I

G = (IG) = I (G). Moreover, G = {F : FV (G)} = {F:v /F} =1. ThusI

1 =IG =(IG)=I (G). Also I2 = (x(V (G)\{v})\F : FF(2)), since2 is a simplicial com- plex on the vertex set V (G)\ {v}. Moreover, FF(2) if and only if v, x1, . . . , xt/ F and FF(G). This also implies that for anyFF(2),FV (G). Thus(V (G)\ {v})\F = {x1, . . . , xt} ∪(V (G)\F ).

Therefore

I2 =x1· · ·xt(xV (G)\F :FF(G)).

Moreover, (xV (G)\F : FF(G)) = (IG) = I (G). Thus I2 = x1· · ·xtI (G). Using the equalityβi,j(x1· · ·xtI (G)) = βi,jt(I (G)), the result is now clear from Corollary 2.11.

By exploiting the following lemma, we state the recursive formula for the graded Betti numbers of the vertex cover ideal of a sequentially Cohen- Macaulay bipartite graph, which generalizes [10, Theorem 3.8] (since any Cohen-Macaulay bipartite graph is sequentially Cohen-Macaulay), and vertex cover ideal of chordal graphs in Corollaries 3.4 and 3.5.

Lemma3.2 ([24, Lemma 6]).LetGbe a graph andx, yV (G). IfNG[x]⊆ NG[y], thenyis a shedding vertex forG.

A graphGwith vertex setV (G)is calledbipartiteifV (G)can be partitioned into two setsXandY such that any edge ofGis of the form{x, y}for some xXandyY.

Van Tuyl and Villarreal in [23] gave a recursive characterization for a se- quentially Cohen-Macaulay bipartite graph as follows.

Theorem3.3 ([23, Corollary 3.11]). LetGbe a bipartite graph. ThenG is sequentially Cohen-Macaulay if and only if there are adjacent verticesx andywithdegG(x)=1such that the bipartite graphsG =G\NG[x]and G=G\NG[y]are sequentially Cohen-Macaulay.

Using this fact we can explain the formula for Betti numbers as follows.

Corollary3.4.LetGbe a sequentially Cohen-Macaulay bipartite graph, x, yV (G)be adjacent vertices withdegG(x)=1such thatG=G\NG[x]

andG = G\NG[y]are sequentially Cohen-Macaulay anddegG(y) = t. Then

βi,j(I (G))=βi,j1(I (G))+βi,jt(I (G))+βi1,jt1(I (G)).

Proof. From [22, Theorem 2.10], we know that any sequentially Cohen- Macaulay bipartite graphGis vertex decomposable. SinceNG[x]⊆NG[y], by

(12)

Lemma 3.2,yis a shedding vertex forG. Now the result is clear by Theorem 3.1 and the fact thatI (G)=I (G\ {y}).

In a graphG, a vertexxis called asimplicial vertexif the induced subgraph on the setNG[x] is a complete graph. A graphGis calledchordal, if it contains no induced cycle of length 4 or greater.

Dirac in [6] proved that any chordal graph has a simplicial vertex. We use this fact in the following corollary.

Corollary 3.5.Let G be a chordal graph with simplicial vertex x and yNG(x)withdegG(y)=t. LetG=G\ {y}andG=G\NG[y]. Then

βi,j(I (G))=βi,j1(I (G))+βi,jt(I (G))+βi1,jt1(I (G)).

Proof. By [24, Corollary 7] any chordal graph is vertex decomposable.

Sincexis a simplicial vertex, for anyyNG(x), we haveNG[x] ⊆ NG[y].

Thus by Lemma 3.2,yis a shedding vertex forG. Now apply Theorem 3.1.

The following theorem investigates another property of chordal graphs.

Theorem3.6.LetGbe a chordal graph. ThenI (Gc)is a vertex splittable ideal.

Proof. We prove the result by induction on|V (G)|. LetxV (G) be a simplicial vertex ofGandV (G)= {x, x1, . . . , xn}. IfGis a complete graph, then the result is clear. Assume thatGis not a complete graph and without loss of generality letNG(x)= {x1, . . . , xk}for some 1≤k < nandG0=G\{x}. ThenI (Gc)= x(xk+1, . . . , xn)+I (Gc0). Moreover, for any distinct integers i and j with 1 ≤ i, jk, since{xi, xj} ∈ E(G), then xixj/ I (Gc0). So I (Gc0)(xk+1, . . . , xn). SinceG0is chordal, by induction hypothesisI (Gc0) is vertex splittable. Also it is easy to see that any ideal which is generated by variables is a vertex splittable ideal. Thus(xk+1, . . . , xn)is vertex splittable.

SoI (Gc)is a vertex splittable ideal as desired.

Edge ideals with linear resolution were characterized in [11] as follows.

Theorem3.7 ([11, Theorem 1]).For a graphG, the edge idealI (G)has linear resolution if and only ifGcis a chordal graph.

Mohammadi in [16] proved that for a chordal graphG,(G) is vertex decomposable, where(G)is the clique complex ofG. By means of The- orem 3.6, we are able to give another proof of this result.

Corollary3.8.For a graphGthe following are equivalent.

(i) Gcis chordal,

(13)

(ii) I (G)is vertex splittable, (iii) Gis vertex decomposable, (iv) Gis Cohen-Macaulay.

Proof. (i)⇒(ii) is the statement of Theorem 3.6.

(ii)⇒(iii) follows from Theorem 2.3, noting the fact thatIG =I (G)and (G)=G.

(iii)⇒(iv) SinceG = V (G)\{x, y}:{x, y} ∈E(G), it is a pure vertex decomposable simplicial complex and so it is Cohen-Macaulay.

(iv)⇒(i) By Theorem 0.1, IG = I (G) has a linear resolution. So by Theorem 3.7,Gcis a chordal graph.

Acknowledgements. The authors would like to thank the referee for his/her valuable comments which substantially improved the quality of the paper. The research of the first author was in part supported by a grant from IPM (No. 91130021).

REFERENCES

1. Biermann, J., Francisco, C. A., Hà, H. T., and Van Tuyl, A.,Colorings of simplicial complexes and vertex decomposability, preprint, arXiv:math.AC/1209.3008v1.

2. Biermann, J., and Van Tuyl, A.,Balanced vertex decomposable simplicial complexes and theirh-vectors, Electron. J. Combin. 20 (2013), no. 3, Paper 15, 12 pp.

3. Björner, A., and Wachs, M. L.,Shellable nonpure complexes and posets. I, Trans. Amer. Math.

Soc. 348 (1996) no. 4, 1299-1327.

4. Björner, A., and Wachs, M. L.,Shellable nonpure complexes and posets. II, Trans. Amer.

Math. Soc. 349 (1997), no. 10, 3945–3975.

5. Cook II, D., and Nagel, U.,Cohen-Macaulay graphs and face vectors of flag complexes, SIAM J. Discrete Math. 26 (2012), no. 1, 89–101.

6. Dirac, G. A.,On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76.

7. Dochtermann, A., and Engström, A.,Algebraic properties of edge ideals via combinatorial topology, Electron. J. Combin. 16 (2009), no. 2, Special volume in honor of Anders Bjorner, Research Paper 2, 24 pp.

8. Eagon, J. A., and Reiner, V.,Resolutions of Stanley-Reisner rings and Alexander duality, J. Pure Appl. Algebra 130 (1998), no. 3, 265–275.

9. Faridi, S.,Simplicial trees are sequentially Cohen-Macaulay, J. Pure Appl. Algebra 190 (2004), no. 1–3, 121–136.

10. Francisco, C. A., Hà, H. T., and Van Tuyl, A.,Splittings of monomial ideals, Proc. Amer.

Math. Soc. 137 (2009), no. 10, 3271–3282.

11. Fröberg, R.,On Stanley-Reisner rings, Topics in Algebra, Banach Center Publications, 26 (1990), Part 2, 57–70.

12. Hà, H. T., and Woodroofe, R.,Results on the regularity of square-free monomial ideals, Adv.

in Appl. Math. 58 (2014), 21–36.

13. Herzog, J., Hibi, T., and Zheng, X.,Dirac’s theorem on chordal graphs and Alexander duality, European J. Combin. 25 (2004), no. 7, 949–960.

14. Herzog, J., and Hibi, T.,Componentwise linear ideals, Nagoya Math. J. 153 (1999), 141–153.

(14)

15. Khosh-Ahang, F., and Moradi, S.,Regularity and projective dimension of edge ideal ofC5-free vertex decomposable graphs, Proc. Amer. Math. Soc. 142 (2014), no. 5, 1567–1576.

16. Mohammadi, F.,Powers of the vertex cover ideal of a chordal graph, Comm. Algebra 39 (2011), no. 10, 3753–3764.

17. Moradi, S., and Kiani, D.,Bounds for the regularity of edge ideals of vertex decomposable and shellable graphs, Bull. Iranian Math. Soc. 36 (2010), no. 2, 267–277.

18. Provan, J. S., and Billera, L. J.,Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5 (1980), no. 4, 576–594.

19. Rahmati-Asghar, R., and Yassemi, S.,k-decomposable monomial ideals, Algebra Colloq. 22 (2015), Special Issue no. 1, 745–756.

20. Sharifan, L., and Varbaro, M.,Graded Betti numbers of ideals with linear quotients, Matem- atiche (Catania) 63 (2008), no. 2, 257–265.

21. Terai, N.,Alexander duality theorem and Stanley-Reisner rings. Free resolutions of coordinate rings of projective varieties and related topics(Japanese) (Kyoto, 1998), Sürikaisekiken- kyüsho Kökyüroku no. 1078 (1999), 174–184.

22. Van Tuyl, A.,Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity, Arch. Math. (Basel) 93 (2009), no. 5, 451–459.

23. Van Tuyl, A., and Villarreal, R.,Shellable graphs and sequentially Cohen-Macaulay bipartite graphs, J. Combin. Theory Ser. A 115 (2008), no. 5, 799–814.

24. Woodroofe, R.,Vertex decomposable graphs and obstructions to shellability, Proc. Amer.

Math. Soc. 137 (2009), no. 10, 3235–3246.

25. Woodroofe, R.,Chordal and sequentially Cohen-Macaulay clutters, Electron. J. Combin. 18 (2011), no. 1, Paper 208, 20 pp.

SOMAYEH MORADI

DEPARTMENT OF MATHEMATICS ILAM UNIVERSITY

P.O. BOX 69315-516 ILAM

IRAN and

SCHOOL OF MATHEMATICS

INSTITUTE FOR RESEARCH IN FUNDAMENTAL SCIENCES (IPM) P.O. BOX 19395-5746

TEHRAN IRAN

E-mail:somayeh.moradi1@gmail.com

FAHIMEH KHOSH-AHANG DEPARTMENT OF MATHEMATICS ILAM UNIVERSITY

P.O. BOX 69315-516 ILAM

IRAN

E-mail:fahime khosh@yahoo.com

Referencer

RELATEREDE DOKUMENTER

 The vertex cover problem is to find a vertex cover of minimum size in a given undirected graph...  The vertex cover problem is to find a vertex cover of minimum size in a given

 Extend piecewise linear function by choosing basis of linear hat functions (value 1 at vertex i and zero at others):.. + Integral of

To appraise free energy, enthalpy, and entropy of activated and stable complexes along this path, we need values of the three rate constants and their temperature dependence

• Independent set problem: Given graph G and an integer k, is there a vertex cover of size ≤ k..

• Independent set problem: Given graph G and an integer k, is there a vertex cover of size ≤ k?.

A more sophisticated model for group analysis could be developed with the Bayesian framework that do not assume vertex-to-vertex correspondence and that can adapt to different levels

The single vertex resulting from the leaf node is then moved to the parent node’s position during the final vertex placement.. The hemisphere node should also work with the

This project has focused on investigation of the stability and robustness of Cu(II) complexes of two adamanzanes: [2 4 .3 1 ]adz and [3 5 ]adz, and on investigation of the