DOI 10.1007/s10801-009-0171-6
Regularity, depth and arithmetic rank of bipartite edge ideals
Manoj Kummini
Received: 14 October 2008 / Accepted: 11 February 2009 / Published online: 27 February 2009
© Springer Science+Business Media, LLC 2009
Abstract We study minimal free resolutions of edge ideals of bipartite graphs. We associate a directed graph to a bipartite graph whose edge ideal is unmixed, and give expressions for the regularity and the depth of the edge ideal in terms of invariants of the directed graph. For some classes of unmixed edge ideals, we show that the arithmetic rank of the ideal equals projective dimension of its quotient.
Keywords Monomial ideals·Graded free resolutions·Arithmetic rank
1 Introduction
LetGbe a simple graph on a finite vertex setV without any isolated vertices. Letkbe a field. SetR=k[V], treating the elements ofV as indeterminates. LetI be the edge ideal of G inR, i.e., the ideal generated by the square-free quadratic monomials xy, where x, y∈V and there is an edge betweenx andy inG. In this paper, we study (Castelnuovo-Mumford) regularity, depth and arithmetic rank of edge ideals of bipartite graphs. Recall that Gis said to be bipartite if there exists a partition V =V1
V2such that every edge inGis of the formxywithx∈V1andy∈V2. WhenI is unmixed (more generally, whenGhas a perfect matching — see Sec- tion 2 for details), we have that |V1| = |V2| =htI. To such a bipartite graph, we associate a directed graphdG on the vertex set{1, . . . ,htI}. This is motivated by a paper of J. Herzog and T. Hibi [4] which studies a similar association between posets and bipartite graphs with Cohen-Macaulay edge ideals. Using this, we show that Theorem 1.1 Let G be an unmixed bipartite graph with edge ideal I. Then regR/I=max{|A| :Ais an antichain indG}. In particular, regR/I is the maximum size of a pairwise disconnected set of edges inG.
M. Kummini (
)Purdue University, Lafayette, IN 47907, USA e-mail:[email protected]
We say thatGis unmixed (respectively, Cohen-Macaulay) ifR/I is unmixed (re- spectively, Cohen-Macaulay). The notion of pairwise disconnected sets of edges in graphs was introduced by X. Zheng [19] who showed that ifI is the edge ideal of a tree (an acyclic graph) then regR/I is the maximum size of a pairwise disconnected set of edges [19, Theorem 2.18]. Additionally, see [5, Corollary 6.9], for the same conclusion for the edge ideals of chordal graphs. For arbitrary graphs, the maximum size of a pairwise disconnected set of edges is a lower bound for regR/I; this follows essentially from [6, Lemma 2.2].
A strong component of a directed graph is a set of vertices maximal with the property that for everyi, jin the set, there is a directed path fromitoj. The following statement about depth, which follows from Corollary3.7, has also been observed by C. Huneke and M. Katzman:
Theorem 1.2 LetGbe an unmixed bipartite graph, with edge idealIand associated directed graphdG. IfdGhaststrong components, then depthR/I≥t.
The problem of determining the minimum number of equations required to gen- erate a monomial ideal up to radical (called the arithmetic rank of the ideal) was first studied by P. Schenzel and W. Vogel [11], T. Schmitt and Vogel [12] and G. Lyubeznik [8]. Lyubeznik showed that for a square-free monomial ideal I, araI≥pdR/I [8, Proposition 3]. Upper bounds for arithmetic rank have also been considered by M. Barile [1] and [2], building on the work of Schmitt and Vogel mentioned above. In [7], K. Kimura, N. Terai and K.-i. Yoshida raise the question of equality of araI and pdR/I, and answer it in some cases [7, Theorem 1.1]. It is known, however, due to Z. Yan [17, Example 2] that, in general, pdR/I and araI need not be equal.
IfG is an unmixed bipartite graph, then we can construct a maximal subgraph G˘ which is Cohen-Macaulay; this corresponds to taking a maximal directed acyclic subgraph ofdG. IfGis, further, Cohen-Macaulay, thenG˘ =G. LetI˘be the edge ideal ofG. We show that˘
Theorem 1.3 LetGbe an unmixed bipartite graph with edge idealI. Then araI ≤ araI˘+pdR/I−htI. If further a maximal acyclic subgraph ofdGcan be embedded inN2, then araI=pdR/I.
Thus, ifGis Cohen-Macaulay and dG has an embedding inN2, thenR/I is a set-theoretic complete intersection, i.e., it can be defined by htI equations.
The next section contains definitions, notation and some preliminary observations.
Theorems1.1and1.2are proved in Section3. A proof of Theorem1.3is presented in Section4.
2 Edge ideals
We fix the following notation:kis a field,V is a finite set of indeterminates overk, Gis a simple graph onV without any isolated vertices andR=k[V]is a polynomial
ring. We takeI⊆Rto be a square-free monomial ideal; later, we will assume thatIis the edge ideal ofG. Setc:=htI. References for homological aspects of monomial ideals, for graph theory and for results on posets, respectively, are [9, Part I], [16]
and [10, Chapter 3]. We will use “multigraded” and “multidegree” to refer to the grading ofRbyN|V|and the degrees in this grading.
The multigraded Betti numbers of R/I are βl,σ(R/I ):=dimkTorRl (k, R/I )σ. Forj ∈Z, the (N-graded) Betti numbers areβl,j :=dimkTorRl (k, R/I )j. We note thatβl,j(·)=
βl,σ(·), where the sum is taken over the set ofσ with|σ| =j. (Here
|.| denotes the total degree of a multidegree.) To represent a multidegree, we will often use the unique monomial inRof that multidegree; further, if that monomial is square-free, we will use its support, i.e., the set of variables dividing it.
Letbe the Stanley-Reisner complex of I. The correspondence between non- faces of and monomials in I can also be expressed as follows: for any mono- mial prime idealp∈SpecR,I⊆pif and only ifp=(F )R, the ideal generated by¯ F¯ :=V \F, for someF ∈[9, Theorem 1.7]. Thus minimal prime ideals ofR/I correspond to complements of maximal faces of. The Alexander dual of, de- noted, is the simplicial complex{ ¯F :F ∈}. Letm∈NandFi⊆V ,1≤i≤m be such that
x∈Fix,1≤i≤m are the minimal monomial generators of I. The Alexander dual ofI, denotedI, is the square-free monomial idealm
i=1(Fi). IfI is the Stanley-Reisner ideal of, thenF¯i,1≤i≤mare precisely the facets of. HenceIis the Stanley-Reisner ideal of. We will need the following theorem of Terai:
Proposition 2.1 (Terai [13]; [9, Theorem 5.59]) For any square-free monomial idealJ, pdR/J=regJ.
The relation between simplicial homology and multigraded Betti numbers is given by Hochster’s Formula [9, Corollary 5.12 and Corollary 1.40]. Forσ⊆V, we denote by|σ the simplicial complex obtained by taking all the faces ofwhose vertices belong toσ. Note that |σ is the Stanley-Reisner complex of the idealI ∩k[σ].
Similarly, define the link, lk(σ ), ofσinto be the simplicial complex{F\σ:F∈ , σ⊆F}. Its Stanley-Reisner ideal ink[ ¯σ]is(I:σ )∩k[ ¯σ]. First, the multidegrees σ withβl,σ(R/I )=0 are square-free. Secondly, for all square-free multidegreesσ,
βl,σ(R/I )=dimkH|σ|−l−1(|σ;k), and (1) βl,σ(I)=dimkHl−1(lk(σ )¯ ;k).
Combining these two formulas we see that βl,σ(I)=β|σ|−l,σ
R (I: ¯σ )
. (2)
We add, parenthetically, that links of faces in Cohen-Macaulay complexes are them- selves Cohen-Macaulay.
We now describe how the graded Betti numbers change under restriction to a sub- set of the variables and under taking colons.
Lemma 2.2 LetI⊆R=k[V]be a square-free monomial ideal,x∈V,l, j ∈Nand σ⊆V with|σ| =j.
(a) LetW⊆V andJ=(I∩k[W])R. Then,
βl,σ(R/J )= 0, σW, βl,σ(R/I ), σ⊆W.
In particular,βl,j(R/J )≤βl,j(R/I ).
(b) Ifβl,σ(R/(I:x))=0, thenβl,σ(R/I )=0 orβl,σ∪{x}(R/I )=0.
Proof (a): The second assertion follows from the first, which we now prove. Let˜ be the Stanley-Reisner complex ofJ. Since for allx∈V \W,xdoes not belong to any minimal prime ideal ofR/J, we see that every maximal face of˜ containsV \W. Hence ifσ⊆W, then for allx∈σ\W,˜|σ is a cone with vertexx, which, being contractible, has zero reduced homology. Applying (1), we see thatβl,σ(R/J )=0.
Now letσ⊆W andF ⊆V. ThenF ∈|σ if and only ifI⊆(F )R¯ andF ⊆σ, which holds if and only ifJ⊆(F )R¯ andF ⊆σ, which, in turn, holds if and only if F∈ ˜|σ. Apply (1) again to get
βl,σ(R/J )=H|σ|−l−1(˜|σ;k)=H|σ|−l−1(|σ;k)=βl,σ(R/I ).
(b): We take the multigraded exact sequence ofR-modules:
0 (IR:x)(−x) R
I
R
(I,x) 0. (3)
The corresponding multigraded long exact sequence of Tor is
· · · Torl+1(k,(I,x)R ) Torl(k,(IR:x)(−x))
Torl(k,RI) · · ·.
LetW=V\ {x}andJ=(I∩k[W])R. Sinceβl,σ(R/(I :x))=0 andxdoes not divide any monomial minimal generator of(I:x), we have, by the same argument as in (2.2),σ⊆W. Letτ =σ∪ {x}. First observe that
Torl
k, R
(I:x)
σ
Torl
k, R
(I:x)(−x)
τ
.
Let us assume that βl,τ(R/I )=0, because, if βl,τ(R/I )=0, there is nothing to prove. Then, the above long exact sequence of Tor, restricted to the multide- greeτ, implies that Torl+1(k,(I,x)R )τ=0. Now, since(I, x)=(J, x), we see further Torl+1(k,(J,x)R )τ =0.
Sincexis a non-zerodivisor onR/J, we have a multigraded short exact sequence
0 RJ(−x) RJ (J,x)R 0,
which gives the following long exact sequence of Tor:
· · · Torl+1(k,RJ) Torl+1(k,(J,x)R )
Torl(k,RJ(−x)) · · ·.
Sincexdoes not divide any minimal monomial generator ofJ,βl+1,τ(R/J )=0.
Therefore Torl(k,RJ(−x))τ =0, or, equivalently, Torl(k,RJ)σ =0. By (2.2) above,
βl,σ(R/I )=0.
Ifp⊆Ris a prime ideal such that htp=c=htI andI⊆p, then we say thatp is an unmixed associated prime ideal ofR/I. Denote the set of unmixed associated prime ideals ofR/I by UnmR/I. Unmixed prime ideals are necessarily minimal overI, so UnmR/I ⊆AssR/I; we say that I or R/I is unmixed if UnmR/I = AssR/I.
We now restrict our attention to edge ideals of graphs. Every square-free quadratic monomial ideal can be considered as the edge ideal of some simple graph. The theory of edge ideals is systematically developed in [14, Chapter 6]. HereafterI is the edge ideal ofG, which we have set to be a simple graph onV. A vertex cover ofGis a setA⊆V such that wheneverxy is an edge ofG,x∈Aory∈A. It is easy to see that for allA⊆V,Ais a vertex cover ofGif and only if the prime ideal(x:x∈A) containsI. SinceI is square-free,R/I is reduced; therefore, AssR/I is the set of minimal prime ideals containingI. These are monomial ideals, and, hence, are in bijective correspondence with the set of minimal vertex covers of G. We will say thatGis unmixed (respectively, Cohen-Macaulay) ifR/I is unmixed (respectively, Cohen-Macaulay). Observe that ifGis unmixed, then all its minimal vertex covers have the same size.
Ifxyis an edge ofG, then we say thatx andy are neighbours of each other. An edge is incident on its vertices. We say that an edgexyis isolated if there are no other edges incident onxor ony. LetGbe a graph. A matching inGis a maximal (under inclusion) set m of edges such that for allx∈V, at most one edge in m is incident onx. Edges in a matching form a regular sequence onR. We say thatGhas perfect matching, or, is perfectly matched, if there is a matching m such that for allx∈V, exactly one edge in m is incident onx.
Lemma 2.3 LetGbe a bipartite graph on the vertex set V =V1
V2, with edge idealI. ThenGhas a perfect matching if and only if|V1| = |V2| =htI. In particular, unmixed bipartite graphs have perfect matching.
Proof IfG has a perfect matching, then |V1| = |V2|. Moreover, by König’s theo- rem [16, Theorem 3.1.16], the maximum size of any matching equals the minimum size of any vertex cover; hence|V1| = |V2| =htI. Conversely, if|V1| = |V2| =htI, then, again by König’s theorem,Ghas a matching of|V1| = |V2|edges, i.e., it has a perfect matching.
IfGis unmixed, then every minimal vertex cover ofGhas the same size. Observe that bothV1andV2are minimal vertex covers ofG.
Discussion 2.4 Letdbe any directed graph on[c], and denote the underlying undi- rected graph ofdby|d|. We will writej iif there is a directed path fromitoj ind. Byj i(and, equivalently,ij) we mean thatjiorj =i. ForA⊆ [c], we say thatjAif there existsi∈Asuch thatji. We say that a setA⊆ [c]is an antichain if for alli, j∈A, there is no directed path fromitoj ind, and, byAd, denote the set of antichains ind. We consider∅as an antichain. A coclique of|d|is a setA⊆ [c]such that for alli=j∈A,iandjare not neighbours in|d|. Antichains in dare cocliques in|d|, but the converse is not, in general, true. We say thatdis acyclic if there are no directed cycles, and transitively closed if, for alli, j, k∈ [c], whenever ij andj kare (directed) edges ind,ikis an edge. Observe thatdis a poset under the orderif and only if it is acyclic and transitively closed. Ifdis a poset, we say that, fori, j∈ [c],j coversiifjiand there does not existjsuch thatj ji. Let Gbe a bipartite graph onV =V1
V2with perfect matching. LetV1= {x1,· · ·, xc} andV2= {y1,· · ·, yc}. After relabelling the vertices, we will assume thatxiyi is an edge for alli∈ [c]. We associateGwith a directed graphdG on[c]defined as fol- lows: fori=j∈ [c],ij is an edge ofdGif and only ifxiyj is an edge ofG. (Here, by ij, we mean the directed edge fromitoj.) Observe thatdG is simple, i.e., without loops and multiple edges. Letκ(G)denote the largest size of any coclique in|dG|.
The significance ofκ(G)is that it gives a lower bound for regR/I. Following Zheng [19], we say that two edgesvwandvw of a graphG are disconnected if they are no more edges between the four verticesv, v, w, w. A set a of edges is pairwise disconnected if and only if(I∩k[Va])Ris generated by the regular sequence of edges in a, where by Va, we mean the set of vertices on which the edges in a are incident. The latter condition holds if and only if the subgraph ofGinduced on Va, denoted as G|Va, is a collection of|a|isolated edges. In particular, the edges in any pairwise disconnected set form a regular sequence inR. Setr(I ):=max{|a| : a is a set of pairwise disconnected edges inG}.
Lemma 2.5 LetGbe bipartite graph with perfect matching. Then, with notation as in Discussion2.4,r(I )≥κ(G)≥max{|A| :A∈AdG}.
Proof IfA⊆ [c]is a coclique of|dG|, we easily see that the edges{xiyi:i∈A}are pairwise disconnected inG. The assertion now follows from the observation, which we made in Discussion2.4, that any antichain indGis a coclique of|dG|. The assertion of Theorem1.1is that whenGis an unmixed bipartite graph, equal- ity holds in the above lemma and that this quantity equals regR/I. We will prove Theorem1.1in the next section; now, we relate some properties of bipartite graphs with their associated directed graphs.
Lemma 2.6 LetGbe bipartite graph with perfect matching, and adopt the notation of Discussion2.4. Letji. Then for allp∈UnmR/I, ifyi ∈p, thenyj∈p.
Proof Applying induction on the length of a directed path fromitoj, we may as- sume, without loss of generality, thatij is a directed edge ofdG. Letp∈UnmR/I
andk∈ [c]. Sincexkyk∈I,xk∈p oryk∈p. Since htp=c, in fact,xk ∈pif and only ifyk∈p. Now sinceyi ∈p,xi∈p, so(I:xi)⊆p. Note that sincexiyj is an
edge ofG,yj∈(I:xi).
Theorem 2.7 LetGbe a bipartite graph on the vertex setV =V1
V2.
(a) [15, Theorem 1.1]Gis unmixed if and only ifGhas a perfect matching anddG is transitively closed.
(b) [4, Lemma 3.3 and Theorem 3.4]Gis Cohen-Macaulay if and only ifGis per- fectly matched and the associated directed graphdG is acyclic and transitively closed, i.e., it is a poset.
Discussion 2.8 Letd be a directed graph. We say that a pairi, j of verticesd are strongly connected if there are directed paths fromi toj and fromj toi; see [16, Definition 1.4.12]. A strong component ofdis an induced subgraph maximal under the property that every pair of vertices in it is strongly connected. Strong components ofd form a partition of its vertex set. Now let Gbe a bipartite graph with perfect matching. LetZ1, . . . ,Zt be the vertex sets of the strong components ofdG. Define a directed graphdon[t]by setting, fora=b∈ [t],abto be a directed edge (from atob) if there exists a directed path indGfrom any (equivalently, all, sincedG|Za
is strongly connected) of the vertices inZato any (equivalently, all, sincedG|Zb is transitively closed) of the vertices inZb. We observe thatdhas no directed cycles.
Now assume further thatG is unmixed. Then, sincedG is transitively closed,d is transitively closed, i.e., it is a poset under the order induced fromdG. We will use the same notation for the induced order, i.e., say that ba if there is a directed edge from a to b. Define the acyclic reduction ofG to be the bipartite graph G on new vertices{u1, . . . , ut}
{v1, . . . , vt}, with edgesuava, for all 1≤a≤t and uavb, for all directed edgesabofd. LetS=k[u1, . . . , ut, v1, . . . , vt], with standard grading. LetI⊆Sbe the edge ideal ofG. Let ζi= |Zi|,1≤i≤t. For a multidegree τ=
iusii
vtii, setτζ=
iusiiζi vtiiζi.
Lemma 2.9 LetGbe an unmixed bipartite graph with edge idealI. For an antichain A=∅ ofd, let A= {j ∈Zb:bA}. Let ∅=∅. Then AssR/I = {(xi :i∈
A)+(yi :i∈ A):A∈Ad}.
Proof Let p∈AssR/I. Let U:= {b:yj ∈p for some j ∈Zb}. It follows from Lemma 2.6that yj ∈p for all j ∈
b∈UZb and that if b b for some b∈U, thenb∈U. Now, the minimal elements ofUform an antichainAunder. Hence {j:yj∈p} = A, showing AssR/I ⊆ {(xi:i∈ A)+(yi:i∈ A):A∈Ad}.
Conversely, letA∈Adandp:=(xi :i∈ A)+(yi:i∈ A). Since htp=c= htI, it suffices to show thatI⊆pin order to show thatp∈AssR/I. Clearly, for all 1≤i≤c,xiyi ∈p. Takei=j such thatxiyj ∈I. Ifi∈ A, then there is nothing to be shown. Ifi∈ A, then there exista, b, b such thata∈A,ba,i∈Zband j∈Zb. Sinceij is a directed edge ofdG,bb ind. Henceba, andj ∈ A,
givingyj∈p. This shows thatI⊆p.
3 Regularity and depth
The content of Lemma2.9 is that there are subsetsW ⊆V such that for all p∈ AssR/I, ifp∩W=∅thenW⊆p. Looking atI, we see that for all minimal gen- eratorsg of I, if any element of W dividesg, then all elements ofW divide g.
Label the minimal monomial generators of I as g1, . . . , gs, gs+1, . . . , gm so that every element ofW dividesg1, . . . , gs and no element ofW dividesgs+1, . . . , gm. Fix x ∈W. For i=1, . . . , s, set hi := x|W|
y∈Wygi and h¯i := x
y∈Wygi. Let J = (h1, . . . , hs, gs+1, . . . , gm)andJ=(h¯1, . . . ,h¯s, gs+1, . . . , gm). Let φ:R→R be the ring homomorphism that sendsx→x|W|andy→y, for ally=x∈V. We make two observations: first, thatIis a polarization ofJ, and, secondly, thatJ=φ (J).
Hence theN-graded Betti numbers ofIandJ are identical [9, Exercise 3.15]. Fur- ther, the following lemma shows thatβl,σ(R/J )=0 if and only ifx|W|dividesσand βl, σ
x|W|−1(R/J )=0.
Lemma 3.1 LetB1=k[x1, . . . , xn]andB2=k[y1, . . . , yn]. Letξ1, . . . , ξnbe pos- itive integers. Set degxi=1 and degyi =ξn for all 1≤i≤n. Define a ring homo- morphismφ:B2→B1 by sendingyi →xiξi. Then for any acyclic complexG• of finitely generated gradedB2-modules (with degree-preserving maps),G•⊗B2 B1is an acyclic complex of finitely generated gradedB1-modules (with degree-preserving maps).
Proof Acyclicity ofG•⊗B2 B1 follows from the fact thatB1 is a free and hence flat B2-algebra. The maps inG•⊗B2 B1 are degree-preserving since φ preserves
degrees.
Proposition 3.2 LetGbe an unmixed bipartite graph, with edge idealI and acyclic reductionG. Let I⊆Sbe the edge ideal ofG. Then reg R/I=pdI
and pdR/I= max{|τζ| −l:βl,τ
I
=0}.
Proof By Proposition2.1, regR/I =pdI and pdR/I =regI. Hence it suffices to show that pdI=pdI
and regI=max{|σζ| −l:βl,σ
I
=0}. From Lemma2.9, with the notation used there, it follows that
I=
⎛
⎝
i∈ A
xi·
i∈ A
yi:A∈Ad
⎞
⎠=
⎛
⎜⎜
⎝
bA i∈Zb
xi·
bA i∈Zb
yi:∅=A∈Ad
⎞
⎟⎟
⎠+ c
i=1
xi
.
For eacha∈ [t], fixia∈Za. Now, as theZaform a partition of[c], we see thatIis a polarization of the ideal
J =
⎛
⎝
bA
xiζb
b ·
bA
yiζb
b :∅=A∈Ad
⎞
⎠+ t
b=1
xiζb
b
⊆S:=k[xi1, . . . , xit, yi1, . . . , yit].
Notice that S S (which, we recall, is the polynomial ring on the vertex set of the acyclic reductionG) under the map φ:xia →ua andφ:yia →va, and that φ (√
J )=I
. Thereforeβl,σ(√
J )=βl,φ (σ )I
. It now suffices to show that pdJ=pd√
J and that regJ=max{|τζ| −l:βl,τ(√
J )=0}. This, being the same argument as in the opening paragraph of this section, follows from the preceding
lemma.
Remark 3.3 LetGbe an unmixed graph with acyclic reductionG. If I⊆RandI⊆S are the respective edge ideals, then it follows from Proposition3.2that regR/I = pdI
=regS/I.
Lemma 3.4 LetG be an unmixed bipartite graph with acyclic reductionG. Then max{|A| :A∈AdG} =max{|A| :A∈AdG}.
Proof LetA= {i1, . . . , ir} ⊆ [c]be an antichain indG. Choosea1, . . . , ar∈ [t]such thatij ∈Zaj. Since dG is transitively closed, it follows that{a1, . . . , ar}is an an- tichain indG. Conversely, if{a1, . . . , ar}is an antichain indG, then for any choice of ij∈Zaj,{i1, . . . , ir}is an antichain indG. We now prove Theorem1.1. IfGis a tree — trees are bipartite — then regR/I is the maximum size of a pairwise disconnected set of edges inG, without the assump- tion thatGis unmixed [19, Theorem 2.18]. However, for bipartite graphsGthat are not trees, we need to assume thatGis unmixed. For example, ifGis the cycle on eight vertices, we can choose at most two edges that are pairwise disconnected, while regR/I=3.
Theorem 1.1 Let G be an unmixed bipartite graph with edge ideal I. Then regR/I=max{|A| :Ais an antichain indG}. In particular, regR/I is the maximum size of a pairwise disconnected set of edges inG.
Proof Since regR/I≥r(I )(see the paragraph on page429following the statement of Theorem1.1), the latter statement follows from the first statement along with Lemma2.5. In order to prove the first statement, letGbe the acyclic reduction of Gon the vertex set{u1, . . . , ut}
{v1, . . . , vt}. Recall thatGis a Cohen-Macaulay bipartite graph. As in Discussion 2.8, let S=k[u1, . . . , ut, v1, . . . , vt]. Let I ⊆S be the edge ideal of G. Remark 3.3and Lemma 3.4give that it suffices to prove the theorem for Cohen-Macaulay bipartite graphs. IfGis Cohen-Macaulay, thendG is a poset. From [4, Corollary 2.2], taken along with Proposition2.1, we see that pdR/I=max{|A| :A∈AdG}. (Note thatIis the idealHdG, in the notation of [4],
with thexiand theyj interchanged.)
Remark 3.5 Let G be a Cohen-Macaulay bipartite graph with edge ideal I, with htI =c. Then regR/I ≤c. If regR/I =c, thenR/I is a complete intersection, or, equivalently,G consists of c isolated edges. We see this as below: LetdG be the
associated directed graph on[c]. Since regR/I is the maximum size of an antichain indG, regR/I ≤c. If regR/I =c, we see thatdG has an antichain ofcelements, which implies that for alli=j∈ [c],ij orji, i.e.,xiyj is not an edge ofG.
We would now like to give a description of depthR/I for an unmixed bipar- tite edge ideal I in terms of the associated directed graph. First, we determine the multidegrees with non-zero Betti numbers for its Alexander dual. Let Gbe a Cohen-Macaulay bipartite graph. For antichainsB⊆AofdG,A=∅, setσA,B:=
iAxi
iAyi
i∈Bxi. Set σ∅,∅=c
i=1xi. With this notation, we restate [4, Theorem 2.1] as follows:
Theorem 3.6 LetGbe a Cohen-Macaulay bipartite graph with edge idealI. For all l≥0, and multidegreesσ, ifβl,σ(I)=0, thenβl,σ(I)=1 andσ=σA,B for some antichainsB⊆AofdGwith|B| =l.
(Although the multidegrees in which the Betti numbers are non-zero are not ex- plicitly given in the statement of [4, Theorem 2.1], we can determine them easily from the description of the differentials given there, prior to stating the theorem.
Note, again, that the roles of thexi and theyj are the opposite of what we follow.) Corollary 3.7 LetGbe an unmixed bipartite graph with edge idealI. Letc=htI. Lett, ζ1, . . . , ζt,dbe as in Discussion2.8. Then
depthR/I=c−max
i∈B
ζi− |B| :Bis an antichain ofd
.
Proof Let G, S, I be as in Discussion 2.8. From Theorem 3.6, we know that if βl,σ((I ))=0 for some multidegree σ ⊆ {u1, . . . , ut, v1, . . . , vt}, then σ =σA,B
for some antichainsB⊆Aofd, with|B| =l. Now, in S, degσA,B=
iAζi + iAζi+
i∈Bζi=c+
i∈Bζi. Hence reg(I )=c+max
i∈B
ζi− |B| :Bis an antichain ofd
.
Note that depthR =dimR =2c. Now apply Proposition 3.2, followed by the Auslander-Buchsbaum formula, to obtain the conclusion.
The above proof also shows that ifGis a bipartite graph such thatR/I satisfies Serre’s condition(S2)(defined, e.g., in [3, Section 2.1]) thenGis Cohen-Macaulay.
For, ifR/I satisfies(S2), then it is unmixed andIis linearly presented, i.e., the non- zero entries in any matrix giving a presentation ofIare linear. This is a special case of [18, Corollary 3.7]. It follows, with the notation of the proof, that for all antichains A=∅ofd, and for alla∈A, degσA,{a}=c+ζa=c+1, giving that every strong component ofdGhas exactly one element. In other words,Gis Cohen-Macaulay. We can now prove Theorem1.2.
Theorem 1.2 LetGbe an unmixed bipartite graph, with edge idealIand associated directed graphdG. IfdGhaststrong components, then depthR/I≥t.
Proof To show that depthR/I≥t, it suffices to show that, for all antichainsBofd, t+
i∈Bζi− |B| ≤c. Sincec=t
i=1ζi, it suffices to show thatt− |B| ≤
i∈Bζi,
which is true sinceζi≥1 for alli.
Remark 3.8 The above bound is sharp. Given positive integerst≤c, and a posetdon t vertices, we can find an unmixed bipartite graphGon the vertex setV =V1
V2
with edge idealI such that|V1| = |V2| =cand depthk[V]/I =t. Choose any an- tichainB indand setζi=1 for alli∈B. Chooseζi≥1, i∈B such that
i∈Bζi= c−t+ |B|. Now construct a directed graphdoncvertices by replacing the vertexi ofdby directed cycle ofζi vertices and then taking its transitive closure. Label the vertices ofdwith[c]. LetGbe a bipartite graph onV = {x1, . . . , xc}
{y1, . . . , yc} such that xiyi is an edge for all i∈ [c] and xiyj is an edge whenever ij is a di- rected edge of d. Then G is an unmixed graph. We know from the corollary that t≤depthR/I≤c−
i∈Bζi− |B| =t.
4 Arithmetic rank
The two statements of Theorem1.3will be proved separately in Proposition4.2and in Proposition4.11.
Discussion 4.1 LetGbe an unmixed bipartite graph on{x1, . . . , xc}
{y1, . . . , yc}. Adopt the notation of Discussion2.8. Choose an acyclic transitively closed subgraph ofdGwhich is maximal under inclusion of edge sets; call itd. It is a poset, with the˘ order induced fromdG. We will denote this order byto avoid confusion with. (Recall thatdoes not define a partial order ifGis not Cohen-Macaulay.) LetG˘ be the Cohen-Macaulay bipartite graph on{x1, . . . , xc}
{y1, . . . , yc}corresponding to d; denote its edge ideal by˘ I˘.
Proposition 4.2 With notation as above, araI≤araI˘+pdR/I−htI.
Proof On the set{xjyi:j i, j=iandxjyiis an edge ofG}, define a partial order:
xjyi> xjyiwheneverj j, j =j, ii, i=i. Call this posetP. (These are the edges ofGthat do not belong toG. If˘ xjyi is such an edge, theni andj belong to the same strong component ofdG.) We now claim that every antichain inP has at most max
a∈Bζa− |B| :Bis an antichain ofd
elements; this quantity, as we note from Corollary3.7, equalsξ :=pdR/I −htI. Let {xjkyik :1≤k≤l}with jkik,1≤k≤lbe an antichain inP. First, there exista1, . . . , al such thatik, jk∈ Zak; this arises from the fact that jk ik. If ak2 ak1, then for, i, j ∈Zak1 and i, j∈Zak2,xjyi> xjyi, so ifak2 =ak1, then they are incomparable. Therefore, to prove the claim, it suffices to show that ifa1=. . .=al=a, say, thenl≤ζa−1.
This follows easily, for, in this case, any antichain inP can contain at most one edge for each value ofj−i, and 1≤j−i≤ζa−1. Moreover, letBbe an antichain ofd
for which the maximum is attained. For alla∈B, setja to be the maximal element ofZa under. Then {xjayi :i∈Za, a∈B}is an antichain ofP withξ elements.
Using Dilworth’s theorem [16, p. 413], we coverP withξ chains,C1, . . . ,Cξ. For 1≤k≤ξ, sethk:=
xjyi∈Ckxjyi. Our final claim is that
I˘+(h1, . . . , hξ)=I. Thehl belong toI andI˘⊆I, so it suffices to show thatI ⊆p for everyp∈SpecR such thatI˘+(h1, . . . , hξ)⊆p.
Letp be such, and, by way of contradiction, assume thatxjyi ∈I\p; since I˘⊆p, ji. First, we may also assume that for alli=i, ii, ifxjyi ∈I, thenyi ∈p, and similarly, that for allj=j, jj, ifxjyi∈I, thenxj∈p. Secondly,iandj belong to the same strong component ofdG; letabe such thati, j ∈Za. LetCl be chain ofP containingxjyi. For allbaandj∈Zb,xjyj ∈ ˘I⊆p, soyj⊆p. Sim- ilarly, for allbaandi∈Zb,xiyi∈ ˘I⊆p, soxi⊆p. We can thus conclude that if xjyi∈Cland(i, j )=(i, j), thenxjyi∈p. Thereforexjyi∈p, contradicting the
choice ofxjyi.
OnN2, we define a poset by setting(a, b)≥(c, d)ifa≥candb≥d. Let(P ,≥), be a finite poset on a vertex setW1. We say thatP can be embedded inN2if there exists a mapφ:W−→N2such that alli, j∈W,j ≥iif and only ifφ (j )≥φ (i);
such a mapφwill be called an embedding ofP inN2. We will denote the projection ofN2along the first co-ordinate byπ.
Definition 4.3 Let(P ,)be a finite poset on a finite vertex set W, with an em- beddingφ inN2. Then there is a unique i0∈W such thati0is minimal inP and (π◦φ)(i0)is minimum. Similarly, letj0be the unique maximal element such that (π◦φ)(j0)is minimum. LetP1andP2be the restrictions ofP respectively toW\{i0} andW\{j0}. The column linearization ofP induced byφis the mapγ:W−→ [|W|]
defined recursively as follows:
γ (i)= 1, i=i0
1+γ1(i), i=i0
whereγ1 is a column linearization ofP1 induced byφ. A row linearization of P induced byφis the mapρ:W−→ [|W|]defined recursively as follows:
ρ(j )= 1, j=j0 1+ρ1(j ), j=j0
whereρ1is a row linearization ofP2induced byφ. We will say that(γ , ρ)is the pair of linearizations induced byφ.
Proposition 4.4 LetP,φ,γ and ρ be as in Definition4.3. Fori, j ∈P, ifj i, j=i, thenγ (j ) > γ (i)andρ(j ) < ρ(i). Ifiandj are incomparable, thenγ (j ) >
γ (i)if and only ifρ(j ) > ρ(i).
Proof Ifj i, thenφ (j )≥φ (i). In the recursive definition ofγ,i would appear as the unique minimal vertex with the smallest value of(π◦φ)beforej would, so
γ (i) < γ (j ). On the other hand, while computingρrecursively,j would appear as the unique maximal vertex with the smallest value of(π◦φ) before i would, so ρ(j ) < ρ(i). On the other hand, ifiandj are incomparable, then we may assume without loss of generality that(π◦φ)(i) < (π◦φ)(j ). Hence, while computingγ andρrecursively,iwill be chosen beforej, givingγ (i) < γ (j )andρ(i) < ρ(j ).
Discussion 4.5 LetP be a poset on a finite setW, with an embeddingφinN2. Let (γ , ρ)be the pair of linearizations ofP induced byφ. LetE= {(γ (i), ρ(j )):j i∈W} ⊆R2. We think of Eas a subset of [|W|] × [|W|] in the first quadrant of the Cartesian plane. Leti, j be such that(γ (i), ρ(j ))∈E is not the lowest vertex in its column, i.e., there existslsuch that(γ (i), ρ(l))lies below(γ (i), ρ(j )). Then ji,liand, from Proposition4.4,l=i. Therefore, again from Proposition4.4, γ (l) > γ (i)and(γ (i), ρ(l)) is not the right-most vertex in its row. Letk be such that (γ (k), ρ(l)) lies immediately to the right of (γ (i), ρ(l)) in its row. Draw an edge between(γ (i), ρ(j )) and(γ (k), ρ(l)). Repeating this for all j i such that (γ (i), ρ(j ))is not the lowest vertex in its column, we obtain a graphonE. Rows and columns ofwill be indexed starting from the bottom left corner.
Lemma 4.6 With notation as in Discussion4.5,has exactly|W|connected com- ponents.
Proof Suppose thatCis a connected component ofand that(γ (i), ρ(j ))is the top left vertex ofC. We claim that it is the left-most vertex in its row. For, if not, then there existsksuch that(γ (k), ρ(j ))lies immediately to the left of(γ (i), ρ(j )). From Proposition4.4,k=j. We note, again from Proposition4.4, that(γ (k), ρ(j ))is not the top-most vertex in its column, contradicting the hypothesis that(γ (i), ρ(j )) is the top left vertex ofC. Now, there are exactly|W|rows in. Lemma 4.7 LetGbe a Cohen-Macaulay bipartite graph such thatφis an embed- ding ofdG inN2. Let (γ , ρ) be the pair of linearizations induced by φ. Then the vertices in the first column of belong to a contiguous set of rows, starting with row 1.
Proof We may assume that the labelling of dG is such that γ−1(1)= 1 and γ−1(2)=2. We need to show thatρ(i) > ρ(1)ifi1. Proposition4.4gives that 1 is minimal indG. Leti1. Theniand 1 are incomparable. Sinceγ (1)=1≤γ (i), we see, again from Proposition4.4, thatρ(i) > ρ(1).
Remark 4.8 LetP be a poset on a finite vertex setW with an embeddingφinN2. Let(γ , ρ)be the pair of linearizations ofP induced byφ. LetW=W\ {γ−1(1)} and letPbe the restriction ofP toW. Thenφ|W is an embedding ofPinN2. For i∈W, setγ(i)=γ (i)−1, and
ρ(i)= ρ(i), iγ−1(1) ρ(i)−1, otherwise.
Then(γ, ρ)is the pair of linearizations induced byφ|W. Letbe the graph con- structed from P as described in Discussion 4.5using γ and ρ. Then is ob- tained by deleting the vertices in the first column of. We see this as follows. For all i, j∈W,ρ(i) < ρ(j )if and only ifρ(i) < ρ(j ); similarly,γ (i) < γ (j )if and only ifγ(i) < γ(j ). Further, there is only one vertex in rowρ(γ−1(1))in, and this is in the first column.
Remark 4.9 LetP be a poset on a finite vertex setW with an embeddingφinN2. Let(γ , ρ)be the pair of linearizations induced byφ. LetW=W\γ−1(1)and let P be the restriction ofP toW. Thenφ|W is an embedding ofP inN2. Letγ˜ be the order-preserving map from Imγ|W to[|W|]. Letγ:= ˜γ ◦γ|W. Forj ∈W, setρ(j )=ρ(j )−ρ(1). Then(γ, ρ)is the pair of linearizations ofPinduced by φ|W. Letbe the graph constructed fromPas described in Discussion4.5using
˜
γ◦γ|W andρ˜◦ρ|W. We claim that is the graph obtained fromby deleting the vertices that lie in rows ρ(j )for some j γ−1(1). For, first observe that for alli, j∈W,ρ(i) < ρ(j )if and only ifρ(i) < ρ(j ); similarly,γ (i) < γ (j )if and only ifγ(i) < γ(j ). Moreover, for alljγ−1(1), the vertices in the columnγ (j ) belong to rows between 1 andρ(j )(possibly, not all of them). Therefore, after the vertices in the rows between 1 andρ(1)have been deleted, the remaining vertices belong to columnsγ (j ) for j 1. Hence (γ(i), ρ(j )) and(γ(k), ρ(l))belong to the same connected component of if and only if(γ (i), ρ(j ))and(γ (k), ρ(l)) belong to the same connected component of.
Example 4.10 We wish to illustrate these constructions with an example of a Cohen- Macaulay bipartite graph. LetGbe the Cohen-Macaulay bipartite graph on the vertex set{x1, y1, . . . , x7, y7}such that the posetdGhas the cover relations (i.e., chains that cannot be further refined) 31, 32, 41, 42, 52, 63, 64, 74 and 75. Table1gives the embeddingφ, the functionsγandρand the graph. We take the sum of the monomials corresponding to the vertices in a connected component of:
g1=x1y6, g2=x2y6+x1y3, g3=x3y6+x2y3+x1y7, g4=x4y6+x3y3+x2y7+x1y4, g5=x6y6+x4y7+x2y4+x1y1, g6=x5y7+x4y4+x2y5, g7=x7y7+x5y5+x2y2.
LetJ=(g1, . . . , g7). In the proof of Proposition4.11we will see thatI=√ J. Before we prove the second assertion of Theorem1.3, we observe that the directed graph associated toG˘ (which we denoted byd˘ in Discussion4.1) has an embedding inN2if and only if the acyclic reductiondofdGhas an embedding inN2. The proof of this is easy, and is omitted.
Proposition 4.11 LetG be an unmixed bipartite graph. If a maximal transitively closed and acyclic subgraph ofdGcan be embedded inN2, then araI=pdR/I.
