Access the full text.
Sign up today, get DeepDyve free for 14 days.
References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.
We present two new problems on lower bounds for Betti numbers of the minimal free resolution for monomial ideals generated in a xed degree. The rst concerns any such ideal and bounds the total Betti numbers, while the second concerns ideals that are quadratic and bihomogeneous with respect to two variable sets, but gives a more nely graded lower bound. These problems are solved for certain classes of ideals that generalize (in two dierent directions) the edge ideals of threshold graphs and Ferrers graphs. In the process, we produce particularly simple cellular linear resolutions for strongly stable and squarefree strongly stable ideals generated in a xed degree, and combinatorial interpretations for the Betti numbers of other classes of ideals, all of which are independent of the coecient eld. Partially supported by NSA grant H98230-07-1-0065 and by the Institute for Mathematics & its Applications at the University of Minnesota. Partially supported by NSF grant DMS-0601010. the electronic journal of combinatorics 16(2) (2009), #R3 1 1 Introduction and the main problems The paper concerns minimal free resolutions of an ideal I in a polynomial ring S = k[x ; : : : ; x ] which is generated by monomials of a xed degree. Many of its results 1 n were motivated by two new problems, Question 1.1 and Conjecture 1.2 below, which we formulate here. Given a squarefree monomial ideal I generated in degree d, it has a uniquely de ned minimal generating set of monomials, indexed by a collection K of d-subsets of P := f1; 2; : : :g in the sense that I = (x x : fi ; : : : ; i g 2 K): i i 1 d 1 d De ne the colexicgraphic order on the d-subsets by saying that S = fi < < i g 1 d 0 0 0 S = fi < < i g 1 d 0 0 0 have S < S if i < i for some k 2 f1; : : : ; dg and i = i for j = k + 1; : : : ; d. For colex k j k j example, the colex order on begins f1; 2; 3g < f1; 2; 4g < f1; 3; 4g < f2; 3; 4g < colex colex colex colex f1; 2; 5g < f1; 3; 5g < f2; 3; 5g colex colex Call K a colexsegment if it forms an initial segment of the colexicographic ordering, and call J a colexsegment-generated ideal if J = (x x : fi ; : : : ; i g 2 K) i i 1 d for a colexsegment K. To state our rst problem, recall that (I) = dim Tor (I; k) is the i k th th i Betti number for I, that is, the rank over S of the i term in any minimal resolution of I by free S-modules. Furthermore, say that a monomial ideal I generated in degree d obeys the colex lower bound if, for all integers i, (I) (J ), where J is the unique i i colexsegment-generated (squarefree) monomial ideal having the same number of minimal generators as I, all of degree d. We ask: Question 1.1 Let I be any monomial ideal generated in degree d. When does it obey the colex lower bound? We should remark that the standard technique of polarization [25, x3.2 Method 1] immedi- ately reduces this question to the case where I is itself generated by squarefree monomials, generated in a xed degree d. The second problem concerns the situation where I is quadratic, and furthermore, generated by quadratic monomials x y which are bihomogeneous with respect to two sets i j of variables within the polynomial algebra S = k[x ; : : : ; x ; y ; : : : ; y ]. In this case, I is 1 m 1 n the edge ideal I = (x y : fx ; y g an edge of G) i j i j for some bipartite graph G on the partitioned vertex set XtY with X = fx ; : : : ; x g; Y = 1 m fy ; : : : ; y g. Rather than considering only the ungraded Betti numbers , here we take 1 n i the electronic journal of combinatorics 16(2) (2009), #R3 2 m advantage of the Z -grading available on the x variables, but ignoring the grading on the y variables. That is, we set deg(x ) := e for i = 1; : : : ; m; but i i deg(y ) := 0 for j = 1; : : : ; n: 0 m For each subset X X, de ne the Betti number 0 (I) to be the Z -graded Betti i;X ; m+n number for this grading, or the following sum of the usual Z -graded Betti numbers 0 0 (I) : i;X tY 0 0 0 (I) := (I): i;X ; i;X tY Y Y If the vertex x 2 X has degree (valence) deg (x ) in G, then the relevant ideal J with i i which we will compare I is J := (x y : i = 1; : : : ; m; and j = 1; 2; : : : ; deg (x )): (1.1) i j i Note that, unlike the ideals J which appeared in Question 1.1, the ideals J in (1.1) are not colex. The bipartite graphs corresponding to these ideals J are known as Ferrers graphs; see [10] and Example 2.5 below. Conjecture 1.2 Consider the edge ideal I = (x y : fx ; y g 2 G) S = k[x ; : : : ; x ; y ; : : : ; y ] i j i j 1 m 1 n for some bipartite graph G on X t Y as above, and let J be the Ferrers graph edge ideal associated to I as in (1.1). Then 0 (I) 0 (J ) for all i and all subsets X X. i;X ; i;X ; After this paper appeared on the math arXiv (math.AC/0712.2537), but while it was under journal review, Conjecture 1.2 was proven by M. Go [16, Theorem 1.1]. We remark that the lower bounds on the Betti numbers in both of the problems can be made quite explicit. In Question 1.1, if the monomial ideal I has exactly g minimal generating monomials, express g = + uniquely for some integers ; with d 1 and 0 < . Then the lower bound can be rewritten (using Corollary 3.14 below) d1 as j 1 + 1 d (I) (J ) = + i i i; d 1; j d i i j=d n n! where = denotes a multinomial coecient. In Conjecture 1.2, if for any subset i;j;k i!j!k! 0 0 0 of vertices X X, one denotes by mindeg(X ) the minimum degree of a vertex x 2 X in the bipartite graph G, then the lower bound can be rewritten (using Proposition 2.17 below) as mindeg(X ) if jX j < i + 2 ijX j+2 0 (I) 0 (J ) = i;X ; i;X ; 0 otherwise: the electronic journal of combinatorics 16(2) (2009), #R3 3 This is certainly not the rst paper about lower bounds on the Betti number. For example, there are lower bounds shown by Evans and Grith, Charalambous, Santoni, Brun, and R omer establishing and strengthening the Buchsbaum-Eisenbud conjecture (of- ten referred to as Horrocks's problem) for monomial ideals (see [8], [28] and the references therein). The Buchsbaum-Eisenbud conjecture states that the i-th total Betti number of a homogeneous ideal I in a polynomial ring is at least , where c is the codimension of I. Observe that, for the ideals under consideration in this paper, we ask for much stronger lower bounds. Another thread in the literature investigates the Betti numbers of ideals with xed Hilbert function. Among these ideals, the lex-segment ideal has the maximal Betti num- bers according to Bigatti, Hulett, and Pardue ([4] [19], [27]). However, in general there is no common lower bound for these ideals (see, e.g., [13] and the references therein). In comparison, the novelty of our approach is that instead of the Hilbert function we x the number of minimal generators of the ideals under consideration. The remainder of the paper is structured as follows. Part I introduces a new family of graphs and their edge ideals, parametrized by well- known combinatorial objects called shifted skew shapes; each such shape will give rise to both bipartite and nonbipartite graphs, generalizing two previously studied classes of graphs that have been recently examined from the point of view of resolutions of their edge ideals { the Ferrers graphs [10] and the threshold graphs [11]. It turns out that these new families of edge ideals are extremely well-behaved from the viewpoint of their minimal free resolutions { the rst main result (Corollary 2.15) gives a combinatorial interpretation for their Z -graded Betti numbers which is independent of the coecient eld k. This interpretation is derived by showing that the relevant simplicial complexes for these graph ideals, whose homology compute these Betti numbers by a well-known formula of Hochster (see Proposition 2.7), always have the homotopy type of a wedge of equidimensional spheres (Theorem 2.14). This is in marked contrast to the situation for arbitrary edge ideals of graphs, where the relevant simplicial complexes are well-known to have the homeomorphism type of any simplicial complex (Proposition 6.1), and for arbi- trary bipartite graph ideals, where we note (Proposition 6.2) that the simplicial complexes can have the homotopy type of an arbitrary suspension. We also show (Theorem 2.20) that the resolutions for the nonbipartite edge ideals within this class can be obtained by specialization from the resolutions of the bipartite ones, as was shown in [11] for Ferrers and threshold graphs. We further interpret the Castelnuovo-Mumford regularity (Theorem 2.23) of these ideals, and indicate how to compute their Krull dimension and projective dimension. Part II investigates a dierent generalization of the Ferrers graph's and threshold graph's edge ideals, this time to nonquadratic squarefree monomial ideals including the special case of the squarefree strongly stable ideals studied by Aramova, Herzog and Hibi [1] which are generated in a xed degree. We provide a simple cellular resolution for these ideals and some related ideals (Theorem 3.13), related by polarization/specialization again as in [11]. We also describe an analogously simple cellular resolution for strongly stable ideals generated in a xed degree, recovering a recent result of Sinefakopoulos [30]. the electronic journal of combinatorics 16(2) (2009), #R3 4 Part III uses the previous parts to address Question 1.1 and Conjecture 1.2, which are veri ed for all of the ideals whose Betti numbers were computed in Parts I and II. How- ever, we exhibit monomial ideals that do not obey the colex lower bound (Remark 4.6). Moreover, a more precise version of Conjecture 1.2 is formulated (Conjecture 4.9), incor- porating both an upper and a lower bound on the Betti numbers for bipartite graph edge ideals, as well as a characterization of the case of equality in both bounds. Furthermore, the upper bound, as well as the characterizations for the cases of equality in both the upper and the lower bound are proven, leaving only the lower bound itself unproven. The Epilogue contains some questions suggested by the above results. In the Appendix some needed technical tools from combinatorial topology and commutative algebra are provided. Contents 1 Introduction and the main problems 2 2 PART I. Shifted skew diagrams and graph ideals 6 2.1 Shifted diagrams and skew diagrams . . . . . . . . . . . . . . . . . . . . . 6 2.2 Graphs and graph ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Betti numbers and simplicial complexes . . . . . . . . . . . . . . . . . . . . 10 2.4 Rectangular decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 Homotopy type and Betti numbers . . . . . . . . . . . . . . . . . . . . . . 15 2.6 Case study: Ferrers diagrams and rook theory . . . . . . . . . . . . . . . . 18 2.7 Specialization from bipartite to nonbipartite graphs . . . . . . . . . . . . . 20 2.8 Castelnuovo-Mumford regularity . . . . . . . . . . . . . . . . . . . . . . . . 25 2.9 Krull dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.10 Projective dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3 PART II: Skew hypergraph ideals 28 3.1 Non-quadratic monomial ideals and hypergraphs . . . . . . . . . . . . . . . 28 3.2 Cellular resolutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 The complex-of-boxes resolution . . . . . . . . . . . . . . . . . . . . . . . . 33 4 PART III: Instances of Question 1.1 and Conjecture 1.2 40 4.1 Armative answers for Question 1.1 . . . . . . . . . . . . . . . . . . . . . 40 4.2 Evidence for Conjecture 1.2 and its re nement . . . . . . . . . . . . . . . . 42 4.3 Proof of the upper bound and the case of equality . . . . . . . . . . . . . . 46 4.4 Two general reductions in the lower bound . . . . . . . . . . . . . . . . . . 47 4.5 The case of equality in the lower bound . . . . . . . . . . . . . . . . . . . . 49 bip 4.6 Verifying the bipartite conjecture for D . . . . . . . . . . . . . . . . . . 50 X;Y 5 EPILOGUE: Further questions 51 the electronic journal of combinatorics 16(2) (2009), #R3 5 6 Appendix 52 6.1 On the topological types of (I(G)) . . . . . . . . . . . . . . . . . . . . . 52 6.2 A wedge lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.3 A collapsing lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.4 A polarization lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2 PART I. Shifted skew diagrams and graph ideals 2.1 Shifted diagrams and skew diagrams We begin with some terminology for diagrams in the shifted plane that are perhaps not so standard in commutative algebra, but fairly standard in the combinatorial theory of projective representations of the symmetric group and Schur's P and Q-functions [23, Exercise I.9]. De nition 2.1 The shifted plane is the set of lattice points f(i; j) 2 Z Z : 1 i < jg drawn in the plane so that the rst coordinate increases from the top row to the bottom, and the second coordinate increases from left to right: (1; 2) (1; 3) (1; 4) (2; 3) (2; 4) (3; 4) . . . . . . . . . . . . . . . Given a number partition = ( ; ; ; ) into distinct parts, that is, > > 1 2 ` 1 2 > > 0, the shifted Ferrers diagram for is the set of cells/boxes in the shifted plane having cells left-justi ed in row i for each i. For example, = (12; 11; 7; 6; 4; 2; 1) has this diagram: Given another number partition with distinct parts having for all i, one i i can form the shifted skew diagram D = = by removing the diagram for from the diagram for . For example, if = (11; 9; 6; 3) and = (12; 11; 7; 6; 4; 2; 1) as before, then the electronic journal of combinatorics 16(2) (2009), #R3 6 D = = has the following shifted skew diagram, with row and column indices labelled to emphasize its location within the shifted plane: 1 2 3 4 5 6 7 8 9 10 11 12 13 In a shifted skew diagram D, cells in locations of the form (i; i + 1) will be called staircase cells. For example, the diagram above has three staircase cells, namely (5; 6); (6; 7); (7; 8). Given a shifted skew diagram D, and any pair X; Y of linearly ordered subsets of positive integers X = fx < x < < x g 1 2 m Y = fy < y < < y g; 1 2 n bip one can form a diagram D with rows indexed by X and columns indexed by Y , by X;Y restricting the diagram D to these rows and columns. For example if D = = is the shifted skew diagram shown above, and if X = fx ; x ; x ; x g = f2; 4; 5; 7g 1 2 3 4 Y = fy ; y ; y ; y ; y ; y ; y ; y g = f4; 6; 7; 8; 9; 10; 11; 12g 1 2 3 4 5 6 7 8 bip then D is this diagram: X;Y y y y y y y y y 1 2 3 4 5 6 7 8 4 6 7 8 9 10 11 12 x = 2 (2.1) x = 4 x = 5 x = 7 bip Such diagrams D should no longer be considered as drawn in the shifted plane, but X;Y rather inside the m n rectangle with row and column indices given by X and Y . On the other hand, given a shifted skew diagram D, and a linearly ordered subset X, nonbip bip one can also form the diagram D (= D ), which one should think of as drawn in X X;X a shifted plane whose rows and columns are indexed by X. For example, if D = = as the electronic journal of combinatorics 16(2) (2009), #R3 7 nonbip above and X = fx ; x ; x ; x ; x ; x g = f2; 4; 5; 7; 8; 10g, then D is this diagram: 1 2 3 4 5 6 x x x x x x 1 2 3 4 5 6 2 4 5 7 8 10 x = 2 x = 4 (2.2) x = 5 x = 7 x = 8 x = 10 nonbip For such diagrams D , call the cells in locations of the form (x ; x ) its staircase i i+1 nonbip cells. For example, in D shown above there are two staircase cells, in positions (x ; x ); (x ; x ). 3 4 4 5 2.2 Graphs and graph ideals De nition 2.2 A (simple) graph G on vertex set V is a collection E(G) := ffu; vg : u; v 2 V and u 6= vg called its edges. Having xed a eld k to use as coecients, any graph G gives rise to a square-free quadratic monomial ideal called its edge ideal I(G) inside the polynomial ring k[V ] := k[v] , generated by the monomials uv as one runs through all edges fu; vg v2V in E(G). jV j Note that since I(G) is a monomial ideal, it is homogeneous with respect to the Z - jV j grading on k[V ] in which the degree of the variable v is the standard basis vector e 2 R . This is the nest grading which we will consider on I(G). However, there are times when we will consider the coarser Z-grading in which each variable v has degree 1. There is a situation in which some dierent gradings also appear. De nition 2.3 Say that a simple graph G is bipartite with respect to the partition V = V t V of its vertex set V if every edge in E(G) has the form fv ; v g with v 2 V for 1 2 1 2 i i i = 1; 2. Equivalently, G is bipartite with respect to V = V t V if and only if I(G) is homo- 1 2 geneous with respect to the Z -grading in k[V ] in which the variables labelled by vertices in V all have degree (1; 0), while the variables labelled by vertices in V all have degree 1 2 (0; 1). bip nonbip Given any shifted skew diagram D, the two kinds of subdiagrams D ; D give X;Y X rise to two kinds of graphs, and hence to two kinds of edge ideals: We hope that using the names of vertices as polynomial variables, a very convenient abuse of notation, causes no confusion. the electronic journal of combinatorics 16(2) (2009), #R3 8 For a pair of linearly ordered sets X = fx ; : : : ; x g; Y = fy ; : : : ; y g, one has the 1 m 1 n bip bipartite G (D) graph on vertex set X t Y , with an edge fx ; y g for every cell i j X;Y bip bip (x ; y ) in the diagram D . Its edge ideal I(G (D)) is inside the polynomial i j X;Y X;Y algebra k[x ; : : : ; x ; y ; : : : ; y ]. 1 m 1 n For a single linearly ordered set X = fx ; : : : ; x g, one has the nonbipartite graph 1 m nonbip G (D) on vertex set X, with an edge fx ; x g for every cell (x ; x ) in the diagram i j i j nonbip nonbip D . Its edge ideal I(G (D)) is inside the polynomial algebra k[x ; : : : ; x ]. 1 m X X We will have occasion, as in Conjecture 1.2, to consider yet a fourth grading on bip k[x ; : : : ; x ; y ; : : : ; y ] and the ideals I(G (D)). This is the Z -grading mentioned in 1 m 1 n X;Y the Introduction, in which the degree of the variable x is the standard basis vector e in i i m m Z but the degree of the variable y is the zero vector in Z . Example 2.4 bip nonbip If D and D are the diagrams shown in (2.1), (2.2), respectively, then X;Y X bip I(G (D)) = (x y ; x y ; x y ; x y ; x y ; x y ; x y ; x y ; x y ) 1 8 2 4 2 5 2 6 3 2 3 3 3 4 3 5 4 4 X;Y k[x ; x ; x ; x ; y ; y ; y ; y ; y ; y ; y ; y ] 1 2 3 4 1 2 3 4 5 6 7 8 nonbip I(G (D)) = (x x ; x x ; x x ; x x ; x x ) 2 5 2 6 3 4 3 5 4 5 k[x ; x ; x ; x ; x ; x ]: 1 2 3 4 5 6 We review now some well-studied classes of graphs that were our motivating special cases. Example 2.5 (Ferrers bipartite graphs) bip Say that D is Ferrers if whenever i < i , the columns occupied by the cells in the row X;Y bip x form a subset of those occupied by the cells in row x . The graph G (D) is then i i X;Y completely determined up to isomorphism by the partition = ( ) where 1 m i is the number of cells in the row x . Call such a Ferrers graph G . An explicit cellular minimal free resolution of I(G ) for the Ferrers graphs G was given in [10], thereby determining its Betti numbers { see also Example 2.6 below. Example 2.6 (threshold graphs) Let D be the shifted Ferrers diagram for a strict partition = ( > > ), so that 1 m nonbip the columns are indexed by [n] = f1; 2; : : : ; ng with n = +1. Then the graph G (D) [n] is called a threshold graph. Such graphs have numerous equivalent characterizations { see [24]. nonbip An explicit cellular minimal free resolution of I(G (D)) in this case was derived [n] in [11] by specialization from the resolution of an associated Ferrers graph from [10]. It would be more accurate to say \not necessarily bipartite" here than \nonbipartite", but we nd this terminology more convenient. 3 m+n The other three gradings with which one might confuse it are: (i) the nest Z -grading, (ii) the Z -grading for which these ideals are bihomogeneous, and (iii) the Z-grading in which all variables x and y all have degree 1. the electronic journal of combinatorics 16(2) (2009), #R3 9 2.3 Betti numbers and simplicial complexes Edge ideals I(G) of graphs are exactly the squarefree quadratic monomial ideals. More generally, any squarefree monomial ideal I in a polynomial algebra k[V ] has some special properties with regard to its minimal free resolution(s) as a k[V ]-module. Since I is jV j a monomial ideal, the resolution can be chosen to be Z -homogeneous. Because it is generated by squarefree monomials, the free summands in each resolvent will have basis elements occurring in degrees which are also squarefree, corresponding to subsets V V . The nely graded Betti number 0(I) is de ned to be the number of such basis elements i;V th in the i syzygy module occurring in the resolution, or equivalently, k[V ] 0(I) = dim Tor (I; k) 0 i;V k V 0 jV j where here M denotes the V -graded component of a Z -graded vector space. The standard graded and ungraded Betti numbers are the coarser data de ned by k[V ] (I) = dim Tor (I; k) = 0(I) i;j k j 0 0 i;V V V :jV j=j P P k[V ] (I) = dim Tor (I; k) = (I) = (I): i k i;V i;j i V V j A famous formula of Hochster relates these resolution Betti numbers to simplicial homology. An abstract simplicial complex on vertex set V is a collection of subsets F of V (called faces of ) which is closed under inclusion: if G F and F 2 then G 2 . Maximal faces of under inclusion are called facets of . There is a straightforward bijection (the Stanley-Reisner correspondence) between simplicial complexes on vertex set V and squarefree monomial ideals I inside k[V ]: let I be generated by all squarefree monomials x x for which fv ; : : : ; v g 62 . v v 1 s 1 s Hochster's formula for 0(I ) is expressed in terms of the (reduced) simplicial homology i;V of the vertex-induced subcomplex 0 := fF 2 : F V g: Proposition 2.7 (Hochster's formula [25, Corollary 5.12]) For a squarefree monomial ideal I k[V ] and any V V , one has a k-vector space isomorphism k[V ] Tor (I; k) 0 H 0 ( 0 ) V jV ji2 V and hence 0 0 0 (I ) = dim H ( ): i;V k jV ji2 V If I = I(G) for a graph G on vertex set V , then we will write = (G); the name for such simplicial complexes is that they are ag or clique complexes. Warning: this does not mean that is the 1-dimensional simplicial complex generated by the edges of G. In fact, there is a somewhat more direct relationship between the edges of G and the Alexander dual of (G). the electronic journal of combinatorics 16(2) (2009), #R3 10 _ De nition 2.8 Given a simplicial complex on vertex set V , its Alexander dual is the simplical complex on vertex set V de ned by := fV n G : G 62 g: _ _ _ Note that the operation 7! is involutive: ( ) = . It is an easy exercise in the de nitions to check that, for a graph G on vertex set V , the facets of the Alexander dual (G) are exactly the complementary sets V n fu; vg to the edges fu; vg in E(G). Lastly, note that a shifted skew diagram D will give rise to two simplicial complexes bip nonbip (G (D)); (G (D)) X;Y X bip nonbip which control the Betti numbers of the edge ideals I(G (D)); I(G (D)): More pre- X;Y X cisely, each vertex-induced subcomplex which appears in Proposition 2.7 for calculating the graded Betti numbers is another simplicial complex of the same form: bip bip 0 0 (G (D)) = (G (D)) X tY 0 0 X;Y X ;Y nonbip nonbip (G (D)) = (G (D)) X X bip Thus our next goal will be to study the homotopy type of the complexes (G (D)) X;Y nonbip and (G (D)). 2.4 Rectangular decomposition The idea in this section is to produce what we call the rectangular decomposition for any bip nonbip diagram D (or D ). As an informal illustration, here is the rectangular decom- X;Y X bip position of the following diagram D into pieces of various types, explained below the X;Y diagram: y y y y y y y y y y y y y y y y 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 x r r r 3 1 1 1 x e e r r r 4 1 1 1 x r r r e e 5 2 2 2 x e r r r e 6 2 2 2 x e e r r r e 7 2 2 2 (2.3) x r 8 3 x e r 9 3 x e e r 10 3 x p p p p p x e p p p p p x p p p x e e the electronic journal of combinatorics 16(2) (2009), #R3 11 There are some full rectangles, of which there are three in diagram (2.3), whose cells have been labelled r or r or r , with the northeasternmost top cell of each rectangle indicated 1 2 3 in boldface, some empty rectangles, of which there are two in diagram 2.3, one indicated by dots occupying rows fx ; x g and column fy g, the other occupying columns fy ; y g 1 2 16 8 9 but having zero width (lying \between" rows x and x ), 7 8 at most one pedestal, whose cells are labelled \p" in diagram 2.3, with the north- easternmost top cell of the pedestal indicated in boldface, and some excess cells, labelled by \e". Informally, the idea behind the rectangular decomposition is that in analyzing the homo- topy type of the associated simplicial complexes in Section 2.5, one nds that removing excess cells does not change the homotopy type, once the excess cells are removed, the complex decomposes into a simplicial join of the complexes corresponding to each full/empty rectangle and the pedestal (if present), complexes associated to full rectangles are zero-dimensional spheres, complexes associated to empty rectangles are simplices, hence contractible, and bip the complex associated to a pedestal is contractible in the case of D , or homotopy X;Y nonbip equivalent to an s-fold wedge of zero-spheres in the case of D where s is the number of (non-excess) staircase cells. bip nonbip Consequently, (G (D)); (G (D)) will either be contractible or have the homo- X;Y X topy type of a wedge of equidimensional spheres. In addition, the homotopy type can be easily predicted from the above decomposition. Here is the formal algorithm that produces the rectangular decomposition. bip De nition 2.9 De ne the rectangular decomposition of D recursively for any shifted X;Y skew diagram D and linearly ordered sets X = fx < < x g, Y = fy < < y g 1 m 1 n with X t Y 6= ?, allowing either X or Y to be empty. The algorithm will in general go through several iterations, terminating either when X t Y becomes empty, or when one encounters a pedestal in Subcase 2b below. bip Say that D has a top cell if it contains a cell in position (x ; y ); in particular this 1 n X;Y requires both X; Y to be nonempty. Initialize the set of excess cells as the empty set; cells will be identi ed as excess cells during iterations of the algorithm. In each iteration, there are several cases. the electronic journal of combinatorics 16(2) (2009), #R3 12 bip Case 1. D has no top cell. X;Y Then there exist some initial segment X = fx ; x ; : : : ; x g X; and 1 2 m (2.4) nal segment Y = fy 0; y 0 ; : : : ; y g Y n n +1 n bip bip 0 0 such that both D and D contain no cells. In this case, pick the segments X ; Y 0 0 X;Y X ;Y bip maximal with this property, and call D the rst empty rectangle in the rectangular 0 0 X ;Y 0 0 0 0 decomposition. Note that X [ Y 6= ?, but it is possible that either X or Y might be empty, in which case one has an empty rectangle with zero length or zero width (!). bip bip 0 0 Now remove the rows and columns X ; Y , that is, replace D by D , and 0 0 X;Y XnX ;Y nY continue the rectangular decomposition. bip Case 2. D has a top cell, namely (x ; y ). 1 n X;Y 0 0 0 0 De ne indices m ; n uniquely by saying m (resp. n ) is maximal (resp. minimal) for bip which (x 0 ; y ) (resp. (x ; y 0)) is a cell of D . m n 1 n X;Y bip If D has a cell in position (x 0 ; y 0), then this will be called its neck cell. m n X;Y 0 0 Again de ne initial, nal segments X ; Y by X = fx ; x ; : : : ; x 0g X; and 1 2 m 0 0 Y = fy ; y ; : : : ; y g Y: n n +1 n bip Subcase 2a. D has both a top cell and a neck cell (possibly the same cell!) X;Y bip In this case, D is a full rectangle in the sense that every possible position (x ; y ) 0 0 i j X ;Y 0 0 0 0 with i 2 X ; j 2 Y actually contains a cell of D. In fact, our choice of m ; n makes bip 0 0 X ; Y maximal with respect to this property. Call D the rst full rectangle in the 0 0 X ;Y rectangular decomposition. bip Then add to the set of excess cells all cells of D (i.e., those lying below the full 0 0 XnX ;Y bip rectangle in the same columns) and all cells of D (i.e., those lying left of the full 0 0 X ;Y nY rectangle in the same rows). bip 0 0 Lastly, remove the rows and columns X ; Y from X; Y , that is, replace D by X;Y bip D , and continue the rectangular decomposition. 0 0 XnX ;Y nY bip Subcase 2b. D has a top cell but no neck. X;Y bip Now call D the pedestal in the rectangular decomposition. Note that not every 0 0 X ;Y diagram will have such a pedestal. bip bip As in Subase 2a, add all cells of D and D to the set of excess cells. But 0 0 0 0 XnX ;Y X ;Y nY now the algorithm also terminates. bip Example 2.10 The diagram D in (2.3) whose nonempty cells are labelled e; r ; r ; r ; p 1 2 3 X;Y passes through six iterations of the algorithm: bip 1st Case 1{ add the empty rectangle D to the decomposition. fx ;x g;fy g 1 2 16 the electronic journal of combinatorics 16(2) (2009), #R3 13 bip 2nd Subcase 2a{ add the full rectangle D (with cells labelled r , top fx ;x g;fy ;y ;y g 3 4 13 14 15 cell (x ; y ) in boldface, neck cell (x ; y )) to the decomposition, and identify two 3 15 4 13 excess cells to its left as well as four excess cells below it. bip 3rd Subcase 2a{ add the full rectangle D (with cells labelled with r , fx ;x ;x g;fy ;y ;y g 5 6 7 10 11 12 top cell (x ; y ) in boldface, neck cell (x ; y )) to the decomposition, and identify 5 12 7 10 three excess cells to its left. bip 4th Case 1{ add the empty rectangle D to the decomposition. Note that this ?;fy ;y g 8 9 empty rectangle has zero width, i.e. it occupies the empty set X = ? of rows (\between" rows and x and x ). 7 8 bip 5th Subcase 2a{ add the full rectangle D (with cells labelled with r , top fx ;x ;x g;fy g 8 9 10 7 cell (x ; y ) in boldface, neck cell (x ; y )) to the decomposition, and identify three 8 7 10 7 excess cells to its left. bip 6th Subcase 2b{ add the pedestal D (with cells labelled with p, fx ;x ;x g;fy ;y ;y ;y ;y g 11 12 13 2 3 4 5 6 top cell (x ; y ; ) in boldface, no neck cell) to the decomposition, and identify one 11 6 excess cell to its left, two excess cells below it. nonbip The algorithm in De nition 2.9 also produces the rectangular decomposition of D , bip viewing it as D with Y = X. There is however, one minor modi cation: if a pedestal X;Y nonbip occurs in the rectangular decomposition (Subcase 2b) for D , one can view the pedestal itself as a diagram in the shifted plane, and hence certain of its cells are dis- tinguished as staircase cells. The number of these staircase cells becomes important in nonbip the next section when one analyzes the homotopy type of (G (D)). bip Before closing this section, we note a simple criterion for when D has a pedestal, X;Y bip bip used later as an aid to show that certain diagrams D have (G (D)) contractible. X;Y X;Y Proposition 2.11 For any shifted skew diagram D and linearly ordered subsets X; Y , bip 0 0 0 the diagram D has a pedestal if and only if it contains two cells c = (i; j); c = (i ; j ) X;Y 0 0 0 with i < i and j < j but does not contain the cell (i ; j) in the southwest corner of the rectangle that they de ne. bip bip 0 0 Proof. Assume D has pedestal D , with top cell (x ; y ) and m := max X and 0 0 1 n X;Y X ;Y 0 0 0 n := min Y . Then c = (x ; y 0); c = (x 0 ; y ) satisfy the conditions of the proposition, 1 n m n because (i ; j) = (x 0 ; y 0) is the location of the missing neck cell that would have made m n the pedestal into a full rectangle. bip On the other hand, it is easily seen that when D has no pedestal it looks like a X;Y usual skew Ferrers diagram [23, xI.1]. Such diagrams have the property that when they contain two cells c; c forming the northwest and southeast corners of a rectangle, the entire rectangle is in the diagram, including its southwest corner cell. the electronic journal of combinatorics 16(2) (2009), #R3 14 2.5 Homotopy type and Betti numbers bip The goal of this section is Theorem 2.14, describing the homotopy type of (G (D)) X;Y nonbip bip nonbip (resp. (G (D))) in terms of the rectangular decomposition of D (resp. D ). X X;Y X The key point is that one can remove excess cells from the diagrams without changing the homotopy type of the associated simplicial complexes. Lemma 2.12 Let D D be a nested pair of shifted skew diagrams, with D obtained 1 2 1 from D by removing one excess cell of D . Then the nested pair of simplicial complexes 2 2 bip bip := (G (D )) := (G (D )) 1 1 2 2 X;Y X;Y will be homotopy equivalent. bip nonbip The same assertion holds replacing (G (D )) with (G (D )) for i = 1; 2. i i X;Y X Proof. By Lemma 6.8 in the Appendix, it suces to show that the Alexander dual is obtained from by adding a new facet F with the property that the subcomplex F _ 2 \ has a cone vertex. bip nonbip We give the argument for G (D); the only change necessary for G (D) is to X;Y X replace each occurrence of a vertex y with the corresponding vertex x having the same j j subscript j. Let e = (x ; y ) be the unique cell in D n D . Since e is an excess cell, it must have i j 2 1 been identi ed as excess during an iteration of the rectangular decomposition algorithm that fell into Subcase 2a or 2b. Then e is located either below or to the left of a full rectangle or pedestal created during that iteration; call this rectangle or pedestal R in either case. Let (x 0 ; y 0) be the top cell for the rectangle or pedestal R. This implies m n 0 0 i > m and j < n . _ _ Note that the extra facet F of not in corresponding to e has vertices X t 2 1 Y n fx ; y g. If e is located below (resp. to the left of) R, we will show that the vertex i j F _ v := y 0 (resp. v := x 0 ) forms a cone vertex for the intersection subcomplex 2 \ . n m 0 _ 00 _ This means showing for all facets F of there exists a facet F of containing v with 1 1 0 00 0 the further property that F \ F F . If F corresponds to the cell (x 0 ; y 0) of D , then i j 1 00 00 00 0 00 0 this means one must nd a cell (x ; y ) of D with y 6= y (resp. x 6= x ) and the i j 1 j n i m further property that fx ; y g [ fx 0 ; y 0g fx 00 ; y 00g: i j i j i j If y 0 6= y 0 (resp. x 0 6= x 0 ) then this is easy; let (x 00 ; y 00) := (x 0 ; y 0). In other words, j n i m i j i j 0 00 0 if v 62 F then one can simply take F := F . If y 0 = y 0 (resp. x 0 = x 0 ) then let (x 00 ; y 00) := (x 0 ; y ) (resp. let (x 00 ; y 00) := j n i m i j i j i j 0 00 00 (x ; y )). There always exists a a cell located at (x ; y ) in D because this position i j i j 1 is dierent from e and D has a cell located in positions e and (x 0 ; y 0). Hence F = 2 i j X t Y n fx 00 ; y 00g is a facet of . i j bip De nition 2.13 Call a diagram of the form D spherical if in its rectangular decom- X;Y position it has only full rectangles and possibly some excess cells, but no empty rectangles nor pedestal. the electronic journal of combinatorics 16(2) (2009), #R3 15 bip nonbip Given a diagram of the form E = D or E = D , de ne its rectangularity X;Y X rect(E) to be the number of full rectangles and/or pedestals (if present) in its rectangular decomposition. For example, Diagram (2.3) has three full rectangles and one pedestal, thus its rect- angularity is four. It is not spherical. The following result justi es the name spherical in De nition 2.13. Theorem 2.14 Let D be any shifted skew diagram D. bip For any linearly ordered subsets X; Y , the homotopy type of (G (D)) is X;Y bip bip an (rect(D ) 1)-dimensional sphere if D is spherical, and X;Y X;Y contractible otherwise. nonbip For any linearly ordered subset X, the homotopy type of (G (D)) is contractible if there are any empty rectangles in the rectangular decomposition, and nonbip an s-fold wedge of (rect(D ) 1)-dimensional spheres if s denotes the number of non-excess staircase cells otherwise. Proof. Lemma 2.12 reduces the proof to the case where the diagrams have no excess cells. When there are no excess cells, the diagrams are disjoint unions of their various empty or full rectangles and pedestal, where here the disjoint union of diagrams means diagrams that share no row or column indices. In this case, it is easily seen that the relevant bip nonbip graphs G (D) and G (D) are also disjoint unions of the graphs corresponding to X;Y X bip these pieces (full/empty rectangle or pedestal). Consequently the complexes (G (D)) X;Y nonbip and (G (D)) are simplicial joins [26, x62] of the complexes corresponding to these pieces. Thus it remains to analyze the homotopy types of the two kinds of complexes when there is only one piece (empty rectangle, full rectangle, or pedestal) in the rectangular decomposition. For an empty rectangle, either complex is contractible because it is the full simplex 2 on its vertex set V = X t Y or V = X. For a full rectangle, either complex is homotopy equivalent to a zero sphere because it is the disjoint union of two full simplices, one on the vertices indexing its rows, the other on the vertices indexing its columns. bip nonbip For a pedestal, one analyzes D and D separately. X;Y X nonbip In the case of a pedestal in the shifted plane of the form D , say with s (non-excess) staircase cells in positions (x ; x ); (x ; x ); : : : ; (x ; x ); (x ; x ); i i+1 i+1 i+2 i+s2 i+s1 i+s1 i+s nonbip one can check directly that (G (D)) is the disjoint union of the s + 1 full simplices on the vertex sets fx ; x ; : : : ; x g; fx g; fx g; : : : ; fx g; fx ; x ; : : : ; x g; 1 2 i i+1 i+2 i+s1 i+s i+s+1 n the electronic journal of combinatorics 16(2) (2009), #R3 16 where (1; n) is the position of the top cell of the pedestal. Note that such a disjoint union of s + 1 simplices is homotopy equivalent to s + 1 isolated vertices, that is, an s-fold wedge of 0-spheres. bip bip In the case of a pedestal of the form D , one notes that G (D) is not changed up X;Y X;Y to isomorphism if one relabels the linearly ordered set Y = fy < < y g of column 1 n bip indices in backwards order, i.e. replace y with y . This has no eect on G (D) up j n+1j X;Y bip to graph isomorphism, nor on (G (D)) up to simplicial isomorphism. However, now X;Y bip the diagram D is no longer a pedestal, but rather has a rectangular decomposition in X;Y two iterations: the rst creates a full rectangle and labels all the remaining cells as excess cells, while the second iteration creates an empty rectangle of zero width. An example is shown here y y y y y y y y y y y y 1 2 3 4 5 6 1 2 3 4 5 6 x p p p p p p x r r r r r r 1 1 1 1 1 1 1 1 x p p p p p p x r r r r r r 2 2 1 1 1 1 1 1 x p p p p x e e e e 3 3 x p p p x e e e 4 4 in which the rectangular decomposition for the diagram on the right creates the full bip rectangle D and removes 5 excess cells in the rst iteration, then creates the fx ;x g;Y 1 2 bip bip empty rectangle D in the second iteration. Thus pedestals of the form D have X;Y fx ;x g;? 3 4 bip (G (D)) contractible. X;Y The homotopy type analysis of these base cases then completes the proof, bearing in mind the following homotopy-theoretic properties of the join operation: A join with a contractible complex yields a contractible complex. The join of a space homotopy equivalent to a d -dimensional sphere and a space homotopy equivalent to a d -dimensional sphere is homotopy equivalent to a (d + 2 1 d + 1)-dimensional sphere. Forming joins commutes (up to homotopy equivalence) with taking wedges. Hochster's formula (Proposition 2.7) combined with Theorem 2.14 immediately yields the following. Corollary 2.15 For any shifted skew diagram D and any linearly ordered subsets X; Y , bip nonbip the ideals I(G (D)) and I(G (D)) have multigraded Betti numbers independent of X;Y X These properties are reasonably well-known. They may be deduced, for example, from the analogous but perhaps better-known properties [35, xIII.2] of the associative smash product (or reduced join) oper- ation X ^ Y , using the fact that the join X Y of X and Y is homotopy equivalent to the suspension of X ^ Y , or equivalently, S ^ X ^ Y [35, xX.8.III]. the electronic journal of combinatorics 16(2) (2009), #R3 17 the coecient eld k: bip bip >1 if D is spherical with rect(D ) = 0 0 0 0 X ;Y X ;Y bip 0 0 0 0 (I(G (D))) = jX [ Y j i 1 i;X tY X;Y 0 otherwise. nonbip nonbip >s if D has no empty rectangles, has rect(D ) = 0 0 X X nonbip 0 (I(G (D))) = jX j i 1 and has s non-excess staircase cells i;X 0 otherwise. 2.6 Case study: Ferrers diagrams and rook theory We analyze here in detail the example of Ferrers diagrams, recovering results from [10], and noting a curious connection to rook theory. Recall from Example 2.5 that for a partition = ( ), the Ferrers graph 1 m bip G corresponds to a diagram D having cells in row i, namely f(x ; y ) : 1 i i i j X;Y m; 1 j g. De nition 2.16 th Say that the cell (x ; y ) in the Ferrers diagram for lies on the k antidiagonal if k = i+j, i j th and let () for k = 2; 3; : : : denote the number of cells on the k antidiagonal. For example, if = (4; 4; 2) then ( (); (); (); (); ()) = (1; 2; 3; 3; 1) 2 3 4 5 6 with the diagram corresponding to G shown below, having cells labelled according to the antidiagonal on which they lie y y y y 1 2 3 4 x 2 3 4 5 x 3 4 5 6 x 4 5 0 0 0 0 0 0 Given X X; Y Y say that X Y if X and Y are non-empty and the full bip 0 0 rectangle X Y is covered by cells in the diagram D corresponding to G . X;Y Proposition 2.17 For any partition = ( > 0), consider the Ferrers 1 m (bipartite) graph G on vertex set X t Y where X = fx ; : : : ; x g and Y = fy ; : : : ; y g. 1 m 1 Then for all i 0 one has 0 0 0 0 1 if jX j + jY j = i + 2 and X Y 0 0 (I(G )) = i;X tY 0 otherwise (2.5) 0 0 for all X X; Y Y: 0 (I(G )) := 0 0 (I(G )) i;X ; i;X tY Y Y (2.6) m 0 if jX j < i + 2 ijX j+2 0 otherwise. the electronic journal of combinatorics 16(2) (2009), #R3 18 0 0 0 0 0 0 (I(G )) = jf(X ; Y ) : jX j + jY j = i + 2 and X Y gj 0 0 X X m + n 2 0 0 m =1 n =1 X (2.7) k 2 = () k2 + 1 + m 1 m 1 2 m = + + + : i + 1 i + 1 i + 1 i + 2 bip Proof. A Ferrers diagram D is easily seen to be spherical if and only if it is a full X;Y bip rectangle XY , which will always have rect(D ) = 1. Thus Corollary 2.15 immediately X;Y gives (2.5), which then immediately implies (2.6), as well as the rst formula in (2.7). The second formula in (2.7) follows from the rst formula by classifying the spherical 0 0 0 0 subdiagrams X Y inside having jX j+jY j = i+2 according to their southeasternmost cell (x 0 ; y 0) so that m n 0 0 m = max X 0 0 n = max Y : 0 0 m +n 2 One can check that there are exactly such rectangular subdiagrams. The third formula in (2.7) then comes from grouping the second formula according to the value 0 0 k = m + n . The last formula in (2.7) (which is equivalent to one stated in [10, Theorem 2.1]) comes from summing the inner summation in the second formula of (2.7). One has 0 0 0 0 m + n 2 0 + m 1 m 1 i i + 1 i + 1 n =1 P 0 m m 1 m and then one uses the fact that = . m =1 i+1 i+2 We remark that the formulae in Proposition 2.17 will also apply to row-nested graphs which appear later (Section 4.2) as these are exactly the bipartite graphs isomorphic to Ferrers graphs. These formulae also allow one to compare the Betti numbers of dierent Ferrers graphs, and lead to a curious corollary relating to the combinatorial theory of rook placements. Given a diagram D ZZ, call an r-element subset of D a (non-attacking) rook placement on D if no two of the r squares share any row or column. Say that two diagrams D; D in the plane Z Z are rook-equivalent if they have the same number of r-element rook placements for all r. In particular, taking r = 1, this means D; D must have the same number of cells, but in general, it is a somewhat subtle equivalence relation. However, when one restricts the equivalence relation to Ferrers diagrams, rook-equivalence has a nice characterization, due originally to Foata and Schutzen berger, elegantly reformulated by Goldman, Joichi, and White, and reformulated further in the following fashion by Ding [12]. the electronic journal of combinatorics 16(2) (2009), #R3 19 Proposition 2.18 Given two partitions ; , their associated Ferrers diagrams are rook equivalent if and only if () = () for all k. k k Corollary 2.19 For two partitions ; , the Ferrers graph ideals I(G ); I(G ) have the same (ungraded) Betti numbers for all i if and only if () = () for all k, that is, i k k if and only if ; are rook equivalent. k2 Proof. The formula (I(G ) = () in Proposition 2.17 gives a linear relation i k k2 i between the vectors ( (I(G ))) and ( ()) , governed by an invertible matrix of i i2 k k2 coecients. This yields the rst equivalence. The second follows from Proposition 2.18. 2.7 Specialization from bipartite to nonbipartite graphs bip The goal of this section is Theorem 2.20. It shows that I(G (D)) is a well-behaved X;X nonbip polarization of I(G (D)), generalizing results from [11]. This turns out to be very useful later when proving results about various invariants of these ideals (e.g., Castel- nuovo-Mumford regularity, Krull dimension, projective dimension, conjectural resolution bip bounds); it is generally much easier to prove things directly for I(G (D)) and then X;Y nonbip apply Theorem 2.20 to deduce the corresponding result for I(G (D)). Given a shifted skew diagram D with rows and columns indexed by [n] := f1; 2; : : : ; ng, we have seen how to associate with it two ideals in two dierent polynomial rings over a eld k: bip I(G (D)) k[x ; : : : ; x ; y ; : : : ; y ] := k[x; y] 1 n 1 n [n];[n] nonbip I(G (D)) k[x ; : : : ; x ] := k[x] 1 n [n] For both ideals we have seen how to compute multigraded Betti numbers, which we now 2n wish to compare via a certain specialization of the Z -grading on k[x ; : : : ; x ; y ; : : : ; y ] 1 n 1 n to a Z -grading. Consider the map sp fx ; : : : ; x ; y ; : : : ; y g ! fx ; : : : ; x g 1 n 1 n 1 n x 7! x i i y 7! x j j sp 2n n and the associated map of the gradings Z ! Z that sends the standard basis vec- tors e ; e 7! e for i = 1; 2; : : : ; n. Using this to de ne a Z -grading on the ring i n+i i k[x ; : : : ; x ; y ; : : : ; y ], one has for any multidegree 2 Z a specialized Betti number 1 n 1 n sp bip (I(G (D)). i; [n];[n] Theorem 2.20 For D a shifted skew diagram with rows and columns indexed by [n], one has nonbip sp bip (I(G (D))) = (I(G (D))) (2.8) i; i; [n] [n];[n] for all 2 Z . Equivalently, the electronic journal of combinatorics 16(2) (2009), #R3 20 bip (i) for all X; Y [n] one has (I(G (D))) = 0 unless X \ sp(Y ) = ?, and i;XtY [n];[n] (ii) for all Z [n], one has nonbip bip (I(G (D))) = (I(G (D))): i;Z i;XtY [n] [n];[n] X;Y [n]: Xtsp(Y )=Z Proof. We leave the discussion of the equivalence of the stated conditions to the reader, except for pointing out that (i) is a consequence of (2.8) because the squarefree monomial bip ideal I(G (D)) can have non-trivial Betti numbers only in the squarefree multidegrees [n];[n] 2n 2 f0; 1g . To prove (i), if X \ sp(Y ) 6= ?, say if an index j lies in both X and in Y , we will show bip bip that (G (D)) is contractible and hence (I(G (D))) = 0. Contractibility i;XtY X;Y [n];[n] bip comes from the fact that either D has X;Y bip no cells in row j, so (G (D)) has a cone vertex, or X;Y bip no cells in column j, so (G (D)) has a cone vertex, or X;Y bip some cell c in row j, and some cell c in column j. But there is no cell of D in X;Y position (j; j), which is the southwest corner of the rectangle de ned by c and c (since D itself has no such cell, as (j; j) is not even a cell in the shifted plane). Hence bip bip D contains a pedestal by Proposition 2.11, and (G (D)) is contractible by X;Y X;Y Theorem 2.14. To prove (ii), note that one may assume Z = [n] without loss of generality. Also note that the only non-zero summands on the right side of the equation in (ii) are X; Y [n] bip with X t sp(Y ) = [n] for which (G (D)) is not contractible. Thus we wish to show X;Y nonbip bip (I(G (D))) = (I(G (D))): (2.9) i;[n] i;XtY [n] [n];[n] X;Y [n]: Xtsp(Y )=[n] bip (G (D)) not contractible X;Y Given each pair X; Y appearing in the right side of (2.9), the proof is completed in three steps. bip Step 1. Show that D has a top cell if and only if D does. X;Y Step 2. Show that if they both have a top cell, then the rectangular decomposition for D bip begins with a full rectangle (not a pedestal) if and only if the same is true for D , X;Y and furthermore these two full rectangles are exactly the same. Step 3. One is reduced to the case where D starts its rectangular decomposition with a pedestal, which must be analyzed. the electronic journal of combinatorics 16(2) (2009), #R3 21 Step 1. Note that column 1 and row n are both empty in D. Hence non-contractibility bip of (G (D)) implies 1 62 Y and n 62 X. But X t Y = [n], so this forces 1 2 X; n 2 Y . X;Y bip Thus D contains a top cell, namely (1; n) if and only if D does. X;Y bip Step 2. Assume without loss of generality that both D and D contain the top cell (1; n). X;Y Assume that the rst step in the rectangular decomposition for D nds a full rectangle bip 0 0 D , say with neck cell (m ; n ). The rst step in the rectangular decomposition for 0 0 X ;Y bip bip D nds either a full rectangle or pedestal D . We wish to carefully argue that 00 00 X;Y X ;Y 00 0 00 0 these are the same, i.e. that X = X and Y = Y . 00 00 0 Start by noting that 1 2 X ; n 2 Y . One can characterize X as the largest initial 0 00 segment of [n] with the property that X fng D. Similarly one has that X is the bip 00 00 0 largest initial segment of X with X fng D . But this implies that X = X \ X. X;Y 00 0 0 Similarly one can argue that Y = Y \ Y . Thus it remains to show that X X and Y Y . bip To argue this, we must rst \prepare" D by possibly removing some of its excess X;Y bip cells. Given any cell c = (i; j) in D that has both i; j 2 X , we claim that c is an X;Y bip excess cell to the left of the rst rectangle D . To see this claim, we need to check 00 00 X ;Y 00 00 that its row index i lies in X and that its column index j is less than any element of Y . 0 00 0 The rst fact is true since i 2 X \ X = X . The second follows because j 2 X implies 0 0 0 0 00 j max X = m < n = min Y min Y ; 0 0 0 0 the relation m < n comes from the fact that (m ; n ) is a cell of D (so it lies in the shifted 00 0 0 plane), while the last inequality is a consequence of the fact that Y = Y \ Y Y . bip Thus without loss of generality, D has no cells in (i; j) with both i; j 2 X ; they X;Y bip are all excess cells which can be removed without aecting (G (D)) up to homotopy. X;Y bip This means D has all of the columns indexed by X empty. Non-contractibility of X;Y bip 0 0 (G (D)) then forces X \ Y = ?. Together with X t Y = [n], this implies, X X, X;Y 00 0 0 00 0 and hence X = X \ X = X , as desired. A symmetric argument shows Y = Y , completing Step 2. Step 3. By Steps 1 and 2, one may assume without loss of generality that D produces a pedestal in the rst (and only) step of its rectangular decomposition. One must show why equation (2.9) holds in this case. bip We claim non-contractibility of (G (D)) has strong consequences for the form of X;Y bip X and Y . It forces any row i in X to contain at least one cell of D ; call this cell c. X;Y bip Similarly, any column j in Y contains at least one cell of D ; call this cell c . Non- X;Y contractiblity also forces i < j for any such i in X and j in Y : if i j, then the cell (i; j) bip that would be the southwest corner of the rectangle de ned by c; c is not in D (since X;Y bip it is not in the shifted plane), and hence D has a pedestal by Proposition 2.11 and X;Y bip (G (D)) is contractible by Theorem 2.14. In other words, max X < min Y , which X;Y the electronic journal of combinatorics 16(2) (2009), #R3 22 combined with X t Y = [n] forces X = f1; 2; : : : ; jg Y = fj + 1; j + 2; : : : ; ng bip for some j = 1; 2; : : : ; n 1. One can also check that D is a full f1;2;:::;jg;fj+1;j+2;:::;ng rectangle if (j; j + 1) is a non-excess staircase cell in the pedestal of D, and otherwise bip (G ) is contractible. Thus (2.9) holds because both sides f1;2;:::;jg;fj+1;j+2;:::;ng vanish for i 6= n 2, and are equal to the number of (non-excess) staircase cells in the pedestal of D for i = n 2. bip The following corollary says that the ideal I(G (D)) in k[x; y] is a well-behaved X;Y nonbip polarization (see the Appendix, Lemma 6.9) of the ideal I(G (D)) in k[x], and lists the usual consequences for Castelnuovo-Mumford regularity and projective dimension; see Subsection 2.8 for de nitions. Corollary 2.21 In the setting of Theorem 2.20, if X = Y , then one has bip nonbip (i) (I(G (D))) = (I(G (D))) for all i; j. In particular, the two ideals share i;j i;j X;Y X the same projective dimension and Castelnuovo-Mumford regularity. (ii) The linear forms ; : : : ; where := x y have images in the quotient ring 1 n i i i bip k[x; y]=I(G (D)) forming a regular sequence. X;Y nonbip (iii) A minimal free resolution for I(G (D)) as a k[x]-module can be obtained from bip a minimal free resolution for I(G (D)) as a k[x; y]-module, simply by modding X;Y out () := ( ; : : : ; ), that is, by tensoring over k[x; y] with k[x; y]=(). 1 n Proof. Assertion (i) follows from Theorem 2.20 and Hochster's formula. The remaining assertions are seen to be equivalent to it by iterating Lemma 6.9 from the Appendix. Example 2.22 Such polarizations and specializations do not work so well for an arbitrary bipartite graph G and its edge ideal I(G) k[x; y]. In other words, it is not in general nonbip nonbip true that the specialized ideal I k[x] for which k[x; y]=(I(G) + ()) = k[x]=I nonbip has (I ) = (I(G)). i;j i;j For example, let G be the bipartite graph on vertex set XtY = fx ; : : : ; x ; y ; : : : ; y g 1 5 1 5 for which I(G) = (x y ; x y ; x y ; x y ; x y ; x y ); and 1 3 1 4 2 3 2 5 3 4 3 5 nonbip I = (x x ; x x ; x x ; x x ; x x ; x x ): 1 3 1 4 2 3 2 5 3 4 3 5 the electronic journal of combinatorics 16(2) (2009), #R3 23 bip This bipartite graph G is a 6-cycle, which one can check is not of the form G (D) for X;Y any shifted skew-shape D. However, one can still think of the edges of G as corresponding to the cells of a diagram in the shifted plane, which would look like this: 1 2 3 4 5 Here is the result of a Macaulay 2 calculation of their graded Betti numbers, with k = Q: i1 : S=QQ[x1,x2,x3,x4,x5,y1,y2,y3,y4,y5]; i2 : IG=ideal(x1*y3,x1*y4,x2*y3,x2*y5,x3*y4,x3*y5); o2 : Ideal of S i3 : betti(resolution(IG)) 0 1 2 3 4 o3 = total: 1 6 9 6 2 0: 1 . . . . 1: . 6 6 . . 2: . . 3 6 2 i4 : Snonbip=QQ[x1,x2,x3,x4,x5]; i5 : Inonbip=ideal(x1*x3,x1*x4,x2*x3,x2*x5,x3*x4,x3*x5); o5 : Ideal of Snonbip i6 : betti(resolution(Inonbip)) 0 1 2 3 4 o6 = total: 1 6 9 5 1 0: 1 . . . . 1: . 6 8 4 1 2: . . 1 1 . the electronic journal of combinatorics 16(2) (2009), #R3 24 2.8 Castelnuovo-Mumford regularity bip The next three subsections discuss three natural invariants for the ideals I(D ) and X;Y nonbip I(D ), namely their Castelnuovo-Mumford regularity, projective (or homological) dimension, and bip nonbip Krull dimension of the quotient rings k[x; y]=I(G (D)) and k[x]=I(G (D)). X;Y X Recall the de nition of the Castelnuovo-Mumford regularity reg (M ) for a Z-graded module M over a regular Z-graded k-algebra S: S S reg (M ) = maxfj i : (M )(= dim Tor (M; k) ) 6= 0g: k j S i;j i The goal of this section is Theorem 2.23, which interprets combinatorially the regularity bip nonbip for both classes of ideals I(G (D)); I(G (D)), in terms of the quantity rectangularity X;Y X de ned in De nition 2.13 above. Theorem 2.23 For any shifted skew diagram and linearly ordered subsets X; Y , one has bip bip reg (I(G (D))) = rect(D ) + 1 k[x;y] X;Y X;Y nonbip nonbip reg (I(G (D))) = rect(D ) + 1 k[x] X X nonbip bip Proof. Note that the assertion for D will follow after proving it for D , since X X;Y nonbip bip rect(D ) = rect(D ) X X;X by de nition of the rectangular decomposition, and nonbip bip reg (I(G (D))) = reg (I(G (D))) k[x] k[x;y] X X;X by Theorem 2.20. bip To prove the assertion for D , rst note that X;Y bip reg (I(D )) k[x;y] X;Y k[x;y] bip := maxfj i : (I(D )) 6= 0g i;j X;Y k[x;y] bip 0 0 0 0 = maxfjX t Y j i : X X; Y Y and (I(D )) 6= 0g 0 0 i;X tY X;Y bip bip 0 0 = maxfrect(D ) + 1 : X X; Y Y; and D is spherical g 0 0 0 0 X ;Y X ;Y where the last equality comes from Corollary 2.15. bip bip To show the inequality reg (I(D )) rect(D ) + 1, note that if one chooses k[x;y] X;Y X;Y 0 0 X ; Y to be the rows and columns occupied by the union of all the full rectangles along with the rst few equal-sized (i.e. longest) rows in the pedestal (if present), then the bip bip bip subdiagram D is spherical with rect(D ) = rect(D ). 0 0 0 0 X ;Y X ;Y X;Y The reverse inequality follows from Lemma 2.24 below. the electronic journal of combinatorics 16(2) (2009), #R3 25 bip Lemma 2.24 For any non-empty diagram of the form D and any subsets X X;Y X; Y Y , one has bip bip rect(D ) rect(D ) 0 0 X ;Y X;Y Proof. Prove this by induction on jXj + jY j. The base case where jXj + jY j = 1 is trivial. For the inductive step, it suces to prove that when one removes a row or column bip from D , the rectangularity cannot go up. Without loss of generality one is removing X;Y bip a non-empty column C from E := D , and we wish to show that X;Y rect(E n C) rect(E): (2.10) By induction, one may assume that E has a top cell, else one can remove an empty row or column from E, leaving both rect(E); rect(E n C) unchanged. Hence the rst step in the rectangular decomposition for E identi es either a full rectangle or pedestal. If it is a pedestal, then rect(E) = rect(EnC) = 1. Thus without loss of generality one may assume that the rst step identi es a full rectangle R; let E denote the remaining diagram after one removes from E the rows and columns occupied by this full rectangle R. For most choices of the column C, one has that E n C shares the same top cell as E, and begins its rectangular decomposition with the full rectangle Rn C or R. In the second case, one has (E n C) = E n C for some column C . Using rect(E) = rect(E ) + 1 (2.11) rect(E n C) = rect((E n C) ) + 1 along with the inductive hypothesis applied to E , one obtains the desired inequality (2.10). In the rst case, we have E = (E n C) and we argue by induction, unless C is the rightmost column C , and the column C second from the right occupies a dierent set n n1 of rows from those occupied by C . Case 1. The column C starts in the same (top) row as the column C , but is longer and n1 n hence extends to lower rows than C . Here one nds that E n C begins its rectangular n n decomposition with a full rectangle that occupies more rows than R. Hence when this larger rectangle is removed from E n C , one nds that (E n C) is obtained from E by removing some rows, and so the inductive hypothesis applies to show rect((E n C) ) rect(E ). Then (2.11) gives the desired inequality (2.10). Case 2. The column C does not start in the top row, unlike column C . In this case n1 n R = C is the entire rst full rectangle in the decomposition for E. Since column C n n1 does not start in the top row, it must extend down to at least as many rows as column C does, or further. This means that (EnC) is obtained from E by removing some columns (at least the column C ) and possibly also some rows. Thus, the inductive hypothesis n1 again shows rect((E n C) ) rect(E ), and one again applies (2.11) to conclude the desired inequality (2.10). the electronic journal of combinatorics 16(2) (2009), #R3 26 2.9 Krull dimension bip To nd an interpretion of the Krull dimension of the quotient rings k[x; y]=I(G (D)) X;Y nonbip and k[x]=I(G (D)), Corollary 2.21 again says that one only needs to do this for bip k[x; y]=I(G (D)). X;Y For any bipartite graph G on vertex set X t Y with edges E(G) (not necessarily of the bip form G (D)), the Krull dimension for k[x; y]=I(G) is the quantity (G) equal to the X;Y maximum size of a coclique (stable set, independent set) of vertices. This quantity (G) is one of four graph invariants for a graph G = (V; E) closely related by classical theorems of graph theory (see e.g. [34, Chapter 3]), which we review here: (G) := maxfjCj : C V is a coclique, i.e. C contains no vertices that share an edgeg (G) := minfjFj : F E is an edge cover, i.e. F is incident to all of V g (G) := maxfjMj : M E is a matching, i.e. M contains no edges that share a vertexg (G) := minfjWj : W V is a vertex cover, i.e. W is incident to all of Eg: Gallai's Theorem asserts that for any graph G one has (G) + (G) = jV j = (G) + (G) while K onig's Theorems assert that for a bipartite graph G one has (G) = (G) = jV j (G) = jV j (G): There are very ecient algorithms (e.g. the augmenting path algorithm) for computing (G) by nding a maximum-cardinality matching in a bipartite graph G. Hence the Krull dimension (G) = (G) is easy to compute for k[x; y]=I(G) of any bipartite graph G. We bip do not know of a faster algorithm tailored to the speci c class of bipartite graphs G (D) X;Y when D is a shifted skew diagram. 2.10 Projective dimension Recall that the projective (or homological) dimension pd (M ) for a nitely-generated module M over a polynomial algebra S is the length of any minimal free S-resolution of M , that is, the largest i for which (M ) 6= 0. Also recall that for any ideal I, since (I) = (S=I), one has pd (I) = pd (S=I) 1. i i+1 S S bip In studying the projective (or homological) dimension of the ideals I(G (D)) and X;Y nonbip I(G (D)), one is again reduced to studying the former, as Theorem 2.20 implies nonbip bip pd I(G (D)) = pd I(G ): k[x] X k[x;y] X;X For the latter, one at least has the following combinatorial interpretation. the electronic journal of combinatorics 16(2) (2009), #R3 27 Proposition 2.25 Given any shifted skew diagram D and linearly ordered subsets X; Y , one has bip 0 0 bip pd I(G (D)) = maxfjX j + jY j rect(D ) 1g 0 0 k[x;y] X;Y X ;Y 0 0 X ;Y bip 0 0 where the maximum runs over all subsets X X; Y Y for which D is spherical. 0 0 X ;Y bip 0 0 Proof. This is immediate from Corollary 2.15, since the X ; Y with D spherical are 0 0 X ;Y bip 0 0 the ones which contribute to nonzero , namely with i = jX j + jY j rect(D ) 1. i 0 0 X ;Y One might hope that this maximum can be computed quickly from the rectangular bip decomposition, but this is not even true in the case where D looks like a single Fer- X;Y rers diagram. Here the rectangular decomposition is very simple, in that it has one full rectangle, followed possibly by one empty rectangle. However, the spherical subdiagrams bip D one must consider to compute the above maximum correspond to the corner cells 0 0 X ;Y of the Ferrers diagram; cf. [10, Corollary 2.2]. Remark 2.26 Herzog and Hibi [17, Corollary 3.5] have shown that, for each bipartite graph G, the ring k[x; y]=I(G) is Cohen-Macaulay if and only if the projective variety de ned by the edge ideal I(G) is equidimensional and connected in codimension one. We suspect that the nonbip analogous conclusion is also true for a nonbipartite graph G (D). 3 PART II: Skew hypergraph ideals 3.1 Non-quadratic monomial ideals and hypergraphs Consider ideals I in k[x] := k[x ; : : : ; x ] generated by squarefree monomial generators 1 n x x of a xed degree d 2. When the number of variables n is allowed to vary, i i 1 d such ideals are parametrized by the collection K := ffi ; : : : ; i g : x x 2 Ig 1 d i i 1 d called a d-uniform hypergraph, where here P := f1; 2; : : :g denotes the positive integers. nonbip Our goal here is to introduce hypergraph generalizations of the ideals I(G (D)) and bip I(G (D)) coming from shifted skew diagrams, as well as the Ferrers graph ideals I(G ), X;Y in order to ask and answer questions about their resolutions. For this it helps to consider certain orderings and pre-orderings on the d-subsets . De nition 3.1 Given two d-subsets S = fi < < i g 1 d 0 0 0 S = fi < < i g 1 d the electronic journal of combinatorics 16(2) (2009), #R3 28 say that S S in the Gale (or componentwise, or Bruhat) partial ordering on if Gale i i for all j. 0 0 Say that S S in the preordering by maxima on if i i . max d Say that S S in the colexicographic (or squashed) linear ordering on if colex 0 0 0 0 S = S or the maximum element of the symmetric dierence SS := (S n S ) t (S n S) lies in S . Note that 0 0 0 S S implies S S implies S S : Gale colex max For the sake of considering monomial ideals which are not necessarily squarefree, de ne a d-element multiset of P to be a sequence (i ; i ; : : : ; i ) with i 2 P and i i i . 1 2 d j 1 2 d P+d1 Denote by the collection of all such d-element multisets; clearly monomial ideals I generated in degree d are parametrized by the collection P + d 1 M := f(i : : : i ) : x x 2 Ig : 1 d i i 1 d P+d1 De ne the Gale partial ordering on by saying 0 0 0 (i i ) (i i ) if i i for j = 1; 2; : : : ; d: 1 d Gale j 1 d j Note that there is a simple depolarization bijection P P+d1 depol : ! d d fi < < i g 7! (i ; i 1; i 2; : : : ; i (d 1)) 1 d 1 2 3 d which is also an order-isomorphism between the Gale orders on these two sets. We omit the straightforward proof of the following easy properties of the Gale order- ings, which will be used in the proof of Theorem 3.13 below. P P+d1 Proposition 3.2 The Gale orderings on and share the following properties. d d (i) They are lattices with meet and join operations corresponding to componentwise minimum and maximum, that is, if v = (i ; : : : ; i ) 1 d 0 0 0 v = (i ; : : : ; i ) 1 d then 0 0 0 v ^ v = (minfi ; i g; : : : ; minfi ; i g) 1 d 1 d 0 0 0 v _ v = (maxfi ; i g; : : : ; maxfi ; i g): 1 d 1 d 0 0 v v v^v (ii) They have the property that if x ; x divide some monomial , then x also divides One might call this collection M a hypermultigraph, but we will rather try to avoid choosing some terminology for such an object! the electronic journal of combinatorics 16(2) (2009), #R3 29 De nition 3.3 Say that a d-uniform hypergraph K is squarefree strongly stable if it forms an order ideal in the Gale ordering on . When d = 2, these are exactly the threshold graphs P+d1 from Example 2.6. Similarly, say that collection M is strongly stable if it forms P+d1 an order ideal in the Gale ordering on . The reason for the terminology is that the associated squarefree monomial ideal I(K) (resp. monomial ideal I(M )) generated by fx x : (i ; : : : ; i ) 2 K (resp. M )g i i 1 d 1 k is usually called a squarefree strongly stable (resp. strongly stable) ideal generated in degree d. Eliahou and Kervaire [15] gave an explicit minimal free resolution for the more gen- eral class of stable monomial ideals [15], including those generated in dierent degrees; Aramova, Herzog and Hibi [1] gave an analogous resolution for squarefree stable ideals, again including those generated in dierent degrees. In Theorem 3.13 below, we will recover an extremely simple cellular version of these minimal free resolutions for both kinds of ideals, when the ideals are generated in a single degree d. In fact, we will show that when M = depol(K), the two resolutions for I(K) and I(M ) are in a precise sense, the same. The resolution for strongly stable ideals also reproves a recent result of Sine- fakopoulos [30], who produced such a cellular resolution by a somewhat more complicated inductive process. We have not checked whether his cellular resolution is exactly the same as ours. De nition 3.4 De ne a skew squarefree strongly stable d-uniform hypergraph to be one of the form KnK 0 0 where K ; K are both squarefree strongly stable and K K. Such hypergraphs have been studied recently from the viewpoint of combinatorial Laplacians by Duval [14]. (1) (d) Say that a d-uniform hypergraph is d-partite on a partitioned vertex set X t tX (j) if each of its d-sets i < < i has i 2 X for all j. 1 d j P P+d1 Given either a d-uniform hypergraph K , or a nite collection M , we d d (1) (d) will associate to it a d-partite d-uniform hypergraph F (K) or F (M ) on X t t X (j) (j) (j) where X := f1 ; 2 ; : : :g, namely (1) (2) (d) F (K) := ffi ; i ; : : : ; i g : fi < < i g 2 Kg 1 d 1 2 d (1) (2) (d) F (M ) := ffi ; i ; : : : ; i g : (i i ) 2 Mg: 1 d 1 2 One also derives from these hypergraphs F (K); F (M ) certain ideals I(F (K)); I(F (M )) in a polynomial algebra having d dierent variable sets. In an unfortunate clash of notation, the squarefree strongly stable d-uniform hypergraphs K are sometimes called shifted, although they have nothing to do with the shifted plane occurring earlier in this paper! In yet another unfortunate clash of notation, the word threshold has been used for a property of hypergraphs that is somewhat stronger than being squarefree strongly stable; see [21]. the electronic journal of combinatorics 16(2) (2009), #R3 30 Example 3.5 (1) (2) (3) We illustrate this here for d = 3, relabelling the partitioned vertex set X t X t X as fa ; a ; : : :g t fb ; b ; : : :g t fc ; c ; : : :g 1 2 1 2 1 2 to avoid superscripts: K = f123; 124; 134; 234; 125; 135g I(K) = (x x x ; x x x ; x x x ; x x x ; x x x ; x x x ) 1 2 3 1 2 4 1 3 4 2 3 4 1 2 5 1 3 5 I(F (K)) = (a b c ; a b c ; a b c ; a b c ; a b c ; a b c ) 1 2 3 1 2 4 1 3 4 2 3 4 1 2 5 1 3 5 and letting M := depol(K), one has M = f111; 112; 122; 222; 113; 123g 3 2 2 3 2 I(M ) = (x ; x x ; x x ; x ; x x ; x x x ) 2 1 3 1 2 3 1 1 2 2 1 I(F (M )) = (a b c ; a b c ; a b c ; a b c ; a b c ; a b c ) 1 1 1 1 1 2 1 2 2 2 2 2 1 1 3 1 2 3 In the next subsection, we will focus on the non-skew special case where K is empty, generalizing threshold and Ferrers graph ideals, by giving a simple cellular linear resolution for the ideals I(K); I(M ); I(F (K)); I(F (M )) generalizing those from [10, 11], and which are in a precise sense, all the same if M = depol(K). In fact, the same methods will also apply to the following ideals, which are a slightly dierent generalization of Ferrers graph ideals to hypergraphs. (1) (d) De nition 3.6 Say that a d-partite d-uniform hypergraph F on vertex set X t tX (j) is a Ferrers hypergraph if there is a linear ordering on each X such that whenever 0 0 0 (j) 0 0 (i ; : : : ; i ) 2 F and (i ; : : : ; i ) satis es i i in X for all j, one also has (i ; : : : ; i ) 2 1 d j 1 d j 1 d (1) F . In other words, F is an order ideal in the componentwise partial ordering on X (d) X . The next proposition generalizes the fact that Ferrers graphs G are isomorphic to a bip subclass of graphs of the form G (D) for shifted skew diagrams D. X;Y Proposition 3.7 Every Ferrers d-uniform hypergraph F is isomorphic to a d-partite d- 0 0 uniform hypergraph of the form F (K n K ) with K; K squarefree strongly stable. (1) (d) (j) Proof. Let F have partitioned vertex set X t t X , and let N := max fjX jg. (1) (d) One can then regard the componentwise ordering on X X as a subposet of d d the componentwise order [N ] for [N ] := f1; 2; : : : ; Ng, and F [N ] as an order ideal. Then the interval [S ; T ] in the Gale ordering on between the sets F F Gale S := f1 < N + 1 < 2N + 1 < < (d 1)N + 1g T := fN < 2N < 3N < < dNg has an obvious order-isomorphism : [S ; T ] ! [N ] F F fi < < i g 7! (i ; i N; i 2N; : : : ; i (d 1)N ): 1 d 1 2 3 d the electronic journal of combinatorics 16(2) (2009), #R3 31 1 The inverse image (F ) is an order ideal inside the interval [S ; T ] which is order- F F Gale isomorhpic to F . De ne the squarefree strongly stable hypergraphs 0 1 0 K := fS 2 : there exist S 2 (F ) with S Sg K := fS 2 K : S 6 S g: Then it is easily seen that F (K n K ) and F are isomorphic as d-partite d-uniform hyper- graphs. 3.2 Cellular resolutions We give a quick review here of the theory of cellular resolutions [25, Chapter 4]. Then we use this to produce an extremely simple, linear , minimal free resolution for the square-free strongly stable ideals I(K) generated in xed degree, as well as their rela- tives I(F (K)); I(M ); I(F (M )), and for all ideals I(F ) with F a Ferrers hypergraph. De nition 3.8 Let C be a polyhedral cell complex, that is, a nite collection C = fP g of convex polytopes P (called cells or faces of C) in some Euclidean space, with each face of P also lying in C, and the intersection P \ P forming a face of both P and P . i i j i j Given a labelling of the vertices (= 0-dimensional cells) of C by monomials in a poly- nomial ring S = k[x ; : : : ; x ], one obtains a labelling of each face P by the least com- 1 N mon multiple m of the monomials that label the vertices lying in P . Letting I be the monomial ideal generated by all the monomial labels of all of the vertices, one obtains a N th Z -graded complex of S-modules F (C) in which the i term F (C) for i 1 is the free S-module with basis elements e indexed by the i-dimensional faces P of C, decreed to have multidegree m . The dierential is de ned S-linearly by d(e ) := sgn(P; Q) e P Q in which Q runs through all the codimension 1 faces of P , and sgn(P; Q) 2 f+1; 1g denotes the incidence function produced from an orientation of the cells of C used in the usual cellular chain complex that computes the homology of C. Note that C, if nonempty, always has exactly one face of dimension 1, namely the empty face ?, so that F (C) S is a free S-module of rank 1 with basis element e of 1 ? multidegree 0. Furthermore, note that the complex F (C) has been arranged so that S=I is the cokernel of the map F (C) ! F (C). In some cases, F (C) is a resolution of S=I and 0 1 lets us compute its Betti numbers { the basic proposition in the theory of cellular resolu- tions tells us that this is controlled by the reduced homology with coecients in k of the subcomplexes de ned for each monomial multidegree by C := fP 2 C : m divides g We are slightly abusing notation here. Strictly speaking, what we get should be called a d-linear resolution: all the minimal generators of the ideal have degree d, while all higher syzygy maps are given by linear forms. the electronic journal of combinatorics 16(2) (2009), #R3 32 Proposition 3.9 [25, Proposition 4.5] F (C) is a resolution of S=I if and only if, for every multidegree 2 Z , the subcomplex C is k-acyclic. Example 3.10 (The Taylor resolution [32]) Let I be any monomial ideal in the polyno- mial ring S, and choose an ordered generating set of monomials (m ; : : : ; m ) for I. Then 1 p the Taylor resolution T (S=I) of S=I with respect to this ordered generating set has as th ( ) its i term T (S=I) S , the free S-module with basis fe : A [p]; jAj = ig. One i A decrees the Z -graded multidegree of e to be m = lcmfm : a 2 Ag. The dierential A A a in T (S=I) is de ned S-linearly by d(e ) := sgn(A; a) e ; A Anfag Anfag a2A r th where sgn(A; a) = (1) if a is the r smallest element of A. It is well-known and straightforward to check that the Taylor resolution T (S=I) is the cellular resolution F (C) associated to the cell complex C which is a (p 1)-dimenensional simplex having vertices labelled by the generators m ; : : : ; m for I. 1 p 3.3 The complex-of-boxes resolution We next describe the particular polyhedral complexes that will support our cellular reso- lutions. De nition 3.11 Let F be a d-partite d-uniform hypergraph on the partitioned vertex (1) (d) set X t t X . By a box inside K we will mean a subset of F which is a Cartesian (j) product X X for some subsets X X . 1 d j De ne the complex of boxes inside F to be the polyhedral subcomplex of the product of (1) (d) X X simplices 2 2 having faces indexed by the boxes inside K. Alternatively, the complex of boxes inside F is de ned to be the vertex-induced subcomplex of the Cartesian (1) (d) X X product of simplices 2 2 on the set of vertices indexed by the sets in F . That is, it consists of all polytopal cells in the Cartesian product whose vertices all lie in F . Example 3.12 Let K; M = depol(K); F (K); F (M ) be as in Example 3.5. Then the complex of boxes C inside F (K) or F (M ) are both isomorphic to a quadrangle and triangle glued along an edge, with a pendant edge hanging from a nonadjacent vertex of the quadrangle. The following diagrams illustrate these complexes of boxes, with vertices labelled in boldface by the generators of the ideals I(F (K)); I(K); I(F (M )); I(M ), and with higher-dimensional faces P labelled in small script by the least common multiple m . The complexes for I(K) and I(M ) are obtained from the ones for I(F (K)) and I(F (M )), respectively, by specializing the labels as described in Theorem 3.13 below. the electronic journal of combinatorics 16(2) (2009), #R3 33 a b c 1 2 3 a b c c a b c c 1 2 3 5 1 2 3 4 For I(F (K)): a b c c c 1 2 3 4 5 a b c a b c c a b c 1 2 5 1 2 4 5 1 2 4 a b b c a b b c c a b b c 1 2 3 5 1 2 3 4 5 1 2 3 4 a b c a b c c a b c a a b c a b c 1 3 5 1 3 4 5 1 3 4 1 2 3 4 2 3 4 x x x 1 2 3 x x x x x x x x 1 2 3 5 1 2 3 4 For I(K): x x x x x 1 2 3 4 5 x x x x x x x x x x 1 2 5 1 2 4 5 1 2 4 x x x x x x x x x x x x x 1 2 3 5 1 2 3 4 5 1 2 3 4 x x x x x x x x x x x x x x x x x 1 3 5 1 3 4 5 1 3 4 1 2 3 4 2 3 4 a b c 1 1 1 a b c c a b c c 1 1 1 3 1 1 1 2 For I(F (M )): a b c c c 1 1 1 2 3 a b c a b c c a b c 1 1 3 1 1 2 3 1 1 2 a b b c a b b c c a b b c 1 1 2 3 1 1 2 2 3 1 1 2 2 a b c a b c c a b c a a b c a b c 1 2 3 1 2 2 3 1 2 2 1 2 2 2 2 2 2 the electronic journal of combinatorics 16(2) (2009), #R3 34 3 3 3 x x x x 3 2 1 1 For I(M ): x x x 2 3 2 2 2 x x x x x x x 3 2 3 2 1 1 1 2 2 2 2 2 x x x x x x x x 2 3 3 1 1 2 1 2 2 2 3 3 x x x x x x x x x x x 1 2 3 1 3 1 1 2 2 2 2 P P+d1 Theorem 3.13 Let K be squarefree strongly stable, and let M be d d strongly stable, with F (K); F (M ) their associated d-partite d-uniform hypergraphs. Let F be any d-partite d-uniform Ferrers hypergraph. (1) (d) (i) For any of the ideals I = I(F (K)); I(F (M )); I(F ) inside S := k[x ; : : : ; x ], (1) (d) labelling a vertex (i ; : : : ; i ) of the complex of boxes by the monomial x x 1 d i i gives a minimal linear cellular S-resolution of S=I. Hence (I) = 1 jX jd;X ttX j d for every box X X inside F or F (K), and all other Betti numbers vanish. 1 d (ii) Furthermore, the specialization map (1) (d) sp : k[x ; : : : ; x ] ! k[x] (j) x 7! x sends the resolution for I(F (K)) or I(F (M )) to a (minimal, linear, cellular) res- olution for I(K) or I(M ). In other words, re-labelling a vertex (i ; : : : ; i ) of the 1 d complex of boxes for F (K) or F (M ) by x x yields a k[x]-resolution of I(K) i i 1 d or I(M ). In particular, I(F (K)); I(K) have the same Z-graded Betti numbers, and the ideals I(F (M )); I(M ) have the same Z-graded Betti numbers. depol P P+d1 (iii) If M = depol(K), then the bijection ! induces a cellular isomorphism d d of the complex of boxes for I(F (K)) and I(F (M )), preserving the degree of the monomials m labelling faces. Consequently, I = I(K); I(M ); I(F (K)); I(F (M )) all have the same Z-graded Betti numbers (I) in this siutation. i;j Strictly speaking, it is a resolution for the quotient of the polynomial ring by the ideal, not for the ideal itself. However, deleting the term in homological degree 0 gives a resolution for the ideal itself. the electronic journal of combinatorics 16(2) (2009), #R3 35 Proof. To simplify notation, assume d = 3, and let a ; b ; c be the three sets of variables; i j k it will be clear that the argument given works for general d. We deal with the part of (i) asserting that the cellular complexes give cellular resolu- tions last. Assuming this, for the rest of assertion (i), note that for each box P = fa ; : : : ; a g fb ; : : : ; b g fc ; : : : ; c g (3.1) i i j j k k 1 r 1 s 1 t in one of the appropriate complexes of boxes inside F; F (K); F (M ), the least common multiple monomial m will have the appropriate degree for a cellular resolution which is d-linear (and hence also minimal), namely deg m = dim P + d: This is because one can easily check that for the labelling with generators of I(F ); I(F (K)); I(F (M )), one has m = (a a )(b b )(c c ); P i i j j k k 1 r 1 s 1 t and for the labelling with generators of I(K); I(M ), one has m = (x x )(x x )(x x ): P i i j j k k 1 r 1 s 1 t In any case, deg m = r + s + t; while dim P = (r 1) + (s 1) + (t 1); so deg m = dim P + 3(= dim P + d). The above descriptions of m also show assertion (ii) of the theorem. Assertion (iii) follows when M = depol(K) because the depolarization bijection on vertices extends to a bijection sending the typical box P inside F (K) shown in (3.1) to the following box inside F (M ): depol(P ) := fa ; : : : ; a g fb ; : : : ; b g fc ; : : : ; c g: i i j 1 j 1 k 2 k 2 1 r 1 s 1 t Lastly we deal with the rst part of assertion (i), asserting that one has various cellular resolutions. By Proposition 3.9, it suces to show that for any of the ideals I(F ); I(K); I(F (K)); I(M ); I(F (M )), if C is the appropriate complex of boxes labelled with the generators of this ideal, then for any multidegree in the appropriate polynomial ring, the subcomplex C is contractible. In fact, we will do this by induction on the number of vertices of C ; in the base case when C has only one vertex, this is trivial. In the inductive step, pick any vertex v of C whose corresponding set or multiset is Gale-maximal among all the vertices of C . We claim that (a) there is a unique facet (maximal face) P of C containing v, and v; (b) if v is not the only vertex of C , then this facet P has strictly positive dimension. v; Assuming claims (a) and (b) for the moment, the argument is completed as follows. Lemma 6.4 below implies that C is homotopy equivalent to the subcomplex C n fvg obtained by deleting all faces containing v. Because C and C are de ned as vertex- induced subcomplexes, the deletion C n fvg is isomorphic to one of the subcomplexes the electronic journal of combinatorics 16(2) (2009), #R3 36 0 C 0 which arises for an ideal I in the same family as I, where one has removed the generator of I corresponding to v. Since C has at least one fewer vertex than C , it is contractible by induction. Hence C is also contractible. Proof of Claim (a): We exhibit explicitly the unique facet P of C that contains v; a vertex v corresponding to a Gale-maximal triple (i ; i ; i ), for each kind of ideal 1 2 3 I = I(F ); I(K); I(M ); I(F (K)); I(F (M )). In each case it is not hard to use the Gale- maximality of v to argue that if v lies in some face P of C , then P P . We give this v; argument explicitly below for only one of the ve kinds of ideals, namely those of the form I(F (K)), as it is representative of how one argues any of the cases. We also introduce here a notational convenience: given a linearly ordered set such as x ; x ; : : :, denote the 1 2 closed interval fx ; x ; : : : ; x ; x g by [x ; x ]. i i+1 j1 j i j When I = I(F ) for a Ferrers hypergraph F , then is a monomial in the variables a ; b ; c , i j k and one has P = ([a ; a ] \ supp ) ([b ; b ] \ supp ) ([c ; c ] \ supp ) : v; 1 i 1 i 1 i 1 2 3 5 4 2 9 3 2 For example, if v = (2; 4; 2) and = a a a b b b b c c c , then P = fa ; a g 2 2 4 5 v; 1 2 1 3 1 5 2 4 fb ; b ; b g fc g: 1 2 4 2 When I = I(F (K)) for K squarefree strongly stable, then is a monomial in the variables a ; b ; c , and one has i j k P = ([a ; a ] \ supp ) ([b ; b ] \ supp ) ([c ; c ] \ supp ) : v; 1 i i +1 i i +1 i 1 1 2 2 3 3 2 4 5 7 3 2 For example, if v = (3; 4; 6) and = a a b b b b c c c c c , then P = fa ; a g fb g 1 7 4 7 v; 1 3 4 3 1 3 4 2 5 6 fc ; c g: 5 6 For this case we provide the argument that every face P of C that contains v must have P P . Express such a face P containing v in the form v; fa ; : : : ; a g fb ; : : : ; b g fc ; : : : ; c g: i i j j k k min max min max min max Because v = (i ; i ; i ) lies in P , one has the inequalities 1 2 3 i i i < j i j < k i k : (3.2) min 1 max min 2 max min 3 max Then Gale-maximality of v forces the equalities i = i 1 max i = j (3.3) 2 max i = k : 3 max The fact that P lies inside C , together with (3.2) and (3.3), implies fa ; : : : ; a g [a ; a ] \ supp i i 1 i max min 1 fb ; : : : ; b g [b ; b ] \ supp j j i +1 i min max 1 2 fc ; : : : ; c g [c ; c ] \ supp : k k i +1 i max 2 3 min the electronic journal of combinatorics 16(2) (2009), #R3 37 This means that P is a subface of P . v; P+d1 When I = I(F (M )) for M strongly stable, then is a monomial in the variables a ; b ; c , and one has i j k P = ([a ; a ] \ supp ) ([b ; b ] \ supp ) ([c ; c ] \ supp ) : v; 1 i i i i i 1 1 2 2 3 3 2 4 5 7 3 2 For example, if v = (3; 4; 6) and = a a b b b b c c c c c , then P = fa ; a g 1 7 4 7 v; 1 3 3 1 3 4 2 5 6 fb ; b g fc ; c ; c g: 3 4 4 5 6 When I = I(K) for K squarefree strongly stable, then is a monomial in the vari- ables x , P is the specialization of the corresponding box P in the complex resolving i v; v; I(F (K)), and one has P = ([a ; a ] \ fa : x 2 supp g) v; 1 i j j ([b ; b ] \ fb : x 2 supp g) i +1 i j j 1 2 ([c ; c ] \ fc : x 2 supp g) : i +1 i j j 2 3 4 5 3 2 For example, if v = (3; 4; 6) and = x x x x x x , then P = fa ; a g fb g fc ; c g: 1 7 v; 1 3 4 5 6 3 4 5 6 P+d1 When I = I(M ) for M strongly stable, then is a monomial in the variables x , but here one must be slightly more careful because I is not a squarefree monomial ideal. This means that the multiplicities of the variables x in become relevant, not just which variables x occur in its support. De ne m (v) to be the multiplicity of the entry j among the rst k coordinates of (i ; i ; i ); this means that m (v) = 0 for any value j. 1 2 3 Then de ne subsets m (v)+1 S (v; ) = fa : x divides g 1 j m (v)+1 S (v; ) = fb : x divides g 2 j m (v)+1 S (v; ) = fc : x divides g 3 j One can then check that P is the specialization of the corresponding box P in the v; v; complex resolving I(F (M )), where P = ([a ; a ] \ S (v; )) ([b ; b ] \ S (v; )) ([c ; c ] \ S (v; )) : v; 1 i 1 i i 2 i i 3 1 1 2 2 3 For example, if v = (3; 3; 4) then m (v) = 2. This implies that 2 3 7 2 if = x x x x then P = fa ; a g fb g fc ; c g; v; 1 3 3 3 4 1 3 4 5 2 2 7 2 if = x x x x then P = fa ; a g fb g fc g: v; 1 3 3 4 1 3 4 5 Proof of Claim (b): If v is not the only vertex of C , then because v is Gale-maximal, without loss of generality we may assume that there is another vertex v of C which lies strictly below v in the Gale ordering: take any other vertex w 6= v of C and Proposition 3.2(ii) implies that v := v ^ w has the desired property. the electronic journal of combinatorics 16(2) (2009), #R3 38 Now suppose for the sake of contradiction that the unique facet P of C containing v; v which was exhibited above is zero-dimensional. This means that the box P = X v; 1 X has each \side" X of the box of cardinality jX j = 1. Looking at the descriptions d m m of P above for each of the ideals I(F ); I(K); I(F (K)); I(M ); I(F (M ), one can argue by v; induction on m that v = (i ; : : : ; i ) 1 d 0 0 0 v = (i ; : : : ; i ) 1 d must be equal in their rst m coordinates for m = 1; 2; : : : ; d, using the facts that v Gale v 0 v, that x divides , and that jX j = 1. Hence v = v, a contradiction. We deduce from this the explicit graded Betti numbers of the ideals I(F ); I(K), I(F (K)); I(M ); I(F (M )) in the above setting. The answers for I(M ); I(K) agree with the results of Eliahou and Kervaire [15] and Aramova, Herzog, and Hibi [1]. The answers for I(F ) generalize Corollary 2.17. Corollary 3.14 If K is a squarefree strongly stable d-uniform hypergraph, and M = depol(K), then all four ideals I = I(K); I(F (K)); I(M ); I(F (M )) have (I) = 0 unless i;j j = i + d and max S d (I) = (I) = i i;i+d S2K k d = (K) kd where (K) := jfS 2 K : max(S) = kgj. If F is a d-partite Ferrers d-uniform hypergraph then (I(F )) = 0 unless j = i + d i;j and i d (I(F )) = (I(F )) = i i;i+d (i ;:::;i )2F k d = (K) kd where (K) := jf(i ; : : : ; i ) 2 F : i = kg. k 1 d j Proof. Theorem 3.13 tells us that all four I = I(K); I(F (K)); I(M ); I(F (M )) have the same graded Betti numbers (I), which vanish unless j = i + d. Furthermore, i;j given a subset of positive integers X, it tells us that the multigraded Betti number (I(K)) is the number of boxes X X inside F (K) giving a decompo- jX jd;X 1 d sition X = X t t X . 1 d Classify these boxes according to their set of maxima S := f max X < < max X g 1 d = f i < < i g 2 K: 1 d the electronic journal of combinatorics 16(2) (2009), #R3 39 Given any set S = fi < < i g 2 K, such a box and decomposition X = X t t X 1 d 1 d exists if and only if S X [max X] := f1; 2; : : : ; max Xg; namely one has the unique decomposition in which X := fi + 1; i + 2; : : : ; i 1; i g \ X j j1 j1 j j j[max S]nSj with the convention that i := 0. Thus for each set S 2 K there are = max(S)d sets X with S X, jXj = i + d, and max(X) = max(S). For each such set X, the nely graded Betti number (I) contributes 1 to (I)(= (I)). This gives the i;X i;i+d i rst formula for (I(K)); the second follows immediately from the rst. Similarly, the rst formula for (I(F )) when F is a Ferrers hypergraph comes from classifying the boxes X X inside F according to their maxima 1 d (max X ; : : : ; max X ) = (i ; : : : ; i ) 2 F: 1 d 1 d The second formula then follows from the rst. Remark 3.15 It would be desirable to extend Theorem 3.13 to deal with the stable ideals considered by Eliahou and Kervaire [15] and squarefree stable ideals considered by Aramova, Herzog, and Hibi [1], which are somewhat less restrictive than their strongly stable counterparts. However, in both cases the issue of how one should construct the polarization I(F (K)) from I(K) becomes trickier. The following example shows that the construction used in Theorem 3.13 does not directly generalize { new ideas are needed. Example 3.16 Consider the ideal I = (x x ; x x ; x x ; x x ). It is squarefree stable, 1 2 1 3 2 3 2 4 but not squarefree strongly stable. If blindly applied, the method of Theorem 3.13 would associate to I a 1-dimensional cell complex (its complex of boxes). However, this complex cannot support a cellular resolution for I (minimal or otherwise), since I has projective dimension 2. 4 PART III: Instances of Question 1.1 and Conjec- ture 1.2 4.1 Armative answers for Question 1.1 The next three propositions are oered as evidence that many monomial ideals obey the colex lower bound. Given a d-uniform hypergraph K , let C denote the unique colexsegment d-uniform hypergraph having the same cardinality. Proposition 4.1 For any squarefree strongly stable d-uniform hypergraph K or P+d1 any strong stable collection M , all of the ideals I(K); I(F (K)); I(M ); I(F (M )) obey the colex lower bound. the electronic journal of combinatorics 16(2) (2009), #R3 40 Proof. By the depolarization bijection, one may assume that M = depol(K). Then Corollary 3.14 implies that all of these ideals have the same Betti numbers (I), namely kd (I) = (K) . Since C also has I(C ) squarefree strongly stable, its Betti i k K K S2K numbers obey a similar formula. However, (K) (C ) for all k by de nition of k k K and due to the fact that the colexicographic ordering on is an extension of the preordering by maxima. Proposition 4.2 Any Ferrers d-partite d-uniform hypergraph F obeys the colex lower bound. Proof. By Corollary 3.14, it suces to show that (F ) (C ) for all k. Note that the k k F map sending vectors (i ; : : : ; i ) 2 P to their partial sums (i ; i + i ; i + i + i ; ; i + 1 d 1 1 2 1 2 3 1 d P i + + i ) is a bijection P ! with the property that it sends the distinct elements 2 d of F which are counted by (F ) to distinct subsets S in having max(S) = k. Since C is an initial segment in a linear ordering on that extends the partial ordering by max(S), this forces (F ) (C ). k k F The proof of the following proposition uses an independent result (Corollary 4.19) about Conjecture 1.2. Proposition 4.3 For any shifted skew diagram D and any linearly ordered subsets X; Y , bip nonbip both the bipartite graph G (D) and the nonbipartite graph G (D) obey the colex X;Y X lower bound. nonbip Proof. There are several reductions. By Theorem 2.20, one can replace G (D) bip by G (D), and hence it suces to prove the assertion only for the bipartite graphs X;X bip G (D). But then Corollary 4.19 implies it suces to prove it only for row-nested bi- X;Y partite graphs. However row-nested bipartite graphs are exactly the bipartite graphs isomorphic to Ferrers graphs so it suces to prove it for Ferrers graphs. But these are Ferrers hypergraphs with d = 2, and hence the result follows from Proposition 4.2. Remark 4.4 The proofs of Propositions 4.1 and 4.2 reveal the important properties of the colexico- graphic ordering used to de ne the colexsegment hypergraph C : colex is a linear order with a minimum element, and all intervals nite, that extends the Gale ordering, and which is weaker than the (total) preordering by maxima on . If one replaces the colex ordering with any ordering on having these properties in de ning C , the proofs of the previous three propositions are still valid. Remark 4.5 As with Conjecture 4.9 below, there is an easy upper bound that comes from the Taylor jKj resolution of I(K) namely (I(K)) . For d = 2 (the graph case) equality is i+1 achieved in this upper bound if and only if the graph has every connected component of G a star, by Proposition 4.13 below. the electronic journal of combinatorics 16(2) (2009), #R3 41 Remark 4.6 It is not true that every monomial ideal generated in a single degree obeys the colex lower bound. For example, consider the edge ideal I of a 5-cycle. It is a Gorenstein ideal with total Betti numbers ( ; ; ) = (5; 5; 1). These are smaller than the total Betti 0 1 2 numbers ( ; ; ) = (5; 6; 2) of the corresponding colexsegment-generated ideal J . In 0 1 2 fact, it is not too dicult to show that I has the smallest total Betti numbers among all homogeneous (not necessarily monomial) ideals that are minimally generated by 5 quadrics. Remark 4.7 Question 1.1 invites comparison with Conjecture 4.3 of Aramova, Herzog, and Hibi [1], in which the Betti numbers of a squarefree monomial ideal are conjectured to be bounded above by the unique lexsegment ideal having the same Hilbert function (rather then bounded below by the unique colexsegment ideal having the same number of minimal generators). Note that this conjecture is true if the ground eld has characteristic zero by [2, Theorem 2.9]. 4.2 Evidence for Conjecture 1.2 and its re nement Here we present a more precise version of Conjecture 1.2, incorporating an upper bound to go with the lower bound, and characterizing when equality occurs for each. In the sections following, we are able to prove the upper bound, which is not hard via the Taylor resolution (Section 4.3). the characterization for the case of equality both in the lower and in the upper bounds (Sections 4.3, 4.4, 4.5). bip the whole conjecture is valid for graphs of the form G (D) (Section 4.6). X;Y We begin by de ning the four classes of graphs that appear as the extreme cases in the conjecture: row-nested (the lower bound), nearly-row-nested (the case of equality in the lower bound), horizontal (the upper bound), and horizontal-vertical (the case of equality in the upper bound). De nition 4.8 Given a bipartite graph G on bipartite vertex set X t Y with edge set E(G), we will often refer to its associated diagram D := f(x; y) : fx; yg 2 E(G)g X Y This motivates the following terminology. De ne for each vertex x 2 X its row R of G or D as follows: R := fy 2 Y : fx; yg 2 E(G)g: In other words, these are the neighboring vertices to x in G. Similarly de ne for vertices y 2 Y the column C in G or D. the electronic journal of combinatorics 16(2) (2009), #R3 42 Say that G is row-nested if the collection of rows fR g is linearly ordered by x x2X 0 0 0 inclusion, that is, if jR j jR j then R R . In particular, if jR j = jR j then x x x x x x R = R 0 . x x 0 0 Say G is nearly-row-nested if jR j < jR j implies R R and for each cardinality x x x x c 0, one has R 2 fc 1; cg: x:jR j=c In other words, rows of dierent cardinalities are nested, while all the rows of a given cardinality c are either all the same or have a common intersection of cocardinality 1. Say G is horizontal if every square in its associated diagram D is the unique square within its column. Say G is horizontal-vertical if every square in its associated diagram D is either the unique square within its column or the unique square within its row, or both. Lastly, de ne (I(G)) := (I(G)): i;X; i;XtY Y Y In other words, these are the nely graded Betti numbers of I(G) with respect to the specialized multigrading in which all the Y variables have degree 0. It is not hard to see that if G is any bipartite graph on vertices X t Y , there is up to 0 0 isomorphism, a unique row-nested bipartite graph R on XtY for some Y with the same row sizes R = (R ) (= deg (x)) for all x 2 X. Similarly, there is up to isomorphism a x G x unique horizontal graph H with the same row sizes as G. Here is the more precise version of Conjecture 1.2. Conjecture 4.9 For any bipartite graph G on vertex set X t Y , let R be the unique (up to isomorphism) row-nested graph with the same row sizes/X-degrees, and H the unique (up to isomorphism) horizontal graph with with the same row sizes/X-degrees. Then for all i and all X X one has 0 0 0 (I(R )) (I(G)) (I(H )) i;X ; G i;X ; i;X ; G k k ( ) (4.1) mindeg(X ) if jX j < i + 2 0 j deg(X )j ijX j+2 i+1 0 otherwise: where 0 0 mindeg(X ) := minfdeg (x) : x 2 X g; and j deg(X )j := deg (x): x2X Furthermore, equality occurs for all i and all X in the lower (resp. upper) bound, that is, in the rst (resp. second) inequality of (4.1), if and only if G is nearly-row-nested (resp. horizontal-vertical). the electronic journal of combinatorics 16(2) (2009), #R3 43 0 0 The binomial coecient expressions for (I(R )) and (I(H )), the Betti i;X ; G i;X ; G numbers that appear in (4.1) as lower and upper bounds, are easily explained. For the upper bound, it will be shown in Proposition 4.13 below that a bipartite graph H is horizontal-vertical if and only if the Taylor resolution for I(H) is minimal, and from this the given formula for 0 (I(H )) follows immediately. For the lower bound, it is easy i;X ; G to see that a graph R is row-nested if and only if it is isomorphic to the Ferrers bipartite graphs considered in Section 2.6, and then Proposition 2.17 gives the formula about the Betti numbers of R . Remark 4.10 We wish to compare Conjecture 4.9 to the Gale-Ryser Theorem from graph theory: Theorem 4.11 (Gale-Ryser) A pair of weakly decreasing nonnegative integer sequences X Y (d ; d ) having the same sum are the X-degrees and Y -degrees of some bipartite graph G Y T on vertex set X t Y if and only if the conjugate partition (d ) majorizes d , that is, X X Y T Y T d + + d (d ) + + (d ) 1 ` 1 ` Y T for all `. The equality (d ) = d holds if and only if the associated graph G is row-nested, that is, a Ferrers graph. The two results share some similarities. Both state an inequality valid for all bipartite graphs, with the case of equality achieved by row-nested/Ferrers graphs. For each xed X-degree sequence d , one can regard the Gale-Ryser Theorem as characterizing which Y X Y -degree sequences d are compatible with d , while Conjecture 4.9 says something about m X which Z -graded Betti numbers 0 are compatible with d . i;X ; Before proving various parts of this conjecture, we pause to give some useful charac- terization of the various classes of bipartite graphs G just de ned, in terms of avoidance of 0 0 certain vertex-induced subgraphs G of G, up to isomorphism. We equivalently phrase X tY bip them also in terms of the diagram D for G avoiding certain subdiagrams D , up to X;Y relabelling the elements of X and of Y . Proposition 4.12 Let G be a bipartite graph on vertex set XtY , with associated diagram D X Y . 0 0 (i) G is row-nested if and only if G avoids G isomorphic to two disjoint edges. X tY bip Equivalently, D avoids subdiagrams D of the form 0 0 X ;Y 0 0 (ii) G is nearly row-nested if and only if G avoids G isomorphic to a 6-cycle or X tY isomorphic to the disjoint union of an edge with a path having two edges and both the electronic journal of combinatorics 16(2) (2009), #R3 44 bip endpoints in Y . Equivalently, D avoids subdiagrams D of the form 0 0 X ;Y or (iii) G is horizontal if and only if G avoids G 0 0 isomorphic to a path with two edges X tY bip and both endpoints in X. Equivalently, D avoids subdiagrams D of the form 0 0 X ;Y (iv) G is horizontal-vertical if and only if G avoids G 0 0 isomorphic to a path with X tY bip three edges or a 4-cycle. Equivalently, D avoids subdiagrams D of the form 0 0 X ;Y or Proof. For each of the four assertions, the forward implication is easy. It is the backward implications that require proof, which we give here. (iii): Obvious. (i): Assume G is not row-nested. Then there exist two rows R ; R which are not x x 1 2 nested, that is, there exist y 2 R n R and y 2 R n R . But then G is 1 x x 2 x x fx ;x g;fy ;y g 1 2 2 1 1 2 1 2 the disjoint union of the two edges fx ; y g; fx ; y g. 1 1 2 2 (iv): Assume G is not horizontal-vertical. Then there exists a cell (x ; y ) in its diagram 1 1 that is neither the unique square within its row nor within its column. Hence there exist cells of the form (x ; y ); (x ; y ) in the diagram, and G will be a path with 1 2 2 2 fx ;x g;fy ;y g 1 2 1 2 two edges or a 4-cycle, depending upon whether the cell (x ; y ) is absent or present in 2 2 the diagram. (ii): Assume G is not nearly row-nested. Case 1. There exist two non-nested rows R ; R of unequal sizes, say jR j > jR j. x x x x 1 2 1 2 Then there exist y ; y 2 R n R and y 2 R n R . Hence G is the 1 2 x x 3 x x fx ;x g;fy ;y ;y g 1 2 2 1 1 2 1 2 3 disjoint union of the edge fx ; y g and the path fx ; y g; fx ; y g having two endpoints in 2 3 1 1 1 2 Y . Case 2. There do not exist two non-nested rows R ; R of unequal size. x x 1 2 Then there must exist a cardinality c for which R c 2. x:jR j=c Subcase 2a. There is a pair of rows R ; R both of cardinality c with jR \ R j c 2. x x x x 1 2 1 2 Then there exist y ; y ; y having the same properties as in Case 1 above. 1 2 3 Subcase 2b. Every pair of unequal rows R 6= R both of cardinality c has jR \ R j = x x x x 1 2 1 2 c 1. Start with two unequal rows R 6= R both of cardinality c. Since they are unequal x x 1 2 and of the same cardinality, one can nd y 2 R n R ; y 2 R n R . Now pick a third row 1 2 1 2 1 2 the electronic journal of combinatorics 16(2) (2009), #R3 45 R of the same cardinality with the property that there exists y 2 R \R but y 62 R ; x 3 x x 3 x 3 1 2 3 this must exist since R c 2. We claim that this forces x 2 R , since x 1 x x:jR j=c jR \ R j = c 1, and it similarly forces x 2 R . But this means G is x x 2 x fx ;x ;x g;fy ;y ;y g 1 3 3 1 2 3 1 2 3 a 6-cycle. 4.3 Proof of the upper bound and the case of equality The upper bound in Conjecture 4.9 follows from the Taylor resolution for a monomial ideal I that was recalled in Example 3.10. Since T (S=I) is a (not necessarily minimal) free S-resolution for S=I, the number of basis elements in T (S=I) of multidegree m always gives an upper bound on the Betti number (S=I) = 0, and this bound is tight for all i;m m if and only if T (S=I) is a minimal free resolution. For a graph G one can easily characterize when the Taylor resolution for I(G) is minimal. Say that a graph is a star if it is a tree with at most one vertex of degree larger than 1. Proposition 4.13 A graph G has the Taylor resolution T (S=I(G)) minimal if and only if every connected component of G is a star. Hence a bipartite graph G has the Taylor resolution T (S=I(G)) minimal if and only if G is horizontal-vertical. Proof. If every connected component of G is a star then the Taylor resolution is minimal, as all the least common multiples m are distinct for dierent subsets A: every generating monomial m = x x contains a variable x or x corresponding to a vertex of degree one, i j i j which is therefore contained in no other generating monomial. Conversely, suppose a graph G has its Taylor resolution minimal. Then for any subset X of its vertices, the vertex-induced subgraph G must also have its Taylor resolution T (S=I(G )) minimal, as it is a subcomplex of the Taylor resolution for I(G). This means that G must avoid as a vertex-induced subgraph G having a 3-cycle, a 4-cycle, or path with 3 edges, since one can do a small calculation of the Taylor resolution for each, and nd that none of them are minimal. We claim that this forces G to have no cycles { if not, it would contain some cycle of minimum length, which would either be of length 3, or of length 4, or of length at least 5 and hence contain a vertex-induced path with 3 edges. Hence G must be a forest, and its component trees must all have diameter 2, in order to avoid the path with 3 edges. Thus each component is a star. Corollary 4.14 The upper bound inequality 0 0 (I(G)) (I(H )) i;X ; i;X ; G the electronic journal of combinatorics 16(2) (2009), #R3 46 asserted by Conjecture 4.9 is valid. Furthermore, equality is achieved if and only if G is horizontal-vertical, as asserted by Conjecture 4.9. Proof. Let S = k[x; y], and compare the Taylor resolutions T (S=I(G)) and T (S=I(H )). Note that when one only looks at the X-multidegrees, setting the Y -multidegrees to 0, the two resolutions have exactly the same number of basis elements in each X-multidegree. The former is a resolution for S=I(G), and hence provides an upper bound on its Betti numbers, while the latter is a minimal free resolution for S=I(H ) by Proposition 4.13. This proves the asserted upper bound. In the case of equality, it follows that a minimal free resolution of S=I has the ranks G i of the free modules in the resolution equal to the ranks that occur in the Taylor resolution T (S=I(G)). Hence this Taylor resolution is minimal, and thus by Proposition 4.13, G is horizontal-vertical. 4.4 Two general reductions in the lower bound Here we give two reductions that may apply to a bipartite graph when one is attempting to verify the lower bound in Conjecture 4.9. Both will be used in the next section to verify the case of equality conjectured for the lower bound. Say that a bipartite graph G on vertex set X t Y , or its diagram D, has the vertex x 2 X (resp. y 2 Y ) as a full row (resp. column) if E(G) contains all of fxg Y (resp. X fyg). Say that x; x 2 X index nested rows if R R . x x The following two results allow one to remove full columns and/or rows, and remove nested rows, when considering a minimal counterexample to Conjecture 4.9. Proposition 4.15 Let G be a bipartite graph on vertex set X t Y . If G has y 2 Y as a full column, one has for all i and all X X that 0 (I(G)) = 0 + 0 (I(G n fyg)) + 0 (I(G n fyg)); i;X ; i;jX j1 i;X ; i1;X ; where Gnfyg denotes the vertex-induced subgraph of G on X t (Y nfyg), and denotes i;j the Kronecker delta function. Consequently, in this situation, G achieves equality in the lower bound of Conjec- ture 4.9 if and only if G n fyg does. Proof. The idea is to compare the most nely graded Betti numbers 0 0 for I(G) i;X tY versus I(G n fyg). If y 62 Y , clearly G 0 0 = (Gnfyg) 0 0, so that 0 0(I(G)) = 0 0 (I(Gnfyg)): X tY X tY i;X tY i;X tY 0 0 0 0 0 0 Furthermore, if y 62 Y and Y 6= ? then (G ) is obtained from (G ) X t(Y tfyg) X tY simply by adding in the vertex y as the apex of a cone over the base simplex having vertex 0 0 set Y . Hence the two complexes are homotopy equivalent, and (I(G)) = i;X t(Y tfyg) 0 0 (I(G n fyg)): i1;X tY Lastly, note that (I(G)) = 1 for i = jX j 1 and 0 for all other i. i;X ;fyg Since 0 (I(G)) = 0 0 (I(G)), the formula in the proposition follows. i;X ; i;X tY Y Y The second assertion is a consequence of the formula, as R will have a full column whenever G does. the electronic journal of combinatorics 16(2) (2009), #R3 47 Proposition 4.16 Let G be a bipartite graph on vertex set X t Y with two nested rows R R . Then x x 2 1 (I(G)) = (I(G n fx g)) i;X; i1;Xnfx g; 1 for all i. Consequently, if Conjecture 4.9 holds for all bipartite graphs with smaller jXj, it will also hold for G. Proof. For the rst assertion, introduce the ideal I(G) + (x ). Although this ideal is no longer quadratic, it is still generated by squarefree monomials, and hence is the Stanley- Reisner ideal for a simplicial complex on this vertex set X t Y . This complex is the simplicial complex of I(Gnfx g) with x still considered as an element of the ground set. 1 1 Hochster's formula (Proposition 2.7) shows that (I(G n fx g)) = (I(G) + (x )): i1;Xnfx g; 1 i;X; 1 Hence it only remains to show that (I(G)) = (I(G) + (x )): (4.2) i;X; i;X; 1 Letting S := k[x; y], one can relate the Betti numbers of I(G) + (x ) and of I(G) via the long exact sequence in Tor (; k) associated to the short exact sequence of S-modules 0 ! S=(I(G) : x )( deg x ) ! S=I(G) ! S=(I(G) + (x )) ! 0 1 1 1 where (I(G) : x ) := ff 2 k[x; y] : f x 2 I(G)g 1 1 denotes the usual ideal quotient (or colon ideal). The ideal (I(G) : x ) is also not quadratic, but is still generated by squarefree monomials, with unique minimal monomial generating set given by fy : fx ; y g 2 E(G)g t fx y : fx ; y g 2 E(G) with x 6= x and fx ; y g 62 E(G)g: j 1 j i j i j i 1 1 j (4.3) Note that x 2 X does not appear among any of these minimal generators for (I(G) : x ), 2 1 because every edge of the form fx ; y g 2 E(G) also has fx ; y g 2 E(G). Therefore 2 j 1 j the nely graded component corresponding to X does not appear in the minimal free resolution for (I(G) : x ), and hence (I(G) : x ) = (S=I(G) : x ) = 0 for all i: i;X; 1 i1;X; 1 Therefore the desired relation (4.2) follows from the aforementioned long exact sequence. For the second assertion, note that the hypothesis on G implies that the row-nested graph R will also have rows (R ) (R ) nested in the same way, and hence the G G x G x 2 1 formula in the proposition holds for R also. The rest is straightforward. the electronic journal of combinatorics 16(2) (2009), #R3 48 4.5 The case of equality in the lower bound Although we do not know how to prove the lower bound in Conjecture 4.9 in general, we prove here its assertion about when equality is achieved. Theorem 4.17 Let G be a bipartite graph on vertex set X t Y , and R the unique (up to isomorphism) row-nested graph having the same row sizes/X-degrees. Then for all i and all X X one has ( )! mindeg(X ) if jX j < i + 2 ijX j+2 0 0 (I(G)) = (I(R )) = i;X ; i;X ; G 0 otherwise: if and only if G is nearly row-nested. Proof. The forward implication. Note that if G is not nearly row-nested, then Proposition 4.12(ii) shows that G contains some vertex-induced subgraph G 0 0 isomorphic to either the disjoint of an edge with a X ;Y path of two edges having both endpoints in Y , or a 6-cycle. In the rst case, consider the subdiagrams for R and G restricted to the two rows X = fx ; x g, which will have sizes jR j = a; jR j = b and, say, a b. In R , these two 1 2 x x G 1 2 rows are nested, while in G they overlap in c columns where a c 2. One calculates 0 (I(R )) = = b 1;X ; G 1 2 + 2 by the formula in the statement of the theorem. Meanwhile, we argue using Corollary 2.15 that (I(G)) c + (a c)(b c): 1;X ; 0 0 This is because one has (I(G)) = 1 for 1;X tY any of the c choices of Y equal to a single column in the overlap of the two rows, and any of the (a c)(b c) choices of Y having two columns of size one. But then the fact that a c 2 implies 0 0 (I(G)) c + (a c)(b c) > b = (I(R )): 1;X ; 1;X ; G In the second case, we may assume that the former subgraphs G 0 0 do not exist in G, X ;Y but a 6-cycle G does exist. The proof of Proposition 4.12(ii) showed that fx ;x ;x g;fy ;y ;y g 1 2 3 1 2 3 in this situation, the subgraph G will have every y of Y n fy ; y ; y g giving a fx ;x ;x g;Y 1 2 3 1 2 3 full column. Hence by Proposition 4.15, it suces to remove these full columns and show the electronic journal of combinatorics 16(2) (2009), #R3 49 that a 6-cycle G does not achieve the lower bound in the conjecture. For this, observe that a 6-cycle G has (I(R )) = = 1 3;X ; G 3 3 + 2 0 0 0 < 2 = dim H ((I(G))) = (I(G)) (I(G)): k 1 3;X ;Y 3;X ; Here the calculation H ((I(G))) k comes from direct inspection: if the 6-cycle G has edges E(G) = fx ; y g , then (I(G)) consists of two trian- i j 1i6=j3 fx ;x ;x g;fy ;y ;y g 1 2 3 1 2 3 gles fx ; x ; x g; fy ; y ; y g together with the three edges fx ; y g connecting them, 1 2 3 1 2 3 i i i=1;2;3 and is homotopy equivalent to a wedge of two circles. The reverse implication. Assume that G is a nearly row-nested bipartite graph on X t Y , and one must show that 0 (I(G)) = 0 (I(R )) for all i and all X X. Proceed by induction on i;X ; i;X ; G jXj + jY j. By the reductions in Propositions 4.16 and 4.15 one may assume that G contains no nested pair of rows, and that it contains no full columns. Because G is nearly row-nested, containing no nested pair of rows implies all the rows R have the same cardinality c. Containing no full columns then forces c = 1. But in this case, both G and R are horizontal-vertical, having their Taylor resolutions minimal by Proposition 4.13, and 1 if i = jX j 1 0 0 (I(G)) = (I(R )) = i;X ; i;X ; G 0 otherwise. Note that the above result gives a characterization of nearly row-nested graphs by means of its Betti numbers 0 . In this sense it is analogous to the characterization of i;X ; Ferrers graphs as the bipartite graphs whose minimal free resolutions are linear (see [10, Theorem 4.2]). bip 4.6 Verifying the bipartite conjecture for D X;Y Having already veri ed the upper bound and the cases of equality for the upper and lower bounds in Conjecture 4.9 generally, we verify here that the lower bound holds for the bip bipartite graphs D , using Corollary 2.15. The crux is the following lemma. X;Y Lemma 4.18 Let D be a shifted skew diagram, and X; Y linearly ordered subsets. bip bip If D has no empty rows, then there exists a subset Y Y for which D is X;Y X;Y bip spherical and rect(D ) = jY j. X;Y bip More generally, if D has at least k cells in every row, then for every j in the range X;Y k bip 1 j k, there are at least dierent choices of subsets Y Y for which D is X;Y bip spherical and rect(D ) = jY j j + 1. X;Y the electronic journal of combinatorics 16(2) (2009), #R3 50 0 0 Proof. For the rst assertion, one can give an algorithm to nd Y . Initialize Y to be bip empty. Without loss of generality one can assume that D has only one cell in its rst X;Y row{ simply remove all columns of Y that intersect the top row except for the longest bip such column, and one will still have no empty rows in D . Add to Y the index y of X;Y bip this unique column intersecting the top row, which is now the rightmost column of D . X;Y bip Note also that D has a rectangular decomposition that begins with the full rectangle X;Y having this single column y . As in the algorithm for rectangular decomposition, replace bip D with its restriction to the rows and columns disjoint from this rst full rectangle, X;Y which is again a diagram with no empty rows by construction, and repeat the process until X is empty. For the second assertion, one nds dierent sets Y by a similar algorithm. Initialize bip Y to be empty. Without loss of generality one can assume that D has exactly k cells X;Y in its rst row{ simply remove all columns of Y that intersect the top row except for the longest k of them, and this will preserve the property of every row having at least k cells. For each j-element subset Y of these k columns that intersect the top row, add Y to Y , 0 0 bip 0 0 and we will continue the the algorithm to produce a Y for which D has jY j j + 1 full X;Y rectangles in its rectangular decomposition. As a rst step, remove the other kj columns bip that intersect the top row from Y , and note that D has a rectangular decomposition X;Y that begins with a full rectangle containing exactly the j columns that intersect the top row. Furthermore, the hypothesis that each row has at least k cells ensures that, after bip replacing D with its restriction to the rows and columns disjoint from this rst full X;Y rectangle, one will have a diagram with no empty rows. Thus one can continue the algorithm from the proof of the rst assertion, adding in one more column to Y each time along with one more full rectangle in the rectangular decomposition. Repeating the process until X is empty, one obtains the desired Y . Corollary 4.19 For any shifted skew diagram D and linearly ordered subsets X; Y , Con- bip jecture 4.9 holds for G (D). X;Y 0 0 Proof. Let X X and let k := mindeg(X ). Then one must show that bip (I(G (D))) i;X ; X;Y i jX j + 2 for jX j < i + 2. bip 0 0 Without loss of generality, X = X. Let I := I(G (D)). Let j := i jX j + 2, so X;Y that 1 j k, and Lemma 4.18 implies that there are at least dierent Y Y for 0 0 0 which (I) = 1. In other words, (I) . Substituting jXj+jY j(jY jj)2;XtY jXj+j2;X; j := i jX j + 2 gives the desired lower bound. 5 EPILOGUE: Further questions We conclude with a few questions motivated by our results. The rst ones concern exten- sions of our results (such as Corollary 2.15, Theorem 2.20, Corollary 2.21, Theorem 3.13) the electronic journal of combinatorics 16(2) (2009), #R3 51 that give the Betti numbers or the explicit maps in the minimal free resolution of certain ideals. 0 0 Question 5.1 Let K K be two nested d-uniform hypergraphs with both I(K); I(K ) squarefree strongly stable, so that I(K n K ) is what we called earlier a skew squarefree strongly stable ideal. 0 0 (i) Are the multigraded Betti numbers for the ideals I(K n K ) and I(F (K n K )) independent of the eld k, as in Corollary 2.15? (ii) Is there a combinatorial recipe like the rectangular decomposition that allows one to compute them? 0 0 (iii) Are the Betti numbers for I(K n K ) obtained from those of I(F (K n K )) by specialization, as in Theorem 2.20, Corollary 2.21? (iv) Can an armative answer to questions (i), (ii), (iii) be given via cellular resolutions, as in Theorem 3.13? bip (v) Can one at least do (iv) in the case of I(G (D)) with D a shifted skew diagram? X;Y This would mean nding a regular CW-complex whose cells are indexed by the spherical subdiagrams of a given shifted skew diagram. Finally, we come back to lower bounds. Remark 5.2 Remark 4.6 still allows for the possibility that among the monomial ideals generated in one degree and with a xed number of minimal generators there is one ideal that has the smallest total Betti numbers. Is this at least true for ideals that are generated in degree two? If so, it would be very interesting to describe the ideals that attain the smallest Betti numbers. Question 5.3 Can one formulate a reasonable extension of Conjecture 1.2 that applies to squarefree monomial ideals generated in degrees d 2, presumably parametrized by d-uniform hypergraphs with some multipartiteness property? 6 Appendix 6.1 On the topological types of (I(G)) The goal is to observe that the simplical complexes (I(G)) associated to edge ideals I(G) of graphs G can have arbitrary homeomorphism type, and when G is bipartite they can have the homotopy type of an arbitrary suspension. The following is simply the well-known observation that the rst barycentric subdivi- sion of a simplicial complex (see e.g. [26, x15]) is always a ag (clique) complex, that is, of the form (I(G)). the electronic journal of combinatorics 16(2) (2009), #R3 52 Proposition 6.1 For any nite simplicial complex there exists some graph G with k(I(G))k homeomorphic to kk. Proof. Let G have vertex set V equal to the collection of all nonempty simplices of , and an edge between two of them if the corresponding simplices of are not included within one another. Then (I(G)) is the rst barycentric subdivision of , and hence their geometric relations are homeomorphic. In particular, this proposition implies the well-known fact that one can have torsion in the homology of (I(G)), and hence dependence of the Betti numbers (I(G)) on the choice of the eld coecients k. See Katzman [20] for some constraints on where this dependence can occur. Among bipartite graphs G, one does not achieve every homeomorphism type for (I(G)), and not even every homotopy type. However, it is easy to say exactly what homotopy types one can achieve, namely all suspensions. In particular, one can still have torsion in the homology of (I(G)) for bipartite G, and hence dependence of the Betti numbers (I(G)) on the choice of the eld coecients k. Proposition 6.2 For any nite bipartite graph G, the geometric realization k(I(G))k is homotopy equivalent to the suspension of the geometric realization kk of some nite simplicial complex . Conversely, for any nite simplicial complex , one can nd a bipartite graph G for which k(I(G))k is homotopy equivalent to the suspension of kk. Proof. Let G be a bipartite graph on vertex set X t Y . Let T be the geometric realization jXj+jY j of k(I(G))k in R where the vertices corresponding to X (resp. Y ) are sent to standard basis vectors in the rst jXj (resp. last jY j) coordinates, and simplices are jXj+jY j embedded piecewise-linearly with these vertices. De ne f : R ! R to be the linear map which sums the last jY j coordinates of the vector, so that f (T ) [0; 1]. One can write T = T [ T where X Y T := T \ f 0; T := T \ f ; 1 T \ T = T \ f X Y and note that there are straight-line homotopies that deformation retract T ; T onto the X Y 1 1 simplices X(= T \ f (0)) and Y (= T \ f (1)). Hence T ; T are contractible, and so X Y 1 1 their union T is homotopy equivalent to the suspension of their intersection T \ f ( ) by Lemma 6.3 below. This intersection comes equipped with a regular CW-decomposition having cells \ f : 2 (I(G)) : the electronic journal of combinatorics 16(2) (2009), #R3 53 Since every regular CW-complex is homeomorphic to a nite simplicial complex (e.g. its own barycentric subdivision), the rst assertion is proven. For the converse, start with a nite simplicial complex . Create a bipartite graph G on vertex X t Y , where X is the collection of vertices of and Y is the collection of facets of , with an edge fx; yg if x corresponds to a vertex of that does not lie on the facet of corresponding to y. It is not hard to see that the maximal simplices of (I(G)) (other 0 0 0 than X; Y ) are exactly the sets X t Y of the following form: Y = fF ; : : : ; F g 6= ? 1 r 0 0 indexes a collection of facets whose intersection F \ \ F is X , and X 6= ?. 1 r We claim that T := k(I(G))k has T \ T = T \ f ( ) homotopy equivalent to X Y kk, and hence T is homotopy equivalent to the suspension of kk by the rst part of the proof. To see the claim, one can exhibit good coverings (that is, ones in which all 1 1 intersections of the covering sets are either empty or contractible) of kk and of T \f ( ) that have isomorphic nerves. Cover kk by the simplices which are achieved as intersections F \ \F of nonempty 1 r collections of facets F . Since each facet F is itself such an intersection, this covers kk. Because intersections of simplices in a simplicial complex are always empty or other simplices, this is a good covering. 1 1 1 1 Cover T \ f ( ) by the polyhedral cells \ f ( ) as runs through all the sets 2 2 0 0 X t Y (described above) that give facets of (I(G)) other than X; Y . It is not hard to see that these cells intersect in the same fashion as their corresponding simplices 1 1 intersect, hence their intersections are always of the form \ f ( ) for some simplex 1 1 . Since this intersection set \ f ( ) is always empty or contractible, this is a good covering. The above analyses of intersections of the covering sets also shows that the nerves 1 1 of the two covers are identical. Hence the two spaces kk; T \ f ( ) that they cover are both homotopy equivalent to the nerve of the cover by the usual Nerve Lemma [5, Theorem 10.6]. 6.2 A wedge lemma The goal is here to state and prove the following commonly-used wedge lemma, whose special cases were used in two proofs above. Although it is well-known, and even a special case of a variation on a lemma of Bj orner, Wachs and Welker (alluded to in their [7, Lemma 7.1, Remark 7.2]), we include a proof for completeness. Lemma 6.3 Let X; Y be two subspaces of a topological space, and assume that the in- clusion maps X \ Y ,! X; Y are both co brations, and both homotopic to a constant map. Then the union X [ Y is homotopy equivalent to the wedge X _ Y _ (X \ Y ), where here denotes suspension. In the situations where we need this lemma, X \ Y; X; and Y are all subcomplexes of a CW -complex, and hence the co bration hypothesis always holds. Furthermore, we can take advantage of the fact that if Z ,! Z is an inclusion of a subcomplex Z in a the electronic journal of combinatorics 16(2) (2009), #R3 54 0 0 CW -complex Z , it is homotopic to a constant map if either Z or Z is contractible, a hypothesis that holds in the two special cases where we wish to apply the lemma: If X and Y are contractible, then X [ Y is homotopy equivalent to (X \ Y ) (used in the proof of Lemma 6.4 below). If X \ Y and Y are contractible, then X [ Y is homotopy equivalent to X (used in the proof of Proposition 6.2 above). Proof.(of Lemma 6.3; cf. proof of [7, Lemma 7.1]) The inclusions X \ Y ,! X; Y give rise to a diagram of spaces D over the 3-element poset Q that has two maximal elements corresponding to X; Y and one minimum element corresponding to X\Y . By [7, Corollary 2.4], the union X [ Y is homotopy equivalent to the homotopy colimit of this diagram hocolimD. On the other hand, there is another diagram of spaces E over the same poset Q in which the inclusions X \ Y ,! X; Y are replaced by the constant maps to which they are homotopic. Then [7, Lemma 2.1] implies that hocolimD and hocolimE are homotopy equivalent. Finally, [7, Lemma 2.2] implies that hocolimE is homotopy equivalent to X ^ Y ^ 0 0 (S (X \ Y )), where here S is a zero-sphere (that is, two disjoint points) and denotes the topological join. Since S (X \ Y ) = (X \ Y ), this completes the proof. The following topological lemma was an essential point in the proof of Theorem 3.13. Lemma 6.4 Let C be a polytopal complex and v a vertex in C that lies in a unique facet P , and assume that P has strictly positive dimension. Then the vertex-induced subcomplex C n fvg, obtained by deleting v and all faces that contain it, is homotopy equivalent to C. Proof. Let P be the unique facet of C containing v, and P n fvg the polytopal complex whose maximal faces are the codimension one faces of P not containing v. As topological spaces, one has C = (C n fvg) [ P P n fvg = (C n fvg) \ P: Since P is convex and hence contractible, it then suces by Lemma 6.3 to show that P n fvg is contractible. In fact, polytopal complexes of the form P n fvg are even known to be homeomorphic to a ball of dimension dim(P ) 1: one can nd a shelling order on the codimension one faces of P in which the maximal faces of P nfvg appear as an initial segment [6, Example 4.7.15 and Proposition 4.7.26(ii)] and [36, Corollary 8.13]. 6.3 A collapsing lemma The goal here is Lemma 6.8 below, which was used in Section 2.5 to show that excess cells in diagrams of shifted skew shapes can be removed without altering the homotopy type of their associated simplicial complexes. For this we rst recall a central notion from simple homotopy theory [9]. the electronic journal of combinatorics 16(2) (2009), #R3 55 0 De nition 6.5 Given two nested simplicial complexes , say that is obtained 0 0 from by an elementary collapse if = n fG; Fg where F is a facet (maximal face) of and G is subface of F that lies in no other faces of . It is not hard to see that this implies is a strong deformation retract of , and hence that they are homotopy equivalent. The notion of simple homotopy equivalence is the equivalence relation on simplicial complexes generated by the elementary relations whenever the two complexes are related by an elementary collapse. The following proposition is the straightforward observation that the operation of Alexander duality 7! from De nition 2.8 (anti-)commutes with elementary col- lapses; this was perhaps observed rst by Kahn, Saks and Sturtevant [22]. 0 0 Proposition 6.6 Let ; be two simplicial complexes on the same vertex set. Then _ 0 _ is obtained from by an elementary collapse if and only if is obtained from ( ) by an elementary collapse. We also recall here the simplest way in which a simplicial complex can be contractible, namely when it has a cone vertex. De nition 6.7 A vertex v in a simplicial complex is called a cone vertex v if every face F in either contains v or has v t F in . 0 0 Lemma 6.8 Let be a pair of nested simplicial complexes. Assume that is obtained from by adding one new facet F for which the intersection subcomplex 2 \ has a cone vertex. 0 0 Then there is a sequence of elementary collapses from down to , so that ; have the same (simple) homotopy type. _ 0 _ Furthermore, has the same (simple) homotopy type as ( ) . Proof. Let v be a cone vertex for the subcomplex 2 \. Order the subfaces F ; F ; : : : ; F 1 2 s of F not lying in that do not contain v, in any order from largest to smallest that respects the partial ordering by (reverse) inclusion. Then the following pairs of faces (G; F ) give a sequence of elementary collapses starting from : (F ; F [ fvg); (F ; F [ fvg); : : : ; (F ; F [ fvg): 1 1 2 2 s s The result at the end of these collapses is . _ 0 _ The assertion for and ( ) then follows from Proposition 6.6. 6.4 A polarization lemma The goal here is Lemma 6.9 about polarizations, which is well-known (e.g., cf. [25, Exercise 3.15]). However, we have stated it here in the form most convenient for our use, and included a proof for the sake of completeness. Let S be a polynomial algebra over a eld k, and I S a homogeneous ideal with respect to the standard Z-grading. Then I or S=I or any nitely generated S-module M the electronic journal of combinatorics 16(2) (2009), #R3 56 has a minimal free resolution F by free S-modules F . Minimality of such a resolution is equivalent to having all entries in the matrices de ning the maps be homogeneous of positive degree. Recall that the graded Betti number (M ) := dim Tor (M; k) is the k j i;j i same as the number of homogeneous basis elements of degree j in F for any such minimal free resolution F . Lemma 6.9 Let S be a polynomial algebra over a eld, and I a homogeneous ideal of S. Given in S a non-zero element of degree 1, let S := S=(), another polynomial algebra with standard grading. Set I := (I + ())=(), a homogeneous ideal of S. Then the following are equivalent: (i) Any minimal free resolution F for I as an S-module has the property that the spe- cialized complex F := S F in which one \mods out " gives a minimal free resolution for I as a S-module. S S (ii) (I) = (I) for all i; j. i;j i;j (iii) Hilb(S=I; t) = (1 t) Hilb(S=I; t): (iv) acts as a non-zero divisor on S=I. Proof. The implication (i) implies (ii) is clear. For (ii) implies (iii), recall that taking the Euler characteristic in each graded component of the minimal resolution F ! S ! S=I ! 0 gives i S j Hilb(S=I; t) := Hilb(S; t) (1) (S=I)t : i;j Since Hilb(S; t) = (1 t) Hilb(S; t), the assertion (iii) follows. For (iii) implies (iv), recall that for any S-module M , the exact sequence 0 ! Ann ()(1) ! M (1) ! M ! M=M ! 0 shows that Hilb(M=M; t) = (1 t) Hilb(M; t) + t Hilb(Ann (); t): Hence is a non-zero-divisor on M exactly when Hilb(M=M; t) = (1 t) Hilb(M; t). Apply this to M = S=I. For (iv) implies (i), rst argue the vanishing Tor (S=I; S=()) = 0 for i > 0 as follows. Since 6= 0 it is a non-zero-divisor on S, and one has the S-resolution 0 ! S(1) ! S ! S=() ! 0 for S=(), which one can tensor over S with S=I to obtain the complex 0 ! S=I(1) ! S=I ! S=(I + ()) ! 0: Taking homology (with the S=(I + ()) term omitted) computes the relevant Tor, and the vanishing follows because the assumption of (iv) implies this complex is exact. the electronic journal of combinatorics 16(2) (2009), #R3 57 Now note that since F ! S ! S=I ! 0 is a resolution of S=I, when one tensors over S with S to obtain F ! S ! S=(I + ()) ! 0; the homology of this complex (with the S=(I + ()) term omitted) will compute the same Tor. The vanishing result for Tor then implies this complex is exact. Hence F resolves I. In fact, it will be a minimal resolution because tensoring over S with S preserves the property that all matrix entries in the maps are of positive degree. References [1] A. Aramova, J. Herzog, and T. Hibi, Squarefree lexsegment ideals, Math. Z. 228 (1998), 353{378. [2] A. Aramova, J. Herzog, and T. Hibi, Shifting operations and graded Betti numbers, J. Algebraic Comb. 12 (2000), 207{222. [3] I. Anderson, Combinatorics of nite sets, Corrected reprint of the 1989 edition. Dover Publications, Mineola, NY, 2002. [4] A. M. Bigatti, Upper bounds for the Betti numbers of a given Hilbert function, Comm. Algebra 21 (1993), 2317{2334. [5] A. Bj orner, Topological methods, Handbook of combinatorics, Vol. 1, 2, 1819{1872, Elsevier, Amsterdam, 1995. [6] A. Bj orner, M. Las Vergnas, B. Sturmfels, N. White, G. M. Ziegler, Oriented ma- troids, Encyclopedia Math. Appl. 46. Cambridge University Press, Cambridge, 1993. [7] A. Bj orner, M. Wachs, and V. Welker, Poset ber theorems, Trans. Amer. Math. Soc. 357 (2005), 1877{1899. [8] M. Brun and T. R omer, Betti numbers of Z -graded modules, Comm. Algebra 32 (2004), 4589{4599. [9] M. M. Cohen, A course in simple-homotopy theory, Graduate Texts in Mathematics 10. Springer-Verlag, New York-Berlin, 1973. [10] A. Corso and U. Nagel, Monomial and toric ideals associated to Ferrers graphs, Trans. Amer. Math. Soc. 361 (2009), 1371{1395. [11] A. Corso and U. Nagel, Specializations of Ferrers ideals, J. Algebraic Comb. 28 (2008), 425{437. [12] K. Ding, Rook placements and classi cation of partition varieties BnM , Commun. Contemp. Math. 3 (2001), 495{500. [13] C. Dodd, A. Marks, V. Meyerson, and B. Richert, Minimal Betti numbers, Comm. Algebra 35 (2007), 759{772. [14] A. M. Duval, A relative Laplacian spectral recursion, Electron. J. Combin. 11(2) (2006), #R26. [15] S. Eliahou and M. Kervaire, Minimal resolutions of some monomial ideals, J. Algebra 129 (1990), 1{25. the electronic journal of combinatorics 16(2) (2009), #R3 58 [16] M. Go, Bounding betti numbers of bipartite graph ideals, arXiv preprint math.AC/0807.1540. [17] J. Herzog, T. Hibi, Distributive lattices, bipartite graphs and Alexander duality, J. Algebraic Combin. 22 (2005), 289{302. [18] M. Hochster, Cohen-Macaulay rings, combinatorics, and simplicial complexes, in: Ring Theory II (Proc. Second Oklahoma Conference) (B.R. McDonald and R. Morris, eds.), Dekker, New York, 1977, pp. 171{223. [19] H. A. Hulett, Maximum Betti numbers of homogeneous ideals with a given Hilbert function, Comm. Algebra 21 (1993), 2335{2350. [20] M. Katzman, Characteristic-independence of Betti numbers of graph ideals, J. Com- bin. Theory Ser. A 113 (2006), 435-454. [21] C. Klivans and V. Reiner, Shifted set families, degree sequences, and plethysm, Elec- tron. J. Combin. 15 (2008), #R14, 35 pp. [22] J. Kahn, M. Saks, and D. Sturtevant, A topological approach to evasiveness, Combi- natorica 4 (1984), 297{306. [23] I.G. Macdonald, Symmetric functions and Hall polynomials, 2nd edition, Oxford University Press, New York, 1995. [24] N.V.R. Mahadev and U.N. Peled, Threshold graphs and related topics. Annals of Discrete Mathematics 56. North-Holland, Amsterdam, 1995 [25] E. Miller and B. Sturmfels, Combinatorial commutative algebra, Graduate Texts in Mathematics 227. Springer-Verlag, New York, 2005. [26] J.R. Munkres, Elements of algebraic topology, Addison-Wesley, Menlo Park, CA, 1984. [27] K. Pardue, Deformation classes of graded modules and maximal Betti numbers Illinois J. Math. 40 (1996), 564{585. [28] T. R omer, Bounds for Betti numbers, J. Algebra 249 (2002), 20{37. [29] H. G. Ryser, Combinatorial mathematics, Carus Mathematical Monographs 14, John Wiley and Sons, New York, 1963. [30] A. Sinefakopoulos, On Borel xed ideals generated in one degree, J. Algebra 319 (2008), 2739{2760. [31] R. Stanley, Combinatorics and Commutative Algebra, Second Ed., Progress in Math- ematics 41. Birkh auser, Boston, MA, 1996. [32] D. Taylor, Ideals generated by monomials in an R-sequence, Ph.D. Thesis, University of Chicago, 1960. [33] M. Velasco, Minimal free resolutions that are not supported by a CW-complex, J. Algebra 319 (2008), 102{114. [34] D.B. West, Introduction to graph theory, Prentice Hall, Upper Saddle River, NJ, 1996. [35] G. W. Whitehead, Elements of homotopy theory, Graduate Texts in Mathematics 61. Springer-Verlag, New York, 1978. [36] G. M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics 152. Springer- Verlag, New York, 1995. the electronic journal of combinatorics 16(2) (2009), #R3 59
The Electronic Journal of Combinatorics – Unpaywall
Published: Feb 11, 2009
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.