Combinatorial relations on skew Schur and skew stable Grothendieck polynomials
Melody Chan Nathan Pflueger













calc, cd





thmTheorem[section]
prop[thm]Proposition
claim[thm]Claim
cor[thm]Corollary
conj[thm]Conjecture
algorithmAlgorithm


definition 
ex[thm]Example
defn[thm]Definition
convention[thm]Convention
observation[thm]Observation

















































































Definition[thm]Definition
definition
  

Example[thm]Example
example
  

Fact[thm]Fact
fact
  

Theorem[thm]Theorem
theorem
  
  
Lemma[thm]Lemma
lemma
  


Remark[thm]Remark
remark
  

Proposition[thm]Proposition
proposition
  

Corollary[thm]Corollary
corollary
  

remark
obs[thm]Observation
















 




M. Chan]Melody ChanDepartment of Mathematics, Brown University, Box
1917, Providence, RI 02912melody_chan@brown.edu

N. Pflueger]Nathan PfluegerDepartment of Mathematics and Statistics, Amherst College, Amherst, MA 01002npflueger@amherst.edu








We give a combinatorial expansion of the stable Grothendieck polynomials of skew Young diagrams in terms of skew Schur functions, using a new row insertion algorithm for set-valued semistandard tableaux of skew shape. This expansion unifies some previous results: it generalizes a combinatorial formula obtained in earlier joint work with López Martín and Teixidor i Bigas concerning Brill-Noether curves, and it generalizes a 2000 formula of Lenart and a recent result of Reiner-Tenner-Yong to skew shapes. We also give an expansion in the other direction: expressing skew Schur functions in terms of skew Grothendieck polynomials.






Combinatorial relations on skew Schur and skew stable Grothendieck polynomials
    [
    December 30, 2023
==============================================================================







§ INTRODUCTION






Let σ be a skew Young diagram (Definition <ref>).
The main result of this paper is a new formula for the skew stable Grothendieck polynomial G_σ of Lascoux-Schützenberger and Fomin-Kirillov  <cit.> as a linear combination of skew Schur functions s_λ on related shapes λ. As was demonstrated by Buch, the coefficients of G_σ  have a combinatorial interpretation in terms of set-valued tableaux <cit.>, and
our original motivation for this paper came from a recent geometric result, proved in a companion paper <cit.>, identifying Euler characteristics of Brill-Noether varieties up to sign as counts of set-valued standard tableaux. 

   

It is natural to ask for a linear expansion of G_σ in terms of other symmetric functions, particularly the basis of Schur functions. 
Such an expansion was obtained by Fomin-Greene, who in fact obtained such expansions for a wide class of symmetric functions including stable Grothendieck polynomials associated to arbitrary permutations <cit.>.  (Note that the stable Grothendieck polynomials of 321-avoiding permutations precisely correspond to stable Grothendieck polynomials of skew shapes as in <cit.>, by a theorem of Billey-Jockusch-Stanley <cit.>.)   Buch's expansion of skew Grothendieck polynomials in terms of Grothendieck polynomials of straight shapes, along with Lenart's expansion of the latter into Schur functions, provides another route to such an expansion <cit.>.  

Our main theorem expresses G_σ instead as a linear combination of skew Schur functions s_λ.  
The coefficients of the linear combination have explicit combinatorial interpretations which we provide; they count appropriate auxiliary tableaux.  We state the result below, postponing all definitions to the next section.


For any connected skew shape σ, the skew Grothendieck polynomial G_σ admits a linear expansion 
    G_σ = ∑_μ⊇σ (-1)^|B(μ/σ)| a_σ,μ· s_μ

where the a_σ, μ are nonnegative integers and the s_μ are skew Schur functions. Here a_σ,μ is the product of the following two integers:


  * the number of row-weakly-bounded semistandard tableaux of shape A(μ/σ), and

  * the number of row-bounded, reverse row-strict tableaux of shape B(μ/σ).



Here A(μ/σ) and B(μ/σ) are the subshapes of μ lying above and below σ, respectively.  In fact, this statement is a specialization of a more general formula for row-refined skew stable Grothendieck polynomials that we obtain in Theorem <ref>.  

Theorem <ref> generalizes Lenart's theorem from 2000 expanding Grothendieck polynomials for non-skew shapes into non-skew Schur functions <cit.>; in fact, that result is a visible specialization.  We explain this connection in detail in Remark <ref>.  We also give a theorem in the other direction, Theorem <ref>, expressing s_σ in terms of polynomials G_μ, for skew shapes σ.  This generalizes an analogous theorem of Lenart from the same paper.



To be clear, skew Schur functions, since they include Schur functions properly, are evidently not a basis for the space of symmetric functions; thus the coefficients of our expansion are not canonical. 
To provide a point of comparison, a result in the literature that is similar in spirit to Theorem <ref> is the skew Pieri rule of Assaf-McNamara, in which the product of a skew shape and a rectangle is expressed in terms of other skew shapes <cit.>. Again, this expression is necessarily noncanonical, but it is combinatorially natural using an insertion algorithm.  Our proof also uses a new insertion algorithm for skew set-valued semistandard tableaux that is related to previous work of Bandlow-Morse, and indeed our algorithm may be interpreted as extending to the skew case some of their results <cit.>.  In fact, it recalls earlier work of Sagan-Stanley row insertion for skew (non-set-valued) tableaux <cit.>, as well as Buch's “uncrowding” algorithm on set-valued tableaux <cit.>.  We also note that using insertion operations to derive such combinatorial identities has been carried out previously, in the form of Hecke insertion operations studied in <cit.>.



Motivation from geometry. 
Our original motivation came from a recent result in Brill-Noether theory that we prove in a pair of companion papers (<cit.>, together with <cit.> which proves an auxiliary result).  
<cit.> Fix r,d≥ 0 and nondecreasing sequences α,β∈^r+1_≥ 0.  Let (X,p,q) be a general twice-pointed curve of genus g over an algebraically closed field.
Then the algebraic Euler characteristic of the Brill-Noether variety (X,p,q) is 

    χ((X,p,q)) = (-1)^g-|σ|·#(standard set-valued tableaux on σ of content {1,…,g}).

 
Here σ is the skew-shape obtained from an (r+1)× (g-d+r) rectangle by adding α_r ≤⋯≤α_0 boxes down the left side and β_0≥⋯≥β_r boxes down the right side.  The partitions α and β encode some ramification conditions imposed at the two marked points p,q of X.  Roughly speaking, from the geometric perspective it is natural to seek formulae for set-valued tableaux in terms of skew Schur functions, which do not give preference to one marked point over the other, rather than (straight) Schur functions, which do.
Indeed, 
our result provides a combinatorial explanation of the main theorem of <cit.>, as we shall explain further in Remark <ref>.    It also generalizes a theorem with López and Teixidor i Bigas which computes genera of Brill-Noether curves  <cit.>. (That case corresponds to the situation in which there is exactly one more label than the number of boxes.)  
In addition, a recent result of Reiner-Tenner-Yong  
is also a special case of Theorem <ref>, and in fact, their work inspired some of the results here <cit.>. 





§ PRELIMINARIES


We now give some preliminaries on tableaux.  First we define a skew Young diagram: this is almost the same as the usual definition, except that we only record the set of boxes in a diagram rather than remembering a formal difference of two partitions.
Fix the partial order ≼ on ^2 given by (x,y)≼ (x',y') if x≤ x' and y≤ y'.  




  * A skew Young diagram is a finite subset σ⊂_>0^2 that is closed under taking intervals.  In other words, σ has the property that if (x,y) and (x',y')∈σ with (x,y)≼ (x',y'), then 
    {(x”,y”):(x,y)≼ (x”,y”) ≼ (x',y')}⊆σ.


  * A skew Young diagram is called a Young diagram if σ is empty or has a unique minimal element.



Skew Young diagrams are sometimes also called skew shapes, and skew Young diagrams having a unique minimal element will sometimes be called straight shapes for emphasis. 
In accordance with the English notation for Young diagrams, we will draw the points of ^2 arranged with x-coordinate increasing from left to right, and y-coordinate increasing from top to bottom, e.g.

    [ (1,1) (1,2)     ⋯; (2,1) (2,2)      ;     ⋮             ]

Furthermore, we will draw, and refer to, the members of σ as boxes, as usual, and we let |σ| denote the number of boxes in σ.  We shall assume throughout for convenience that σ is a connected shape, i.e. its Hasse diagram is connected (see Remark <ref> on the disconnected case). 

 
A tableau of shape σ is an assignment T of a positive integer, called a label, to each box of σ.  

  * A tableau T of shape σ is semistandard if the rows of σ are weakly increasing from left to right, and the columns of σ are strictly increasing from top to bottom.

  * A tableau T of shape σ is standard if it is semistandard and furthermore each integer 1,…,|σ| occurs exactly once as a label.




<cit.> 
A set-valued tableau of shape σ is an assignment of a nonempty finite set of positive integers  to each box of σ. 

Given sets S,T⊆_>0, we write S<T if max(S)<min(T), and we write S≤ T if  max(S)≤min(T).  Then we extend the definitions of semistandard and standard tableaux to set-valued tableaux.


  * A set-valued tableau T of shape σ is semistandard if the rows of σ are weakly increasing from left to right, and the columns of σ are strictly increasing from top to bottom.

  *  A set-valued tableau T of shape σ is standard if it is semistandard and furthermore the labels are pairwise disjoint sets with union {1,…,r} for some r ≥ |σ|.

Denote by (σ) the set of all semistandard set-valued tableaux on σ.




Let =(c_1,c_2,…) be a nonnegative integer sequence that is eventually zero.  We say that a tableau or set-valued tableau T of shape σ has content = c(T) if label i appears exactly c_i times, for all i.  
Write |T| = |c(T)| = ∑ c_i for the total number of labels.

  


  * For any skew shape σ, the skew Schur function s_σ is

    s_σ =∑_T 𝐱^c(T)

as T ranges over all semistandard fillings of σ.

  * For any skew shape σ, the skew stable Grothendieck polynomial G_σ is

    G_σ =∑_T (-1)^|T|-|σ|𝐱^c(T)

as T ranges over all semistandard set-valued fillings of σ.



Given a set-valued tableau T of shape σ, define the excess of T, denoted e(T), as the vector =  (e_1,e_2,…) in which e_i records the number of labels in row i in excess of the number of boxes in row i.  Therefore |σ|+|e(T)|=|c(T)|.  

 
Definition <ref> does not require σ to be a connected skew shape, but there is little loss of generality in focusing on the connected case, as we do in this paper. If σ is a union of two disconnected parts σ_1, σ_2, then a filling T of σ is semistandard if and only if the resulting fillings T_1 of σ_1 and T_2 of σ_2 are semistandard, since no box in σ_1 is comparable by ≼ to a box of σ_2. Also, c(T) = c(T_1) + c(T_2). It follows that G_σ = G_σ_1 G_σ_2. Hence Grothendieck polynomials of disconnected skew shapes factor into those of connected skew shapes.




§ ROW INSERTION FOR SKEW SET-VALUED TABLEAUX


We now set notation for a refinement of the Grothendieck polynomial based on the excess statistic, and we prove a theorem expressing it linearly in terms of skew Schur functions. Note that the idea of introducing an additional parameter into the Grothendieck polynomial goes back already to <cit.>.

  Let σ be a skew Young diagram.
We define the row-refined skew stable Grothendieck polynomial of σ to be the power series 

    RG_σ(𝐱;𝐰) = ∑_T∈(σ) (-1)^|e(T)|𝐱^c(T)𝐰^e(T).


Thus RG_σ(𝐱;1) = G_σ(𝐱), so the usual skew stable Grothendieck polynomial is obtained as a specialization.


Let μ be a skew Young diagram.


  * A tableau T of shape μ is reverse row-strict if its rows are strictly decreasing from left to right, and its columns are weakly decreasing from top to bottom. 

  * A tableau T of shape μ is row-bounded, respectively row weakly-bounded, if for every box (i,j) in μ, T(i,j) < i, respectively T(i,j)≤ i.



We henceforth adopt the following convention governing containment of Young diagrams. 

Fix σ a skew shape; we take the numbering of the rows of σ to start at 1 at the top.  For another skew shape λ, we write λ⊇σ if every box of σ is a box of λ, and furthermore every box of λ is in the same column as some box of σ. In other words, we will only consider skew shapes λ⊇σ that occupy the same set of columns as σ. They are not allowed to extend σ to the right or to the left.


By Convention <ref>, if σ is a connected skew shape and λ⊇σ, then λ - σ consists of a set of boxes above σ and a set of boxes below σ.  Write A(λ/σ) and B(λ/σ) for these respective skew Young diagrams; A and B stand for above and below.  We emphasize that, contrary to some conventions, λ may extend σ both above and below.



 For any connected skew shape σ, 

    RG_σ(;) = ∑_(μ,) (-1)^| B(μ/σ)| a_σ,μ,· s_μ() ·^

where the sum is over all skew shapes μ⊇σ and sequences , and the numbers a_σ,μ, are nonnegative integers.  Specifically, a_σ,μ, is the number of pairs (T',T”) such that


  * T' is a row-weakly bounded semistandard tableau on A(μ/σ), and

  * T” is a reverse-row-strict, row-bounded tableau on B(μ/σ), 

satisfying 
    c(T') + c(T”) = .



For convenience, we record the coefficient-by-coefficient interpretation of Theorem <ref>.  Let _,(σ) denote the set of semistandard set-valued fillings of σ of content  and excess .

  Let σ be any connected skew shape, and fix sequences  and .  Then 

    |_,(σ)| = ∑_μ⊇σ  (-1)^|A(μ/σ)|· a_σ,μ,· |_, 0 (μ)|,

where a_σ,μ, are the nonnegative integers defined in Theorem <ref>.


Thus Theorems  <ref> and <ref> are equivalent.

The change from B(μ/σ) in Theorem <ref> to A(μ/σ)  in Theorem <ref> is not accidental; it arises from the definition of RG as a signed generating function for set-valued semistandard tableaux.

Then, by specializing to = 1 in Theorem <ref>, we obtain Theorem <ref>.
















 
Consider the row-bounded, reverse row-strict tableaux of shape B(μ/σ), as in (2) above. There is a bijection between this set and the set of row-bounded, row- and column- strictly-decreasing tableaux of shape B(μ/σ), obtained by replacing label T(i,j) with i-T(i,j).  Therefore, when σ is a straight shape whose highest row is in row 1, Theorem <ref> reduces to <cit.>.  In particular, A(μ/σ) is always empty in this case.  

We also note that when N=|σ|+1, Theorem <ref> specialized to the monomial x_1⋯ x_N is equivalent to <cit.>.
Moreover a proof using a row insertion algorithm in the special case that σ is a straight shape and N=|σ|+1  is presented in <cit.>.






The determinantal formula of <cit.> can also be expanded as a similar sum involving enumeration of standard young tableaux on larger skew shapes (see <cit.>).
Thus, Theorem <ref> establishes in a purely combinatorial manner that the determinantal formula in  <cit.> is equal to the number of set-valued tableaux.



D. Grinberg has pointed out the row-refined skew stable Grothendieck polynomials RG_σ(𝐱;𝐰) in Definition <ref>, restricted to straight shapes σ, are Hall-dual to the power series g̃_μ(𝐱;𝐰) defined in <cit.>.  In other words, 

    ⟨ RG_σ(𝐱;𝐰), g̃_μ(𝐱;𝐰)⟩ = δ_σ,μ

for straight shapes σ and μ. Here ⟨·,·⟩ denotes the Hall inner product on symmetric functions in variables 𝐱, treating the w_i as scalars. 






Now we prove Theorem <ref> using a new generalized row insertion algorithm.  This proof occupies the rest of the section.  This algorithm extends the set-valued insertion algorithm in <cit.> to the case of skew shapes. 

(RSK row insertion) First, recall the row insertion operation, the atomic operation of the RSK algorithm <cit.> (we present a very slightly more general version). Suppose σ is a skew or straight shape and T is a semistandard tableau of shape σ.  Given k∈ and i, the operation T←_i k inserts k in the leftmost box of row i labeled j>k, or a new box at the right end of the i^th row if no box in that row is labeled >k (in the case where there are not yet any boxes in that row, the new box is placed directly below the leftmost entry in the previous row).  In the latter case the operation terminates. In the former, we insert j into the (i+1)^st row of σ in the same manner, and repeat down the rows of σ.  The insertion path is the sequence of boxes b_i,j_1,b_i+1,j_2,… in which insertions occurred; one can check that j_1 ≥ j_2 ≥⋯ <cit.>.


In particular, row insertion inputs a semistandard tableau of shape σ and outputs a semistandard tableau of shape σ' obtained by adding one box to σ.


Notice that row insertion may be applied without changes to set-valued tableaux in the following situation.  Suppose T is a set-valued semistandard tableau of shape σ.  Suppose k is a label in a box b with at least one other label; let i index the row containing b.  Suppose further that every box in row i+1,i+2,… is labeled with a singleton set.  Then one may define the operation T←_i k as before, deleting k from box b and row-inserting it in the next row, and repeating.  Simply put, the row insertion path does not traverse any box with more than one label in this case.

This observation allows for the next algorithm.




The algorithm proceeds as follows.  Let r be the number of rows of σ. For each k=r,…,1 (in descending order), we will do two “sweeps” of σ. First we sweep out all labels in row k that are not the minimum in their box, via row-inserting them downward. Then we sweep out all labels in all (singly-labeled) boxes b for which T'(b) = k, again via row insertion.  These boxes need not be in row k.  In the auxiliary labeling T”, the newly created boxes are labeled k, and properties of row insertion will imply that at most one box in each column of T” is labeled k. An example is given in Example <ref>.  

Now we describe the algorithm more precisely. For k=r,…,1, proceed as follows.  First, let m be the maximum label in the rightmost box of row k that has multiple labels.  Delete m and insert m into the leftmost box of row k+1 labeled m_2>m, or a new box at the right end of the k+1^st row if no box in that row is labeled >m.  In the latter case the operation terminates; the new box is labeled k in the auxiliary filling T”. In the former, we insert m_2 into the (k+2)^nd row of σ in the same manner, and repeat down the rows of σ.  This is the familiar row-insertion operation of Definition <ref>.  The insertion path is the sequence of boxes b_0 = (k,j_0),b_1=(k+1,j_1),… in which insertions occurred; one can check that j_0 ≥ j_1 ≥⋯ (<cit.>).  Repeat row-insertion on the maximum label in the rightmost non-singly valued box in row k, until that row has only singly-valued boxes.  

The second part of step k is as follows.  Since T' is row-weakly-bounded and reverse row-strict, it follows that there is at most one box (i,j)∈ A(λ/σ) in each row such that T'(i,j)= k; furthermore i≥ k if so, so that T(i,j) must consist of a single label.  So for each such box (i,j), taken in order with i increasing, delete the box and row-insert the label T(i,j) it starting in row i+1.  When the operation terminates, the new box is labeled k in the auxiliary filling T”.  We note for later use that in this stage, every box labeled k in T” is the leftmost of its row, since all boxes labelled >k have already been removed.



Let 
    σ = (:: ,:: ,:  ,  )     λ = (:  ,   ,   ,  )      T' = (:1,21,1)      T=
    boxsize=.75cm    2    3
    
     1,4     6     8 
    
     5,7     9     10,13
    
     11     12
     .

The algorithm gives


    boxsize=.5cm    2    3
    
     1,4     6     8 
    
     5,7    9     10 
    
     11     12    13        2    3
    
     1,4    6     8 
    
     5     9     10 
    
     7     12    13
    11        2    3
    1    6     8 
    
     4     9     10 
    
     5     12    13
    7
    11       2   3
        6     8 
    
     1     9     10 
    
     4     12    13
    5
    7
    11          3
       2    8 
    
     1     6     10 
    
     4     9    13
    5   12
    7
    11          3
           8 
    1    2     10 
    
     4     6    13
    5   9
    7   12
    11          3
           8 
        2     10 
    
     1     6    13
    4   9
    5   12
    7
    11

and the auxiliary tableau T” is 
    (::3,31,21,2,1)






The output of Algorithm <ref> takes the claimed form.



We remark that the process in Algorithm <ref> preserves the property that every box in row k+1 and below has exactly one label in it, so the row-insertion is always well-defined.  The process also clearly preserves the content of the tableau T. Thus iterating the described two-step process for k=r,…,1 produces the output data μ, T”, and T, with c(T) = c(T). Furthermore T” is row-bounded since T' was row-weakly-bounded. To conclude that the output is as claimed, the only thing left to show is that the labeling T” of B(μ/σ) is reverse row-strict.

 Indeed, since the rows are processed in the order r,…,1 in Algorithm <ref>, it is enough to show that for a fixed k∈{1,…,r} that no two boxes labelled k in T” lie in the same row.  This follows from the standard fact that row-insertion paths move weakly to the left. Precisely: Suppose m and m' are labels that are processed consecutively in step k.  Let b_0,b_1,… b_M be the insertion path of m.  By assumption, after m is inserted, every box b_i except possibly b_0 is still singly labeled, and max(T(b_0)) < T(b_1) < … < T(b_M). 

Furthermore, we claim that the label m' is on or to the left of the insertion path of m.  Indeed, if m' is also in row k, then this is clear since m'<m; otherwise, we simply note that m' is in the leftmost box of its row, so the claim is also clear.  Finally, row-insertion of m' preserves the property of being weakly left of the insertion path of m.  So the insertion path of m' cannot end to the right of that of m'; thus it ends below that of m'. This concludes the proof of the lemma.


Now we show that all possible outputs are attained bijectively by the algorithm.

 
For any connected skew shape σ and any  and , Algorithm <ref> produces a bijection between choices of 


  * a skew shape λ⊇σ with B(λ/σ)=∅,

  * T' a reverse-row-strict, row-weakly-bounded tableau on A(λ/σ), and

  * T∈_,-c(T')(λ);

and choices of


  * a skew shape μ⊇σ with A(μ/σ)=∅,

  * T” a reverse-row-strict, row-bounded tableau on B(μ/σ) with c(T”)=, and

  * T∈_,(μ).

Therefore, 


    ∑_(λ, T') |_, -c(T')(λ)| = ∑_(μ,T”) |_, 0(μ)|

where


  * the left hand sum ranges over all λ⊇σ with B(λ/σ)=∅, together with a reverse row-strict, row-weakly-bounded labeling T' of A(λ/σ), and

  * the right hand sum ranges over all μ⊇σ with A(μ/σ) = ∅, together with a reverse row-strict, row-bounded labeling T” of B(μ/σ).




 The skew set-valued row-insertion algorithm in Algorithm <ref> constructs a map

    ∐_(λ, T')_, -c(T')(λ) ∐_(μ,T”)_, 0(μ),

where the conditions on λ,μ,T', and T” are as in the statement of the proposition. We claim this map is a bijection, and it suffices to provide an inverse.  The inverse may be described algorithmically as follows.  Given μ, T”, and T satisfying conditions (1), (2), and (3) described as the output of Algorithm <ref>, perform the following procedure for k=1,…, r.  Consider the boxes of B(μ/σ) labelled k in T”, in order from highest to lowest row number (i.e. lowest to highest on the page).  For each such box b, delete b and inverse-row-insert its label m upwards, stopping if it reaches row k.  If the label m lands in a new box b', necessarily in row ≥ k, then set T'(b) = k.  An example is given in Example <ref>, read in reverse.

The resulting tableau T' is reverse-row-strict by an argument  analogous to Lemma <ref>.  So the result of this procedure is the data λ,T', and T satisfying the conditions (1), (2), and (3) described as the input  of Algorithm <ref>. 
Now it is evident that the procedure described is in fact inverse to the RSK map in Algorithm <ref>, since each upwards insertion operation is inverse to row insertion, and it processes boxes in the reverse order.


Now we state 
a Definition and 
Lemma, which will be used to prove Theorem <ref>. We will postpone its proof until after the the proof of Theorem <ref>.  The need for Definition <ref> as a hypothesis for Lemma <ref> was pointed out to us by D. Grinberg.



Let P be any finite poset, with its set of cover relations C = {(x,y)∈ P× P: x⋖ y} partitioned into two disjoint sets C=G⊔ B (called good and bad, colloquially).  We will say that the partition is acyclic if the directed graph on the Hasse diagram of P obtained by orienting all good cover relations up and all bad cover relations down is acyclic.

The partition G⊔ B of the cover relations in the Hasse diagram is drawn below is not acyclic.

    @R=6mm@C=6mm   ∙@-[dl]_G@-[dr]^B   
    ∙@-[dr]_G       ∙@-[dl]^B
       ∙



Let P be any finite poset, 
with its set of cover relations C = {(x,y)∈ P× P: x⋖ y}.  Let C=G⊔ B be an acyclic partition of C, with elements of G and B called good and bad throughout.  
Say that an increasing sequence

    ℐ = (∅ = I_0 ⊊⋯⊊ I_ℓ = P)

of order ideals I_i is a G-sequence if for every i=1,…,ℓ, the only cover relations within I_i ∖ I_i-1 are in G.  Precisely: if x,y∈ I_i ∖ I_i-1 and x⋖ y then (x,y)∈ G.  The length of such a G-sequence ℐ is defined to be |ℐ|=ℓ.
Then 



    ∑_ℐ a G-sequence (-1)^|ℐ| = 
    (-1)^|P|   if G=∅,
    
    0    otherwise.




Suppose P = P(λ) is the poset of boxes of a diagram λ.  If G=∅ then the G-sequences are in natural correspondence with increasing tableaux of shape λ with label set {1,…,N} for some N.  Lemma <ref> states that counting these increasing tableaux, with sign according to the parity of N, is (-1)^|P|.  For example, if P=P((3,1)) then the Lemma states that 

    (-1)^4 = #{(123,4),(124,3), (134,2) } - #{(123,3) ,(123,2)}.



Postponing the proof of Lemma <ref>, we now prove Theorem <ref>.  

  

We fix σ and sequences  and , with || = |σ| + ||; otherwise the statement is trivial.    Now isolating the term  |_, (σ)| on the left of Equation (<ref>), we have

    |_, (σ)| = ∑_(μ,T”) |_, 0(μ)| - ∑_(λ, T'): λ⊋μ |_, -c(T')(λ)|

where the conditions on (μ,T”) and (λ,T') are as stated in Proposition <ref>.  Now we may use Proposition <ref> inductively to expand each of the terms |_, -c(T')(λ)| in the second sum of Equation (<ref>).  We obtain

    |_, (σ)| = ∑_(μ,T',T”) b_σ,μ,T',T”· |_, 0(μ)|,

 for some coefficients b which we will soon study. Here


  * μ⊇σ is a skew shape,

  * T' is any row-weakly-bounded filling of A(μ/σ), 

  * T” is a reverse-row-strict, row-bounded filling of B(μ/σ),

such that

    c(T') + c(T”) = .


To prove Theorem <ref> it is enough to show that the coefficients on the right hand side are given by

    b_σ,μ,T',T” = 
    (-1)^|A(μ/σ)|    if T' is semistandard, 
     
    0     otherwise.


Indeed, it follows from the recursive expansion of Equation (<ref>) that the coefficient b_σ,μ,T',T” depends only on T': it is
the signed count of the number of ways to build T' as a sequence of tableaux

    ∅ = T_0 ⊊ T_1 ⊊⋯⊊ T_ℓ = T'

on a corresponding sequence of skew shapes

    ∅ = λ_0 ⊊λ_1 ⊊⋯⊊λ_ℓ = A(μ/σ)

 such that each λ_i is obtained from λ_i-1 by adding boxes on the left or above boxes of λ_i-1, and the restriction of T_i to λ_i/λ_i-1 is reverse row-strict for each i.  By the signed count, we mean that such a sequence is counted with sign (-1)^ℓ.   

For example, a filling T' =  
    (21,22)
 can be obtained in the following ways, with the following signs:




(  ,  )     (  , 2)     (  ,22)     ( 1,22)     (21,22)    +




(  ,  )     (  , 2)     ( 1, 2)     ( 1,22)     (21,22)     +




   (  ,  )     (  , 2)     ( 1,22)     (21,22)    -




   (  ,  )     (  , 2)     (  ,22)     (21,22)     -




and so b_σ,μ,T',T” = 0 for this T'.

Thus, to compute b_σ,μ,T',T” in general, we let P=P(A(μ/σ)) be the poset whose elements are boxes of A(μ/σ) and such that b_1⋖ b_2 if and only if box b_1 is directly to the right of or directly below b_2. Now let G be the subset of cover relations b_1⋖ b_2 of P in which either


  * b_1 is directly to the right of b_2 and T'(b_2) > T'(b_1), or

  * b_1 is directly below b_2 and T'(b_2) ≥ T'(b_1).

Let B be the set of cover relations not in G.  Observe that G and B are an acyclic partition of the cover relations, in the sense of Definition <ref>.  Indeed, a cycle in the oriented Hasse diagram, say on boxes b_0,b_1,…,b_t=b_0 would correspond to a sequence of inequalities T(b_0) ≤ T(b_1) ≤⋯≤ T(b_t) = T(b_0), and since the boxes b_0,…,b_t occupy more than one row and one column,  at least one (in fact at least two) of those t inequalities are strict, which is clearly impossible.
Then by Lemma <ref> it follows that 

    b_σ,μ,T',T” = 
    (-1)^|A(μ/σ)|    if G=∅, 
     
    0     otherwise.

But G=∅ means precisely that T' is semistandard.  











It remains only to prove Lemma <ref>.
 We prove Lemma <ref> by induction on |P|, with P=∅ being obvious.  

Write J(P) for the set of order ideals of P. 
We break up (<ref>) according to the first order ideal I_1 and proceed inductively on P∖ I_1.  Start with the equality

    ∑_ℐ a G-sequence (-1)^|ℐ| = ∑_∅ A ∈ J(P)  ∑_ℐ a G-sequenceI_1=A (-1)^|ℐ|.

Notice that for any order ideal A, the partition on the cover relations of P∖ A induced by G⊔ B is again acyclic.  Then by induction, the nonzero contributions to the right hand side of (<ref>)  come from nonempty order ideals A in which 


  * all cover relations inside A are good,

  * all cover relations inside P∖ A are bad.

Let 𝒜 be the set of nonempty order ideals of P satisfying these conditions.  Then using (<ref>) inductively, (<ref>) becomes

    ∑_ℐ a G-sequence (-1)^|ℐ| = ∑_A∈𝒜  (-1)· (-1)^|P∖ A|.


It remains to identify 𝒜 in terms of P and G, which we do as follows. Let Y be the maximal up-closed subset of P such that all cover relations within Y are bad.  Note that Y is uniquely defined, since if Y_1 and Y_2 are up-closed subsets satisfying that condition, then Y_1∪ Y_2 also satisfies the condition.  

Let X = P∖ Y.  Let Y'⊆ Y be the subset consisting of the minimal elements y∈ Y satisfying that if x⋖ y then (x,y)∈ G. 
Then we claim 


  * If X = ∅ then 𝒜 = {I ⊆min(P): I∅}, where min(P) denotes the minimal elements of P.

  * If X∅ and some cover relation within X is in B, then 𝒜=∅.

  * If X∅ and all cover relations within X are in G, then

    𝒜 = {X∪ I: I⊆ Y'}.





 If X=∅ then G=∅, and 𝒜 then consists of all nonempty order ideals with no cover relations within them. So part (1) follows.

Suppose X∅.  Suppose A∈𝒜. Now for each maximal element x∈ X, there is some y∈ Y such that x⋖ y is good.  So necessarily x∈ A, since otherwise the covering relation x⋖ y would lie in P∖ A.  So A contains all maximal elements of X; thus A⊇ X.   So if some cover relation within X is in B, then 𝒜=∅, proving part (2).  

Otherwise, we see that X∈𝒜.  Furthermore, if A∈𝒜 then A∩ Y must be an antichain in Y; otherwise A contains a bad cover relation.  So A∩ Y⊆min(Y).  And if y∈ A∩ Y, then any cover relation x⋖ y must be good.  We conclude that 𝒜⊆{X∪ I: I⊆ Y'};  the reverse containment also clearly follows.


Now from Claim <ref>, the rest of the proof of Lemma <ref> can be deduced from (<ref>) by using the obvious identity 
∑_S⊆ T (-1)^|S| = 0
for nonempty finite sets T.  Explicitly, in the case <ref>(1), Equation (<ref>) becomes 

    ∑_∅ A ⊆min(P)  (-1)·(-1)^|P∖ A| = (-1)^|P|.

In the case <ref>(2), Equation (<ref>) is the empty sum.  
In the case <ref>(3), Equation (<ref>) becomes

    ∑_I⊆ Y'  (-1)·(-1)^|P∖(X ∪ I)| = (-1)^|P|+1∑_I⊆ Y' (-1)^|I|,

which is 0, as desired, provided that Y'∅. It remains only to show that Y'=∅ is not possible.

If Y'=∅ then by definition of Y', every minimal element y∈ Y covers some x∈ X such that x⋖ y is bad. And every maximal element x∈ X is covered by some y ∈ Y such that x⋖ y is good.  Therefore in the orientation of the Hasse diagram of P described in Definition <ref>, every element in X sends out an upwards edge, and every element in Y sends out a downwards edge. Therefore the oriented Hasse diagram has no sink and cannot be acyclic, contradicting the hypotheses.







§ AN INVERSE FORMULA




We give an analogous linear expansion of skew Schur functions into skew stable Grothendieck polynomials. This formula generalizes <cit.>, which pertains to straight shapes, and visibly specializes to that result when σ is a straight shape. 


For any connected skew shape σ, 

    s_σ = ∑_μ⊇σ (-1)^|A(μ/σ)| b_σ,μ· G_μ

where the b_σ, μ is the product of the following two numbers:


  * the number of row-weakly-bounded, reverse-row-strict tableaux of shape A( μ/σ), and 

  * the number of row-bounded, semistandard tableaux of shape B(μ/σ).




Fix σ. By Theorem <ref>, the right hand side of (<ref>) is

    ∑_μ⊇σ∑_λ⊇μ (-1)^|A(μ/σ)|+|B(λ/μ)| a_λ,μ· b_μ,σ· s_λ

And a_λ,μ· b_μ,σ is the product of the sizes of the following two sets:


  * the row-weakly-bounded tableaux T' on A(λ/σ) which are semistandard on A(λ/μ) and reverse-row-strict on A(μ/σ), and

  * the row-bounded tableaux T” on B(λ/σ) which are reverse-row-strict on B(λ/μ) and semistandard on B(μ/σ).
 

Now for a fixed λ, a row-weakly-bounded filling T' of A(λ/σ), and a row-bounded filling T” of B(λ/σ), the contribution of the triple (λ,T',T”) to the sum (<ref>) is

    ∑_μ with σ⊆μ⊆λ
    T',T” satisfy (1),(2)
     (-1)^|A(μ/σ)|+|B(λ/μ)|·  s_λ


Now if λ = σ then (<ref>) equals s_σ vacuously.  Otherwise, we show that (<ref>) vanishes. In words, the coefficient of s_λ in (<ref>) is a signed count of ways to divide the two shapes A(λ/σ) and B(λ/σ), such that in each, the upper-left is semistandard and the lower-right is reverse-row-strict.  Then the following lemma, applied to A(λ/σ) and B(λ/σ), finishes the proof of Theorem <ref>. 



Let μ be any nonempty skew shape. A division of μ is a partition μ = μ_S ⊔μ_R into two skew shapes such that μ_S is an order ideal of μ considered as a poset (Definition <ref>).  In other words, no box of μ_R is north/west of any box of μ_S.
Suppose T is a (non-set-valued) tableau on μ.  Say that (μ_S,μ_R) is allowed by T if T is semistandard on μ_S and reverse-row-strict on μ_R.  Then

    ∑_(μ_S,μ_R)  allowed by T (-1)^|μ_S| = 0.



If T = (a_1,…,a_n) is a tableau on a single row of length n, then the above sum is empty unless a_1 ≤⋯≤ a_M > ⋯ > a_n for a unique index M. In this case, there are two allowable divisions: where μ_S is either the first M or the first M-1 boxes.


Each cover relation b_1 ⋖ b_2 in μ may be labelled S or R according to whether the restriction of T to the 2-box shape {b_1,b_2} is semistandard or is reverse-row-strict. In the first case, write S in box b_1; in the second case, write R in box b_2. In this way, fill the boxes of μ using the alphabet {∅, S, R, SR}.  (In Example <ref>, the first M-1 boxes are S, the next box is empty, and the remaining are R.)  

Now if there are any allowable divisions at all, then no box is labelled SR, the S boxes must be an order ideal, the boxes containing R must be the complement of an order ideal, and the empty boxes form an antichain in between.  Then (μ_S,μ_R) is allowable if and only if μ_S contains all S boxes and μ_R contains all R boxes.  Then to prove the lemma, it is enough to show that there exists at least one empty box.  Consider, among all boxes with maximum number in T, an upper-rightmost one.  That box has empty label.







Acknowledgments. We thank Vic Reiner, Bridget Tenner and Alexander Yong for generously answering some questions over email about their work <cit.>. We also thank Jennifer Morse, Travis Scrimshaw, and an anonymous referee for helpful contextual remarks and references.   We are grateful to Darij Grinberg for correcting an earlier error in the formulation of Lemma <ref>, and for other detailed comments.
MC was supported by an NSA Young Investigators Grant and NSF DMS-1701924.










amsalpha




