Tuning the cytotoxic properties of new ruthenium(III) and ruthenium(II) complexes with a modified bis(arylimino)pyridine Schiff base ligand using bidentate pyridine-based ligands.

J Algebr Comb (2014) 39:783–806 DOI 10.1007/s10801-013-0467-4 Tropical decomposition of Young’s partition lattice Vivek Dhand Received: 20 December 2012 / Accepted: 1 August 2013 / Published online: 30 August 2013 © Springer Science+Business Media New York 2013 Abstract Young’s partition lattice L(m, n) consists of integer partitions having m parts where each part is at most n. Using methods from complex algebraic geometry, R. Stanley proved that this poset is rank-symmetric, unimodal, and strongly Sperner. Moreover, he conjectured that it has a symmetric chain decomposition, which is a stronger property. Despite many efforts, this conjecture has only been proved for min(m, n) ≤ 4. In this paper, we decompose L(m, n) into level sets for certain tropical polynomials derived from the secant varieties of the rational normal curve in projective space, and we find that the resulting subposets have an elementary raising and lowering algorithm. As a corollary, we obtain a symmetric chain decomposition for the subposet of L(m, n) consisting of “sufficiently generic” partitions. Keywords Young’s partition lattice · Hankel matrices · Tropical polynomials · Symmetric chain decomposition 1 Introduction 1.1 Stanley’s conjecture Young’s partition lattice L(m, n) is defined to be the poset of integer partitions λ = (0 ≤ λ1 ≤ · · · ≤ λm ≤ n) equipped with the following partial order: λ≤μ ⇐⇒ λi ≤ μ i for all 1 ≤ i ≤ m. We can visualize the elements of this poset as Young diagrams that fit in the bottom left-hand corner of an (m × n) rectangle, ordered by inclusion (Fig. 1). Note that L(m, n) is a ranked poset, where the rank of λ is given by λ1 + · · · + λm . B V. Dhand ( ) Boulder, CO, USA e-mail: vivek.dhand@gmail.com 784 J Algebr Comb (2014) 39:783–806 ••• ••• •• ••• •• •• • ••• • •• • • ••• •• • Fig. 1 The Hasse diagram of L(2, 3) This poset appears in different guises in several branches of mathematics. For example, it is isomorphic to the poset of Schubert cells in the Grassmannian of mplanes in Cm+n . In the groundbreaking paper [6], R. Stanley used the hard Lefschetz theorem to prove that L(m, n) is rank-symmetric, unimodal, and strongly Sperner. Furthermore, he conjectured that it has a symmetric chain decomposition, i.e. can be expressed as a disjoint union of rank-symmetric, saturated chains. A poset which has at least one symmetric chain decomposition is called a symmetric chain order. Despite many efforts, this conjecture has only been proved for min(m, n) ≤ 4 [2, 5, 9]. In fact, even the problem of finding an explicit matching between adjacent ranks of L(m, n) remains unsolved [4]. It is worth noting that K. O’Hara proved a weaker result by constructing a symmetric chain decomposition of the poset with the same underlying set as L(m, n) but with all possible covering relations between adjacent ranks [3, 10]. In elementary terms, the problem is to find a rule such that: 1. For each Young diagram in L(m, n), we either do nothing or remove a box so that the result is another Young diagram. 2. Each Young diagram has at most one preimage under this rule. 3. Each terminal Young diagram has complementary rank with the corresponding initial Young diagram. The main result of this paper involves a simple algorithm which, among other things, yields a symmetric chain decomposition for a large subposet of L(m, n) consisting of “sufficiently generic” partitions. 1.2 The monomial model of Young’s partition lattice Note that a partition λ ∈ L(m, n) is uniquely determined by the (n + 1)-tuple (a0 , . . . , an ) where ai is equal to the number of times that i appears in (λ1 , . . . , λm ). J Algebr Comb (2014) 39:783–806 785 A covering relation in L(m, n) is given by adding a box to an acceptable row of a Young diagram, which sends (a0 , . . . , an ) → (a0 , . . . , ai−1 − 1, ai + 1, . . . , an ). In this way, we obtain an edge coloring of the Hasse diagram of L(m, n), using n colors, where the ith color corresponds to the above operation. a Let An = C[z0 , . . . , zn ]. By mapping (a0 , . . . , an ) to the monomial z00 . . . znan we see that L(m, n) is isomorphic to the poset An (m) of monomials of degree m in An . In terms of partitions, this isomorphism is given by (λ1 , . . . , λm ) → zλ1 zλ2 · · · zλm . The ith color operation corresponds to changing a single zi−1 to zi , and this partial order is induced by the standard action of sl2 C on the irreducible representation Cz0 , . . . , zn . The advantage of using this model for Young’s partition lattice is that we can simultaneously deal with An (m) for all m ≥ 0 and exploit the full structure of An as a commutative graded C-algebra with sl2 C-action. 1.3 Combinatorial secant ideals of the rational normal curve Since finding a symmetric chain decomposition of L(m, n) is so difficult, we might first look for a coarser decomposition into centered subposets. From the point of view of commutative algebra, a natural way to decompose the monomial basis in An is to choose a monomial ideal I ⊂ An and form the graded algebra:  grI (An ) = I j /I j +1 . j ≥0 In fact, we can obtain even finer decompositions by starting with a set of monomial ideals I1 , . . . , It ⊂ An and looking at the multigraded algebra grI1 · · · grIt An . In order to take full advantage of the underlying symmetry, we should start with a set of sl2 C-invariant ideals and perform a Gröbner degeneration to obtain monomial ideals. For the rest of the paper, let k = n/2 . From the point of view of algebraic geometry, the nicest possible sl2 C-invariant subvarieties of projective space are the rational {r} normal curve Cn ⊂ Pn and its secant varieties Cn for 0 ≤ r ≤ k. By considering {r} the initial ideals of Cn (with respect to any diagonal term order) we obtain a set of squarefree monomial ideals In,r ⊂ An for 0 ≤ r ≤ k. We can now equip the monomial basis in An with extra gradings according to the order of vanishing on this set of monomial ideals. Given a monomial μ ∈ An , let degr (μ) be the number of minimal generators of In,r appearing in the image of μ under the natural map An → grIn,k · · · grIn,1 An . 786 J Algebr Comb (2014) 39:783–806 Given integers d0 , . . . , dk ≥ 0, we define   Qn (d0 , . . . , dk ) = μ ∈ An | degr (μ) = dr for each 0 ≤ r ≤ k . Set-theoretically, this decomposition is implicit in Conca’s “canonical decomposition” algorithm for factoring monomials [1]. However, our description (in terms of tropical polynomials, see below) does not depend on a particular choice of factorization and therefore allows for a finer investigation of the poset structure. It turns out that In,1 is the Stanley–Reisner ideal of the path graph with vertices {0, . . . , n}, and In,r is the rth combinatorial secant ideal of In,1 [7, 8]. Using these facts, we find an explicit formula for the irredundant irreducible decomposition of each In,r , which leads us to the following tropical polynomials: fn,r (a0 , . . . , an ) = min 0≤λ0 ≤···≤λn−2r ≤r n−2r  a2λj +j . j =0 a For any monomial μ = z00 · · · znan , we define fn,r (μ) = fn,r (a0 , . . . , an ). We have: (s) μ ∈ In,r ⇐⇒ fn,r (μ) ≥ s, where I (s) denotes the sth symbolic power of I . Remarkably, grading by the symbolic powers give us the same decomposition of monomials as the ordinary powers:   k    Qn (d0 , . . . , dk ) = μ ∈ An  fn,r (μ) = (j + 1 − r)dj for each 0 ≤ r ≤ k . j =r With this explicit description in hand, we find that Qn−2 (d1 , . . . , dk ) embeds into Qn (d0 , . . . , dk ) in two opposite ways, and there exists an elementary algorithm for producing coverings by saturated chains running between these two extremes. 1.4 The raising and lowering algorithm A pair of consecutive entries (ai , ai+1 ) in (a0 , . . . , an ) is called a maximal pair if ai + ai+1 = max (aj + aj +1 ). 0≤j ≤n−1 Let us now describe the crucial algorithm that produces saturated chains in Qn (d0 , . . . , dk ) running between the two extremal copies of Qn−2 (d1 , . . . , dk ). The algorithm (right-moving version) 1. Choose a maximal pair (ai , ai+1 ) for some 0 ≤ i ≤ n − 1. If i = n − 1, apply the nth color an−1 times and end the chain. 2. Otherwise, apply the (i + 1)th color (ai − ai+2 ) times, and then go back to the first step and start with the maximal pair (ai+1 , ai+2 ). J Algebr Comb (2014) 39:783–806 787 The algorithm (left-moving version) 1. Choose a maximal pair (ai−1 , ai ) for some 1 ≤ i ≤ n. If i = 1, apply the inverse of the first color a1 times and end the chain. 2. Otherwise, apply the inverse of the ith color (ai − ai−2 ) times, and then go back to the first step and start with the maximal pair (ai−2 , ai−1 ). a Given a monomial μ = z00 · · · znan ∈ Qn (d0 , . . . , dk ), we apply the two versions of the algorithm to the leftmost (resp. rightmost) maximal pair in (a0 , . . . , an ) to obtain the left (resp. right) transversal chain of μ. Theorem Let n, d0 , . . . , dk ≥ 0. The transversal chains provide a vertex covering of Qn (d0 , . . . , dk ) by saturated chains. If d0 > 0, then this covering is actually a decomposition. Transversal chains are not necessarily rank-symmetric. Nevertheless, when dealing with sufficiently generic monomials, we can stitch them together to get a symmetric chain decomposition. Corollary If Qn−2 (d1 , . . . , dk ) has a symmetric chain decomposition and 1 + 2d0 ≥ k  di (n − 2i)i, i=1 then Qn (d0 , . . . , dk ) has a symmetric chain decomposition. In other words, we can decompose Young’s partition lattice into a “generic” part and a “singular” part: L(m, n) = L(m, n)gen  L(m, n)sing , where L(m, n)gen is a symmetric chain order, and L(m, n)sing has a covering by transversal chains. Note that by a decomposition of a poset we mean a set-theoretic decomposition where each factor is equipped with the induced partial order. Let us outline the contents of the paper. In Sect. 2, we decompose L(m, n) according to the order of vanishing on the monomial ideals In,r for 0 ≤ r ≤ k, and we give a simpler description in terms of the level sets of certain tropical polynomials. The poset structure aside, the results of this section are essentially contained in [1]. In Sect. 3, we use the tropical description to prove that each level set in An contains two extremal embeddings of a smaller level set in An−2 . In Sect. 4, we prove that the raising and lowering algorithm yields a covering of the level sets by monotonic saturated chains running between the extremal subposets. Indeed, most of the time this covering is a decomposition, and this fact allows us to inductively stitch these chains together to obtain a symmetric chain decomposition for the generic part of L(m, n). 788 J Algebr Comb (2014) 39:783–806 2 Combinatorial secant ideals of the rational normal curve Let An = C[z0 , . . . , zn ], and let An (m) denote the set of monomials of degree m in An . Define a partial order on An (m) as follows: a b z00 · · · znan ≤ z00 · · · znbn n  ⇐⇒ ai ≤ i=j n  bi for 1 ≤ j ≤ n. i=j This partial order is induced by the following action of sl2 C = CH, E, F on the irreducible representation Cz0 , . . . , zn : H (zi ) = n − 2i, E(zi ) = izi−1 , F (zi ) = (n − i)zi+1 . It is not hard to see that L(m, n) is isomorphic to An (m) by the map (λ1 , . . . , λm ) → zλ1 zλ2 · · · zλm . Note that L(m, n) ≃ L(n, m) simply by taking the conjugate partition, which corresponds to the well-known duality An (m) ≃ Am (n) for choosing multisets from a a finite set. Also note that the weight of a monomial μ = z00 · · · znan is given by wt(μ) = n  ai (n − 2i), i=0 while its rank is given by rk(μ) = n  iai , i=0 and therefore we obtain the simple relation wt(μ) = mn − 2rk(μ). Since we will be working exclusively with centered subposets of An (m), it will be more convenient for us to refer to the weights of monomials instead of their ranks. Recall that k := n/2 . The ideal of the rational normal curve Cn ⊂ Pn is generated by the set of maximal minors of the (2 × n)-Hankel matrix: Hn,1 = z0 z1 z1 z2 ... ... zn−1 . zn Furthermore, the ideal of the rth secant variety of Cn is generated by the set of maximal minors of the (r + 1) × (n − r + 1) Hankel matrix ⎤ ⎡ z1 ... zr z0 ⎢ z1 z2 . . . zr+1 ⎥ ⎥ ⎢ Hn,r = ⎢ . . .. ⎥ . . ⎣ . . . ⎦ zn zn−r zn−r+1 . . . J Algebr Comb (2014) 39:783–806 789 where 1 ≤ r ≤ k. Let In,r denote the initial ideal (with respect to any diagonal term order) of the ideal of the rth secant variety of Cn . The minimal generators of In,r are the initial monomials of Hankel determinants,   In,r = {zi0 · · · zir | ij + 1 < ij +1 for 0 ≤ j ≤ r − 1} . For ease of notation, we define In = In,1 and In,0 = m = (z0 , . . . , zn ). Recall that for an ideal I in a ring A and an element a ∈ A such that  a∈ / Ij, j ≥0 the order of vanishing of a on I is defined as   ordI (a) = max j | a ∈ I j . The associated graded ring grI A =  I j /I j +1 j ≥0 receives a natural set map σ : A → grI A, where   σ (a) = a mod I d+1 if ordI (a) = d,  σ (a) = 0 if a ∈ Ij. j ≥0 Also, if J ⊂ A is another ideal, we can form the multigraded algebra grJ grI A := grJ grI A, where J denotes the ideal generated by σ (J ) ⊂ grI (A). In our situation, we will consider the composition of several such maps: An → grIn,1 An → grIn,2 grIn,1 An → · · · → grIn,k . . . grIn,1 An . Given a monomial μ ∈ An , let degr (μ) be the number of minimal generators of In,r appearing in the image of μ under the above composition. A maximal factorization of μ is any factorization of μ in An of the form μ = μ0 μ1 · · · μk , where each μr is a product of degr (μ) minimal generators of In,r . We can visualize a maximal factorization as a tableau with degr (μ) rows of length (r + 1), where the entries in each row form a <1 -chain, i.e., a sequence of nonnegative integers (i0 , . . . , ir ) such that ij + 1 < ij +1 for 0 ≤ j ≤ r − 1. Let us rearrange 790 J Algebr Comb (2014) 39:783–806 the entries in this tableau so that each entry is as small as possible as we read from left to right and from the longest to the shortest row. This is the same tableau obtained by factoring out each minimal generator of In,r in lexicographic order as r runs from k to 0, which is exactly Conca’s algorithm for “canonical decomposition” of monomials [1]. The key property of Conca’s tableau is that, for any entry a, either a or a − 1 must appear in each preceding row. Otherwise, we could insert a at an earlier place in the tableau while preserving the <1 -chains along the rows, which would contradict the fact that the tableau is initial for the lexicographic order. Example 2.1 The monomial μ = z0 z2 z3 z4 z5 ∈ A5 (5) has two possible maximal factorizations: 0 2 4 3 5 0 3 5 2 4 The one on the left is Conca’s tableau for μ. Definition 2.2 Following the above discussion, we obtain a multigraded decomposition of the monomial basis in An :   Qn (d0 , . . . , dk ) = μ ∈ An | degr (μ) = dr for all 0 ≤ r ≤ k . Note that μ ∈ Qn (d0 , . . . , dk ) if and only if Conca’s tableau for μ has exactly di rows of size (i + 1). Also note that Qn (d0 , . . . , dk ) ⊂ An (m), where m= k  dr (r + 1). r=0 While our decomposition is set-theoretically equivalent to Conca’s decomposition, there are a few subtle but important differences. Conca’s construction yields one particular maximal factorization for each monomial. This choice obscures the poset structure, which is our main object of interest. The goal of the rest of this section is to give a description of Qn (d0 , . . . , dk ) that treats all maximal factorizations equally and illuminates the structural relationships between these posets. To begin with, we give an explicit description of the unique irredundant irreducible decomposition of each In,r in terms of the associated simplicial complex. Let Δn denote the set of subsets of {0, . . . , n}. For any F ∈ Δn , we define   zF = zi ∈ An and mF = (zi ) ⊂ An . i∈F i∈F Let Γ ⊂ Δn be an abstract simplicial complex, so S ⊂ T ∈ Γ =⇒ S ∈ Γ . The Stanley–Reisner ideal of Γ is defined as follows:   F   IΓ = z F  F ∈ /Γ = m . F ∈Γ J Algebr Comb (2014) 39:783–806 791 For our problem, the relevant simplicial complex is the path graph with n + 1 vertices,   Γn = ∅, {0}, . . . , {n}, {0, 1}, {1, 2}, . . . , {n − 1, n} . It is easy to check that the Stanley–Reisner ideal of Γn is equal to In . Indeed, In ⊂ IΓn because In is generated by the quadratic monomials corresponding to the edges in the complement of the path graph. On the other hand, any F ∈ Δn such that |F | ≥ 3 must contain some i and j such that i + 1 < j , so we see that IΓn ⊂ In . Remark 2.3 We know from Sect. 6.1 of [8] that In,r is equal to the rth combinatorial secant ideal of In . Let Γn,r denote the simplicial complex of r-fold unions of simplices from Γn : Γn,r = {F1 ∪ · · · ∪ Fr | Fi ∈ Γn }. By Remark 2.9 of [7], it follows that In,r is the Stanley–Reisner ideal of Γn,r . Furthermore, it is not hard to see that each facet of Γn,r is equal to the disjoint union of r edges in Γn . Therefore, the set of F ∈ Δn such that F is a facet of Γn,r is equal to   {2λ0 , 2λ1 + 1, . . . , 2λn−2r + n − 2r} | 0 ≤ λ0 ≤ · · · ≤ λn−2r ≤ r . It follows that the irredundant irreducible decomposition of In,r (cf. [1], Lemma 3.5) is given by  m{2λ0 ,2λ1 +1,...,2λn−2r +n−2r} . In,r = 0≤λ0 ≤···≤λn−2r ≤r We are now ready to describe the symbolic powers of our monomial ideals. If I is a radical ideal in a polynomial ring over an algebraically closed field, then the sth symbolic power of I is  I (s) = Ms, M∈MI where MI denotes the set of all maximal ideals containing I [8]. Proposition 2.4 For each 0 ≤ r ≤ k, the tropical polynomial fn,r (a0 , . . . , an ) = min 0≤λ0 ≤···≤λn−2r ≤r n−2r  a2λj +j j =0 satisfies the following property: a (s) z00 · · · znan ∈ In,r ⇐⇒ fn,r (a0 , . . . , an ) ≥ s. Proof In fact, there is a general relationship between symbolic powers and tropical polynomials. Any squarefree monomial ideal I with the irredundant irreducible decomposition  I= mF F 792 J Algebr Comb (2014) 39:783–806 has the following symbolic powers: I (s) =  s mF . F Therefore, a z00 · · · znan ∈ I (s) ⇐⇒ Now,  F s = m   a z00 . . . znan ∈ (mF )s  b  zi i   i∈F i∈F z00 · · · znan ∈ (mF )s ⇐⇒ and so a for all F.  bi = s ,  ai ≥ s. i∈F In our particular example, we obtain: a (s) z00 · · · znan ∈ In,r ⇐⇒ 2n−r  a2λj +j ≥ s for all 0 ≤ λ0 ≤ · · · ≤ λn−2r ≤ r, j =0 which is equivalent to fn,r (a0 , . . . , an ) ≥ s.  Example 2.5 If n = 5, then the ideal I5,1 = (z0 z2 , z0 z3 , z0 z4 , z0 z5 , z1 z3 , z1 z4 , z1 z5 , z2 z4 , z2 z5 , z3 z5 ) has the following irredundant irreducible decomposition: (z0 , z1 , z2 , z3 ) ∩ (z0 , z1 , z2 , z5 ) ∩ (z0 , z1 , z4 , z5 ) ∩ (z0 , z3 , z4 , z5 ) ∩ (z2 , z3 , z4 , z5 ), and the corresponding tropical polynomial is ⎫ ⎧ ⎪ ⎪ ⎪ a0 + a1 + a2 + a3 ⎪ ⎪ ⎪ ⎪ ⎬ ⎨ a0 + a1 + a2 + a5 ⎪ f5,1 (a0 , . . . , a5 ) = min a0 + a1 + a4 + a5 . ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ a0 + a3 + a4 + a5 ⎪ ⎭ ⎩ a2 + a3 + a4 + a5 Similarly, I5,2 = (z0 z2 z4 , z0 z2 z5 , z0 z3 z5 , z1 z3 z5 ) = (z0 , z1 ) ∩ (z0 , z3 ) ∩ (z0 , z5 ) ∩ (z2 , z3 ) ∩ (z2 , z5 ) ∩ (z4 , z5 ), f5,2 (a0 , . . . , a5 ) = min(a0 + a1 , a0 + a3 , a0 + a5 , a2 + a3 , a2 + a5 , a4 + a5 ). J Algebr Comb (2014) 39:783–806 793 a Remark 2.6 For a monomial μ = z00 · · · znan , note that fn,r minimizes a sum over the complements of facets of Γn,r :  ai . fn,r (μ) = min F ∈Γn,r i ∈F / Since deg(μ) = a0 + · · · + an , we can rewrite this as     ai = deg(μ) − max ai . fn,r (μ) = min deg(μ) − F ∈Γn,r F ∈Γn,r i∈F i∈F Given a facet F ∈ Γn,r , we will refer to the sum  ai α(F, μ) = i∈F as the amount of μ covered by F . With this terminology, in order to calculate fn,r (μ), we need to use r disjoint edges in Γn to cover as much of μ as possible. Lemma 2.7 For any monomial μ ∈ An and 0 ≤ r ≤ k, we have: fn,r (μ) = k  (j + 1 − r) degj (μ) and degr (μ) = (fn,r − 2fn,r+1 + fn,r+2 )(μ), j =r where fn,j = 0 for j > k. Proof Consider the smallest entry a in the last row of Conca’s tableau for μ. Since a or a − 1 must appear in each preceding row, we see that covering {a − 1, a} with an edge from Γn will maximize the amount covered. Moreover, the rows are <1 -chains, so we can cover exactly one entry from each row. In other words, the number of boxes in the first column of the tableau is equal to  ai . max F ∈Γn i∈F Therefore, fn,1 (μ) is equal to the number of boxes that do not lie in the first column. Now we remove the boxes with entries a or a − 1 from the tableau and repeat this argument for what remains. It follows that fn,r (μ) is equal to the number of boxes of the tableau that do not lie in the first r columns. Subtracting r boxes from each row and adding up what remains, we find that k  (j + 1 − r) degj (μ). fn,r (μ) = j =r Moreover, degr (μ) is equal to the difference between the number of boxes in the (r + 1)th column and the (r + 2)th column. Therefore,     degr (μ) = fn,r (μ) − fn,r+1 (μ) − fn,r+1 (μ) − fn,r+2 (μ) = fn,r (μ) − 2fn,r+1 (μ) + fn,r+2 (μ), as desired.  794 J Algebr Comb (2014) 39:783–806 Example 2.8 Consider the monomial μ = z02 z14 z23 z3 z4 z54 ∈ A5 (15). Conca’s decomposition for μ yields the tableau 0 0 1 1 1 1 2 2 4 2 5 3 5 5 5 Note that f5,0 (μ) = deg(μ) = 15. First, we cover {1, 2}, which removes seven boxes, so f5,1 (μ) = 15 − 7 = 8. Next, we cover {4, 5}, which removes five boxes, so f5,2 (μ) = 8 − 5 = 3. Counting the number of rows of each size, we see that deg0 (μ) = 2 = 15 − 2(8) + 3, deg1 (μ) = 2 = 8 − 2(3), deg2 (μ) = 3, as expected. 3 Structure of the level sets We have the following “tropical” decomposition of An (m):   k  Qn (d0 , . . . , dk ) = μ ∈ An | fn,r (μ) = (j + 1 − r)dj for each 0 ≤ r ≤ k , j =r where m= k  dj (j + 1). j =0 Note that each fn,r is a piecewise-linear function from Rn+1 → R. It follows that Qn (d0 , . . . , dk ) can be visualized as the set of integer lattice points in Rn+1 ≥0 that lie in the intersection of the given level sets:    (a0 , . . . , an ) | fn,r (a0 , . . . , an ) = (j + 1 − r)dj . 0≤r≤k In fact, since fn,0 = m, we can actually visualize these posets inside Rn . Example 3.1 We embed A3 (m) ⊂ R3 by drawing the covering relations along the three axes as follows: z0 • • z1 z1 • • z2 z2 • • z3 J Algebr Comb (2014) 39:783–806 795 Below we have drawn the Hasse diagram of A3 (4) ⊂ Z3≥0 along with its tropical decomposition into three subposets: • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • Q3 (4, 0) • • • • • • • • • • • • • • • • • • • • • Q3 (2, 1) • • • • • • Q3 (0, 2) • • • • • • • Proposition 3.2 Qn (d0 , . . . , dk ) is a rank-symmetric, rank-unimodal, and centered subposet of An (m). Proof Since Γn has an involution which sends i to n − i, we see that In,r and fn,r are invariant under the automorphism τn of An that sends each zi to zn−i . It follows that Qn (d0 , . . . , dk ) carries a rank-flipping involution, which implies that it is a ranksymmetric, centered subposet of An (m). To prove the rank-unimodality of Qn (d0 , . . . , dk ), let Jn,r denote the ideal generated by maximal minors of the Hankel matrix Hn,r . Since all of the ideals involved are sl2 C-invariant, the multigraded components of the algebra grJn,k · · · grJn,1 An are finite-dimensional sl2 C-representations. In particular, the dimensions of the weight spaces of each multigraded component form a unimodal sequence. Since the algebra grIn,k · · · grIn,1 An is obtained by Gröbner degeneration, the dimensions of the weight spaces remain the same, and therefore the rank sizes of Qn (d0 , . . . , dk ) form a unimodal sequence.  Note that In,r has a unique minimal generator of highest (resp. lowest) weight, namely: μn,r = z0 z2 · · · z2r   resp. νn,r = τn (μn,r ) = zn zn−2 · · · zn−2r . 796 J Algebr Comb (2014) 39:783–806 It follows that Qn (d0 , . . . , dk ) has a unique monomial of highest (resp. lowest) weight, namely: μn (d0 , . . . , dk ) = k  # dj μn,j resp. νn (d0 , . . . , dk ) = j =0 k  $ dj νn,j . j =0 We can now state the embedding property of the Q-posets. Lemma 3.3 Let d0 , . . . , dk ≥ 0, and let d = d0 + · · · + dk . Then multiplication by znd induces an embedding of posets, znd : Qn−2 (d1 , . . . , dk ) → Qn (d0 , . . . , dk ), which sends νn−2 (d1 , . . . , dk ) to νn (d0 , . . . , dk ). Proof Since zn νn−2,r = νn,r , we see that znd νn−2 (d1 , . . . , dk ) = znd0 k k   d dj dj znj νn−2,j = νn,j = νn (d0 , . . . , dk ). j =1 j =0 Let μ ∈ Qn−2 (d1 , . . . , dk ). One can show that Conca’s tableau for znd μ is obtained from Conca’s tableau for μ by adding a box with entry n to the end of each row (along with d0 extra rows of size one, each with entry n). We give a second proof below in terms of tropical polynomials. Recall that (fn,0 − fn,1 )(a0 , . . . , an ) = max (aj + aj +1 ). 0≤j ≤n−1 In the monomial znd μ, the sum of the exponents of zn−1 and zn is equal to d, and d ≥ d1 + · · · + dk = fn−2,0 (μ) − fn−2,1 (μ). In other words, the edge {n − 1, n} will cover at least as much of znd μ as any other edge in Γn . Now we claim that, for each 1 ≤ r ≤ k,   fn,r znd μ = fn−2,r−1 (μ). Recall that the calculation of fn,r involves all r-fold disjoint unions of edges in Γn . We can split up this calculation into two cases: the nth vertex is either covered or uncovered. If the nth vertex is covered, then so is the (n − 1)th vertex, which leaves r − 1 edges for the vertices 0, . . . , n − 2. In other words, for znd μ, we have max n∈F ∈Γn,r  i∈F ai = d + max F ∈Γn−2,r−1  i∈F ai = d + deg(μ) − fn−2,r−1 (μ). J Algebr Comb (2014) 39:783–806 797 On the other hand, if the nth vertex is uncovered, choose r − 1 pairwise disjoint edges from Γn−2 and then arbitrarily choose the rth edge from Γn−1 . Since the exponent of zn−1 in znd μ is zero, we get the following inequalities: max  n∈F / ∈Γn,r i∈F ai ≤ max (aj + aj +1 ) + 0≤j ≤n−2 max F ∈Γn−2,r−1  ai i∈F ≤ d + deg(μ) − fn−2,r−1 (μ). Therefore,      fn,r znd μ = deg znd μ − max ai F ∈Γn,r i∈F     = d + deg(μ) − max max ai , max ai n∈F ∈Γn,r i∈F n∈F / ∈Γn,r i∈F = d + deg(μ) − d − deg(μ) + fn−2,r−1 (μ) = fn−2,r−1 (μ). It follows that, for 1 ≤ r ≤ k,     degr znd μ = (fn,r − 2fn,r+1 + fn,r+2 ) znd μ = (fn,r−1 − 2fn,r + fn,r+1 )(μ) = degr−1 (μ). The only difference occurs at r = 0:     deg0 znd μ = (fn,0 − 2fn,1 + fn,2 ) znd μ = d + (fn−2,0 − 2fn−2,0 + fn−2,1 )(μ) = d − (fn−2,0 − fn−2,1 )(μ) = d − (d1 + · · · + dk ) = d0 . Therefore, we have shown that multiplication by znd defines a map Qn−2 (d1 , . . . , dk ) → Qn (d0 , . . . , dk ). Since multiplication by a fixed element is injective and preserves the partial order, this map is an embedding of posets.  Remark 3.4 Composing the above embedding with the rank-flipping involution on both sides, we get another embedding, τn znd τn−2 : Qn−2 (d1 , . . . , dk ) → Qn (d0 , . . . , dk ), 798 J Algebr Comb (2014) 39:783–806 which sends μn−2 (d1 , . . . , dk ) to μn (d0 , . . . , dk ). We can express this embedding as the composition of the homomorphism κn : An−2 → An that sends each zi → zi+2 , followed by multiplication by z0d . Indeed, for any minimal generator zi0 . . . zir of In−2,r we have: τn zn τn−2 (zi0 · · · zir ) = τn (zn zn−2−i0 · · · zn−2−ir ) = z0 zi0 +2 · · · zir +2 = z0 κn (zi0 · · · zir ) from which the general formula follows. Remark 3.5 The images of the above embeddings can be written down in elementary terms as well: % &  z0d κn Qn−2 (d1 , . . . , dk ) = μ ∈ Qn (d0 , . . . , dk )  a0 = max (aj + aj +1 ) , %  znd Qn−2 (d1 , . . . , dk ) = μ ∈ Qn (d0 , . . . , dk )  an = 0≤j ≤n−1 & max (aj + aj +1 ) . 0≤j ≤n−1 These equalities follow immediately from the fact that covering {0, 1} (resp. {n − 1, n}) will cover the maximum possible amount in each such monomial. 4 The raising and lowering algorithm Recall that the Hasse diagram of An (m) is equipped with an edge coloring by {1, . . . , n}, where the ith color corresponds to the following covering relation: (a0 , . . . , an ) → (a0 , . . . ai−1 − 1, ai + 1, . . . , an ). Let C be a saturated chain in An (m). We obtain a sequence of colors (c1 , . . . , ct ) by reading the covering relations in C from highest to lowest weight. We say that a saturated chain C is monotonic if c1 ≤ · · · ≤ ct . A pair of consecutive entries (ai , ai+1 ) of (a0 , . . . , an ) is called a maximal pair if ai + ai+1 = max (aj + aj +1 ). 0≤j ≤n−1 a Let μ = z00 · · · znan ∈ Qn (d0 , . . . , dk ). The following “right-moving” algorithm produces a monotonic saturated chain between μ and an element of znd Qn−2 (d1 , . . . , dk ): 1. Let (ai , ai+1 ) be a maximal pair of (a0 , . . . , an ). If i = n − 1, apply the nth color an−1 times and end the chain. 2. If i < n − 1, apply the (i + 1)th color (ai − ai+2 ) times, then go back to the first step and choose the maximal pair (ai+1 , ai+2 ). The corresponding “left-moving” algorithm produces a monotonic saturated chain between μ and an element of z0d κn Qn−2 (d1 , . . . , dk ): J Algebr Comb (2014) 39:783–806 799 1. Let (ai−1 , ai ) be a maximal pair of (a0 , . . . , an ). If i = 1, apply the inverse of the first color a1 times and end the chain. 2. If i > 1, apply the inverse of the ith color (ai − ai−2 ) times, then go back to the first step and choose the maximal pair (ai−2 , ai−1 ). The left transversal chain of μ is constructed as follows. We begin with the leftmost maximal pair in (a0 , . . . , an ) and run both the left-moving and right-moving algorithms. The concatenation of the two resulting chains is a single monotonic saturated chain passing through μ which runs between z0d κn Qn−2 (d1 , . . . , dk ) and znd Qn−2 (d1 , . . . , dk ). Similarly, the right transversal chain of μ is constructed by applying the same procedure starting with the rightmost maximal pair in (a0 , . . . , an ). Example 4.1 Consider the monomial μ = z0 z1 z2 z4 z5 ∈ A5 (5). We easily calculate that f5,1 (μ) = 3 and f5,2 (μ) = 1, so μ ∈ Q5 (0, 1, 1). The corresponding lattice vector is (a0 , . . . , a5 ) = (1, 1, 1, 0, 1, 1), which we can visualize as five indistinguishable balls distributed among six labeled urns. The following diagrams represent the calculation of the left and right transversal chains of μ: • • • • • • • μ= • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • =μ • • • • • • • • Left transversal chain • • • • • Right transversal chain Upward arrows denote left moves, downward arrows denote right moves, and covered maximal pairs are underlined. We have chosen not to draw the steps where no balls are moved and the only change is the movement of the covering edge. Theorem 4.2 Let n, d0 , . . . , dk ≥ 0. The transversal chains provide a vertex covering of Qn (d0 , . . . , dk ) by monotonic saturated chains. If d0 > 0, then this covering is actually a decomposition. Proof For the first statement, the only thing to check is that the algorithm stays within Qn (d0 , . . . , dk ) at each step. We claim that if (ai , ai+1 ) is a maximal pair of (a0 , . . . , an ) and ai > ai+2 , then fn,r (a0 , . . . , an ) = fn,r (a0 , . . . , ai − 1, ai+1 + 1, . . . , an ) 800 J Algebr Comb (2014) 39:783–806 for all 0 ≤ r ≤ k. To prove this, let us deal with each possible case in turn. Let μ denote the monomial obtained by applying the (i + 1)th color to μ. Recall that fn,r (μ) = min α(F , μ). F ∈Γn,r If F ∈ Γn,r is a facet such that {i, i + 1} ⊂ F , then α(F , μ ) = α(F , μ). If i ∈ F and i + 1 ∈ / F , then α(F , μ ) = α(F , μ) + 1, which means that it is irrelevant for calculating the minimum over such sums. The only other possibility is that i ∈ /F and i + 1 ∈ F , which means that i + 2 ∈ F as well. In this case, since ai > ai+2 , we see that α(F , μ) > fn,r (μ), because moving the edge to the left by one step and covering {i, i + 1} would strictly decrease the sum. Therefore, α(F , μ ) = α(F , μ) − 1 ≥ fn,r (μ), and the overall minimization will be unchanged. For the second statement, if d0 > 0, then Conca’s tableau for μ has at least one row of size one. If the entry in the last row is 0 (resp. n), then (a0 , a1 ) (resp. (an−1 , an )) is the unique maximal pair. Otherwise, if the entry in the last row is 0 < i < n, then (ai−1 , ai ) is a maximal pair. The only other possible maximal pair is (ai , ai+1 ), which can only happen if ai−1 = ai+1 . In this case, the algorithm will only move the covering edge, so there is essentially a unique starting maximal pair. It follows that the left and right transversal chains of μ coincide and the transversal chains are necessarily disjoint from each other by the uniqueness of each step of the algorithm. Therefore, if d0 > 0, we obtain a monotonic saturated chain decomposition of Qn (d0 , . . . , dk ).  Corollary 4.3 If Qn−2 (d1 , . . . , dk ) has a symmetric chain decomposition and 1 + 2d0 ≥ k  dj (n − 2j )j, j =1 then Qn (d0 , . . . , dk ) has a symmetric chain decomposition. Proof Suppose we have a decomposition Qn−2 (d1 , . . . , dk ) = C1  · · ·  Ct where each Ci is a rank-symmetric, saturated chain. Let μ0 be a monomial in Ci for some i. Let d = d0 + · · · + dk and consider the monomial a μ = z00 . . . znan = τn znd τn−2 μ0 = z0d κn μ0 ∈ Qn (d0 , . . . , dk ). Let us calculate the left transversal chain of μ. The leftmost maximal pair is (a0 , a1 ) and a1 = 0, so the first few steps of the algorithm look like (a0 , 0, a2 , a3 , . . . , an ), (a2 , a0 − a2 , a2 , a3 , . . . , an ), (a2 , a3 , a0 − a3 , a3 , . . . , an ), .. . J Algebr Comb (2014) 39:783–806 801 (a2 , a3 , . . . , an , a0 − an , an ), (a2 , a3 , . . . , an , 0, a0 ). We see that the a0 term travels to the right while all the other entries shift to the left by two spots. In other words, the left transversal chain of z0d κn μ0 in Qn (d0 , . . . , dk ) has lowest weight monomial znd μ0 . The key point is that, for d0 > 0, we obtain a decomposition Qn (d0 , . . . , dk ) = R1  · · ·  Rt where Ri is the induced subposet that contains the chains z0d κn Ci and znd Ci , as well as all the transversal chains between them. Note that Ri also contains d0 + 1 translates of z0d κn Ci (resp. znd Ci ), namely d−j j z1 κn Ci z0   j d−j resp. zn−1 zn Ci for 0 ≤ j ≤ d0 . The general structure of Ri can be represented as follows: z0d κn Ci • .• • .. .• .•. .. .. •. .. .. . • •. • . .. .. ... •. • .. .• .. . .. • • .. .• . .. • • • Transversal chains • • znd Ci • • • .. • Now the boundary of this rectangle can be thought of as a disjoint union of a pair of symmetric saturated chains (in two different ways). If we remove such a pair of symmetric chains, we are left with a smaller rectangle. We can continue this process as long as we are guaranteed that the boundary of what remains is connected. At each step, the length of Ci is truncated by two, and the length of each transversal chain is truncated by four. Therefore, for Ri to have a symmetric chain decomposition, it is sufficient that 2d0 + 1 is greater than or equal to the number of edges in a maximal chain of Qn−2 (d1 , . . . , dk ). We may assume that C1 is the chain containing the unique highest weight monomial μn−2 (d1 , . . . , dk ) (resp. lowest weight monomial νn−2 (d1 , . . . , dk )) in Qn−2 (d1 , . . . , dk ). Note that the number of edges in any chain of Qn (d0 , . . . , dk ) of maximal length is equal to the weight of μn (d0 , . . . , dk ), and 802 J Algebr Comb (2014) 39:783–806 k    wt μn (d0 , . . . , dk ) = dj wt(μn,j ) j =0 = k  j  dj (n − 4i) j =0 = k  i=0   dj n(j + 1) − 2j (j + 1) j =0 = k  dj (n − 2j )(j + 1). j =0 Therefore, the number of edges in C1 is equal to k−1  dj +1 (n − 2 − 2j )(j + 1) = j =0 k  dj (n − 2j )j. j =1 We conclude that if 1 + 2d0 ≥ k  dj (n − 2j )j, j =1 then Qn (d0 , . . . , dk ) has a symmetric chain decomposition.  We can now define the generic part of L(m, n). We say that (d0 , . . . , dk ) ∈ Zk+1 ≥0 is n-stable if 1 + 2d0 ≥ k  dj (n − 2j )j, j =1 and we say that (d0 , . . . , dk ) ∈ Zk+1 ≥0 is generic if (dr , . . . , dk ) is (n − 2r)-stable for each 0 ≤ r ≤ k. Now we define ' L(m, n)gen = Qn (d0 , . . . , dk ). (d0 ,...,dk ) generic Let L(m, n)sing denote the complement of L(m, n)gen in L(m, n), equipped with the induced partial order. Then Corollary 4.3 implies that there is a decomposition of L(m, n) into centered, rank-symmetric, and rank-unimodal subposets: L(m, n) = L(m, n)gen  L(m, n)sing such that L(m, n)gen is a symmetric chain order. J Algebr Comb (2014) 39:783–806 803 Conjecture 4.4 We conjecture that Qn (d0 , . . . , dk ) is a symmetric chain order for all n, d0 , . . . , dk ≥ 0. This statement is strictly stronger than the statement that L(m, n) is a symmetric chain order for all m, n ≥ 0 since there are examples of m and n where symmetric chain decompositions of L(m, n) do not necessarily respect the tropical decomposition. Remark 4.5 The inequality presented in the theorem is not a necessary condition for Qn (d0 , . . . , dk ) to have a symmetric chain decomposition. Indeed, the argument will produce a symmetric chain decomposition for Ri as long as we can successively peel off two boundary chains at a time and leave a rectangle with connected boundary. Corollary 4.6 L(m, n) is a symmetric chain order if min(m, n) ≤ 4. Proof First note that if min(m, n) ≤ 2, then L(m, n) = L(m, n)gen , so we are done by Corollary 4.3. By the way, since Q2 (0, 1) = {z0 z2 }, we have an isomorphism of ranked posets Q2 (d0 , d1 ) ≃ Q2 (d0 , 0), which consists of a single symmetric chain of size 2d0 + 1. It follows that our decomposition A2 (m) = m/2 ' Q2 (m − 2j, j ) ≃ j =0 m/2 ' Q2 (m − 2j, 0) j =0 is already a symmetric chain decomposition. If n = 3, then we have A3 (m) = m/2 ' Q3 (m − 2j, j ). j =0 If d0 = 0, then m = 2j , and there is an isomorphism of ranked posets: Q3 (0, m/2) ≃ A2 (m/2) (z0 z2 )a02 (z0 z3 )a03 (z1 z3 )a13 → (a02 , a03 , a13 ), so Q3 (0, m/2) is a symmetric chain order. On the other hand, if d0 > 0, then the two embedded copies of Q1 (j ) ⊂ Q3 (m − 2j, j ) are both saturated chains of size (j + 1), so Q3 (m − 2j, j ) is a rectangular poset of the type discussed in the proof of Corollary 4.3. The top copy of Q1 (j ) consists of monomials of the form z00 (z0 z2 )d1 −j (z0 z3 )j . d Since the first color (which changes a single z0 to a z1 ) can be applied (d0 + j ) times to the j th element, we see that there will be sufficient translates of Q1 (j ) in Q3 (m − 2j, j ) for the argument of Corollary 4.3 to work. 804 J Algebr Comb (2014) 39:783–806 If n = 4, then we have ' A4 (m) = Q4 (d0 , d1 , d2 ). d0 +2d1 +3d2 =m Note that Q4 (0, 0, 1) = {z0 z2 z4 }, so Q4 (d0 , d1 , d2 ) ≃ Q4 (d0 , d1 , 0). It follows that A4 (m) ≃ m/2 ' Q4 (m − 2j, j, 0). j =0 If d0 = 0, we have an isomorphism of ranked posets, Q4 (0, m/2, 0) ≃ A2 (m) (zi zj )aij → (2a02 + a03 + a13 , a03 + 2a04 + a14 , a13 + a14 + 2a24 ). If d0 > 0, we have the two copies Q2 (j, 0) ⊂ Q4 (m − 2j, j, 0), which are saturated chains of size (2j + 1). The top copy consists of monomials of two types, z00 (z0 z2 )d1 −j (z0 z3 )j d and z00 (z0 z3 )d1 −j (z0 z4 )j . d The first color can be applied (d0 + j ) times to elements of the first type, while the elements of the second type can receive (d0 +d1 ) applications of the first color followed by j applications of the second color. Again, it follows that there will be sufficient  translates of Q2 (j, 0) available to apply the proof technique of Corollary 4.3. Example 4.7 To see why the proof of Corollary 4.6 does not generalize, consider Q5 (0, 1, 1) ⊂ L(5, 5)sing . We draw the covering relations of A5 (m) along the five coordinate axes of R5 as follows: z0 • • z1 z1 • • z2 z2 • • z3 z3 • z4 • • z4 • z5 J Algebr Comb (2014) 39:783–806 805 and we obtain the following embedding of Q5 (0, 1, 1) ⊂ Z5≥0 : • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • For min(m, n) ≤ 4 and d0 = 0, we could identify the Q-posets in terms of posets encountered earlier. In this case, we find a poset containing overlapping copies of both Q5 (0, 1, 0) ≃ L(2, 3) and Q5 (0, 0, 1) ≃ L(3, 1). In such composite cases, it is not clear how to stitch the known symmetric chain decompositions together. Also, in general, when d0 > 0, one has to choose a symmetric chain decomposition of Qn−2 (d1 , . . . , dk ) in order to obtain a rectangular decomposition of Qn (d0 , . . . , dk ), and some choices may result in rectangles that are not symmetric chain orders. Acknowledgements Thanks are due to Peter Magyar for telling me about Stanley’s conjecture and for many enlightening conversations on a host of mathematical topics. I would also like to thank the Department of Mathematics at Michigan State University for their hospitality while this project was under way. References 1. Conca, A.: Straightening law and powers of determinantal ideals of Hankel matrices. Adv. Math. 138, 263–292 (1998) 2. Lindström, B.: A partition of L(3, n) into saturated chains. Eur. J. Comb. 1, 61–63 (1980) 3. O’Hara, K.: Unimodality of Gaussian coefficients: a constructive proof. J. Comb. Theory, Ser. A 53, 29–52 (1990) 4. Proctor, R.A.: Solution of two difficult combinatorial problems with linear algebra. Am. Math. Mon. 89, 721–734 (1982) 5. Riess, W.: Zwei Optimierungsprobleme auf Ordnungen. In: Arbeitsberichte des Institut für Mathematische Maschinen und Datenverarbeitung (Informatik), Bank II, Number, 5 Erlangen, pp. 50–57 (1978) 6. Stanley, R.: Weyl groups, the hard Lefschetz theorem, and the Sperner property. SIAM J. Algebr. Discrete Methods 1, 168–184 (1980) 806 J Algebr Comb (2014) 39:783–806 7. Sturmfels, B., Sullivant, S.: Combinatorial secant varieties. Pure Appl. Math. Q. 2(3), 867–891 (2006). Part 1 8. Sullivant, S.: Combinatorial symbolic powers. J. Algebra 319(1), 115–142 (2008) 9. West, D.: A symmetric chain decomposition of L(4, n). Eur. J. Comb. 1, 379–383 (1980) 10. Zeilberger, D.: Kathy O’Hara’s constructive proof of the unimodality of the Gaussian polynomials. Am. Math. Mon. 96, 590–602 (1989)