Robinson-Schensted correspondence for unit interval orders
Dongkwan Kim Pavlo Pylyavskyy
math.CO

  
The Stanley-Stembridge conjecture associates a symmetric function to each natural unit interval order 𝒫. In this paper, we define relations à la Knuth on the symmetric group for each 𝒫 and conjecture that the associated 𝒫-Knuth equivalence classes are Schur-positive, refining theorems of Gasharov, Brosnan-Chow, Guay-Paquet, and Shareshian-Wachs. The resulting equivalence graphs fit into the framework of D graphs studied by Assaf. Furthermore, we conjecture that the Schur expansion is given by column-readings of 𝒫-tableaux that occur in the equivalence class. We prove these conjectures for 𝒫 avoiding two specific suborders by introducing 𝒫-analog of Robinson-Schensted insertion, giving an answer to a long standing question of Chow. 





Charged multi-hadron systems in lattice QCD+QED
    J. M. Zanotti
    Received 29 November 2019 / Accepted 07 March 2020
======================================================






 	
 	



§ INTRODUCTION

Since its formulation in 1993, Stanley-Stembridge conjecture <cit.> has been one of the most intriguing problems in algebraic combinatorics. Interest in it was greatly strengthened when Shareshian and Wachs <cit.> related the conjecture to Hessenberg varieties. The original conjecture was shown by Guay-Paquet <cit.> to be equivalent to saying that chromatic symmetric functions of incomparability graphs of unit interval orders are positive combinations of elementary symmetric functions. Shareshian and Wachs realized that essentially the same symmetric functions arise as Frobenius characters of actions of symmetric groups on cohomology rings of Hessenberg varieties, as studied by Tymoczko <cit.>. Shareshian-Wachs conjecture was proved by Brosnan and Chow <cit.>, and independently by Guay-Paquet <cit.>. On the combinatorial level the results of Brosnan-Chow and Guay-Paquet imply a graded refinement of the Schur positivity result of Gasharov <cit.>. It also provides useful tools to understand combinatorics in terms of geometry, i.e. theory of perverse sheaves and geometric properties of (regular) Hessenberg varieties.

The original Stanley-Stembridge conjecture, nowadays usually stated in terms of positivity in complete homogenous symmetric functions, remains open except for special cases, see Gebhard-Sagan <cit.>, Dahlberg-van Willigenburg <cit.>, Harada-Precup <cit.>, Cho-Huh <cit.>, Cho-Hong <cit.>, etc.

In an independent development, Assaf <cit.> has introduced a beautiful theory of D graphs to address Schur positivity questions in symmetric functions, such as Macdonald polynomials, LLT polynomials, and k-Schur functions. While as shown by Blasiak <cit.> getting exactly the right axiomatization to address those questions can be very challenging, Assaf's work provides a very useful framework. In particular her characterization of dual equivalence graphs has been used in a variety of contexts, see for example Chmutov <cit.> and Roberts <cit.>. Assaf's ideas were further developed by Blasiak-Fomin <cit.> and others. 

In this paper we combine the two lines of research. Specifically, for each unit interval order  we define an analog of Knuth moves. The resulting -Knuth equivalence classes of permutations satisfy correct axioms to fit into the framework of D graphs. We conjecture that via the standard map from permutations to quasisymmetric functions the images of -Knuth equivalence classes are symmetric and Schur positive. This is a refinement of results of Gasharov, Brosnan-Chow, and Guay-Paquet. Furthermore, we conjecture that the decomposition into Schur functions can be read off from column reading words of -tableaux that occur in the equivalence class. 

We prove this Schur positivity conjecture for a special class of unit interval orders . For that purpose we introduce an analog of Robinson-Schensted insertion that preserves descents, solving an open problem dating back to the works of Sundquist-Wagner-West and Chow. The 1997 work of Sundquist-Wagner-West <cit.> constructs a version of Robinson-Schensted insertion for unit interval orders, however in general their algorithm does not preserve descents, and thus cannot be used to derive Schur positivity results. Chow <cit.> proved that Sundquist-Wagner-West does preserve descents under a very restrictive condition — in our terminology his condition is to avoid a suborder isomorphic to  _(2,1),4. Chow implicitly states in his paper the question of constructing Robinson-Schensted correspondence that preserves descents when  avoids a  less restrictive pattern  _(3,1,1),5. In this paper we solve this problem for unit interval orders that avoid both  _(3,1,1),5 and  _(4,2,1,1),6. As a result, in those cases we are able to prove Schur positivity of the  -Knuth equivalence classes.

This project started as an attempt to prove Stanley-Stembridge conjecture. This goal remains elusive, as it would require introducing an affine analog of  -Knuth equivalence classes and proving their h-positivity. We expect this to be strictly harder than proving Schur positivity of the -Knuth equivalence graphs introduced in this paper, and even that remains open in full generality. Nevertheless, -Knuth equivalence classes seem to be interesting objects of their own, perhaps having geometric meaning in terms of (equivariant) cohomology and moment graphs of Hessenberg varieties. We hope that understanding -Knuth equivalence classes, and in particular proving Conjecture <ref>, will shed new light on Stanley-Stembridge conjecture. 

The paper proceeds as follows. In Section <ref> we recall some standard combinatorial notions such as partitions, partial orders and tableaux. In Section <ref> we recall properties and characterizations of natural unit interval orders. We also introduce an important class of natural unit interval orders called ladders, as well as  ladder-climbing property. In Section <ref> we introduce -Knuth equivalence classes and state the main theorem <ref>. In Section <ref> we introduce column insertion procedure, which is then used in Section <ref> to define the full -Robinson-Schensted insertion algorithm. Section <ref> is filled with examples illustrating everything introduced in the previous sections. In Sections <ref> and <ref> we give proofs of the results from previous sections. 




§ DEFINITIONS AND NOTATIONS
 

For a, b ∈, we set [a,b]{x ∈| a≤ x ≤ b}. For a set X, we let |X| be its cardinal.





 §.§ Partitions

A partition is a finite sequence of integers λ=(λ_1, λ_2, …, λ_a) such that λ_1≥λ_2 ≥⋯≥λ_a >0. In such a case, we set its length to be a (denoted l(λ)) and its size to be λ_1+λ_2+⋯+λ_a (denoted |λ|). When |λ|=n, we also write λ⊢ n. If i > l(λ), we set λ_i=0. We write λ' to denote the conjugate partition of λ. We define the staircase partition (n) to be (n-1, n-2, …, 2, 1). For two partitions λ and μ, we write λ⊂μ if λ_i≤μ_i for all i ∈_>0. Pictorially, it means that the Young diagram of μ contains that of λ.




 §.§ Partial orders
 We use the symbols ≥, >, ≤, and < for the usual order on . However, throughout this paper we discuss various partial orders, for which new symbols are necessary in order to avoid conflict. Namely, suppose that a partial order  on [1,n] is given. For a,b∈ [1,n], we write



  * a  b (or b  a) if a is smaller than b with respect to ,

  * a  b (or b  a) if a<b and a  b,

  * a  b (or b  a) if a<b but a b, and

  * a _ b if a and b are not comparable with respect to  (and a≠ b).

If there is no confusion we drop the subscript _ from each symbol.


For a partial order  on a set X and its subset Y ⊂ X, the restriction of  to Y, denoted |_Y, is well-defined. For two partial orders  on [1,n] and ' on [1,m], we say that  avoids ' or  is '-avoiding if restriction of  to any subset of [1,n] (of cardinal m) is not isomorphic to '.



 §.§ Symmetric groups and words
 In this paper, a word means a finite sequence. For a word α=(α_1, α_2, …, α_k), we also write α=α_1α_2⋯α_k to simplify notations. For a word α, we denote by α the corresponding underlying set. We let |α|∈ be the length of α. If |α|=0, then we also write α=∅. By a subword of α, we mean a word (α_i_1, α_i_2, …, α_i_s) such that 1≤ i_1<i_2<⋯<i_s≤ k. For two words α and β, we define α+β to be their concatenation. 


Let _n be the symmetric group permuting [1,n]. We identify elements in _n with the words in which each of 1, 2, …, n appears once. For w=w_1w_2⋯ w_n ∈_n and a partial order  defined on [1,n], we set 


  * its -descent to be _(w) = {i ∈ [1,n-1] | w_i w_i+1},

  * its genuine -inversion to be 

    _(w) =   {(i,j) ∈ [1,n]^2 | i  j, i appears before j in w,
    
        and there do not exist any subword  ia_1a_2⋯ a_kj  of w such that 
        i _ a_1 _ a_2 _⋯_ a_k _ j},


  * its (genuine) -height to be (if _(w) =∅ then _(w)=1 and otherwise)

    _(w) = max{k ∈|    there exist  a_1, a_2, …, a_k-1, a_k  such that 
        (a_1, a_2), …, (a_k-1,a_k) ∈_(w)},


  * its fake -inversion to be _(w)={(i,j) ∈ [1,n]^2| i  j, w^-1(i)<w^-1(j)}, and

  * its (fake) -inversion number to be |_(w)|.

For example, if  is the usual order on [1,n] then _(w) is the set of usual inversions in w, (w) is the length of the longest decreasing subword of w, and _(w) = ∅. On the other hand, if  is the trivial order on [1,n] then _(w)=∅, _(w) = 1, and _(w) is the set of usual inversions in w. In addition, if  is defined with respect to the Hasse diagram in Figure <ref> and w=(9,5,1,8,4,7,3,6,2) then 


  * _(w)={1, 2, 4, 6, 8}, 

  * _(w)={ (9,5), (9,4), (9,3), (9,2), (9,1),  (8,4), (8,3), (8,2),  (7, 3), (7,2), (6, 2), (5,1)},

  * _(w)=3 (= the length of (9,5,1)),

  * _(w)={(3,2), (4,3), (5,3), (5,4), (7,6), (8,6), (8,7), (9,8)}, and

  * |_(w)|=8.

 We adopt the convention that if i→ j in the Hasse diagram of an order  then i is greater than j with respect to , which is in accordance with the notation i  j.









 §.§ Standard and -tableaux
 A tableau T is said to satisfy the -tableau condition if for two entries i,j ∈ [1,n] adjacent in T, (1) if i is above j then i j, and (2) if i is left to j then i j.
That is, entries in T are increasing along columns and nondecreasing along rows with respect to . 
Such a tableau T is called a -tableau if in addition it contains each entry of [1,n] exactly once.
(Note that our definition is a conjugated version of the one in <cit.>.) We denote by _n (resp. _λ) the set of -tableaux of size n (resp. of shape λ). Similarly, we denote by _n (resp. _λ) the set of standard Young tableaux of size n (resp. of shape λ). Note that if  is the usual order on [1,n] then -tableaux are exactly standard Young tableaux.

smalltableaux
For a tableau T, we often identify each of its columns with its reading word from bottom to top and also identify T with the sequence of its columns. In addition, we define the reading word of T, denoted (T), to be the concatenation of column reading words from bottom to top. We define the descent of T∈_n to be (T) ={i ∈ [1,n-1]| i  i+1}. For example, if T=1358,267,4 then T is identified with ((4,2,1), (6,3), (7,5), (8)), the reading word of T is (T)=(4,2,1,6,3,7,5,8), and (T)={1, 3, 5}.

For a partial order  on [1,n] and T∈_n, we define its fake -inversion to be _(T)={(i,j) ∈ [1,n]^2| i  j,  the column of  i  is left to that of  j} and its fake -inversion number to be |_(T)|. Since each column of a -tableau is a chain in , it is easy to show that _(T)=_((T)) for any -tableau T. For example, if  is given again by Figure <ref> and T=1432,5876,9  then _(T)=_((T))={(3,2), (4,3), (5,3), (5,4), (7,6), (8,6), (8,7), (9,8)}, and thus |_(T)|=8.




 §.§ Schur and fundamental quasi-symmetric functions
 For a partition λ, we set s_λ to be the Schur function corresponding to λ. For a composition μ, we set F_μ to be the fundamental quasi-symmetric function corresponding to μ defined by Gessel.




§ NATURAL UNIT INTERVAL ORDER
 
In this section we recall the notion of natural unit interval orders and some of its properties. Also, we introduce a ladder order which plays a prominent role in this paper.


 §.§ Three equivalent definitions of natural unit interval orders
 Here we define natural unit interval orders in three different ways. We refer readers to <cit.> for the proof that these definitions are indeed equivalent.


  §.§.§ Definition in terms of unit intervals
 
 We say that  on [1,n] is a natural unit interval order if it there exist n real numbers y_1<y_2< ⋯<y_n such that i j ⇔ y_i+1<y_j.

Pictorially, one may regard y_1, …, y_n as the starting points of unit intervals I_1=[y_1, y_1+1], I_2=[y_2, y_2+1], …, I_n=[y_n, y_n+1]. Then the above definition translates to the following.


  * If i<j, then I_i should start before I_j in the real line.

  * We have i j if and only if I_j starts after I_i ends in the real line.

For example, Figure <ref> shows an arrangement of unit intervals and the corresponding natural unit interval order.





  §.§.§ Definition using partitions
 For n ∈_>0, let λ be a partition contained in (n). We define the partial order _λ,n on [1,n] such that a b if and only if a≤λ_n+1-b. In other words, we have [1, λ_i]={x ∈ [1,n] | x  n+1-i}. For example, when n=5 and λ=(3,1) then _λ,n is given as in Figure <ref>.



We say that a partial order  on [1,n] is a natural unit interval order if =_λ, n for some λ⊂(n).




  §.§.§ Defining properties
 One may also define natural unit interval orders by imposing certain conditions on a partial order, namely:
 We say that a partial order  on [1,n] is a natural unit interval order if


  * the usual order is a linearization of , i.e. if a  b then a<b, and

  * if b  c, a _ b, and a_ c, then b<a<c. 


Because of the first condition, , are equivalent to , when we consider natural unit interval orders. From now on we usually use the former rather than the latter for such orders. Also, hereafter we refer to the second condition as . For example, if  is a natural unit interval order and a, b, c ∈ [1,n] satisfy b c and a<b, then a  c by .




 §.§ (3+1) and (2+2) avoidance

There is another characterization of natural unit interval orders in terms of suborder avoidance. Indeed, it is essentially proved in <cit.> that a partial order  on [1,n] is a natural unit interval order if and only if the usual order is a linearization of  and  avoids suborders “(3+1)” (disjoint union of a chain of length 3 and an element) and “(2+2)” (disjoint union of two chains of length 2). Here we prove only one direction which will be useful later on.
  Suppose that  is a natural unit interval order on [1,n]. Then,


  * there does not exist a,b,c,d ∈ [1,n] such that a b c, a_ d, and d_ c, and

  * there does not exist a,b,c,d ∈ [1,n] such that a b, c d, c _ b, and a _ d.


 (1) If b>d (resp. b=d) then a d by  applied to {a, b, d} (resp. since a  b) which is absurd. Similarly, if b<d then d  c by  which is again impossible. (2) If c>a (resp. c=a) then c  b by  applied to {a, b, c} (resp. since a  b) which is absurd, and thus c<a. However, by symmetry we should have a<c as well, which is again impossible.






 §.§ Properties of -tableaux
 
We discuss some properties of -tableaux for natural unit interval orders. These will be frequently used in the later part of this paper without reminder.

 Suppose that (a_p, …, a_1) and (b_q, … b_1) are two adjacent columns in a -tableau such that the former is on the left of the latter. 


  * If a_i>b_j then i≥ j

  * If a_i  b_j then i>j.

  * If i<j then a_i <b_j.


 For (1), suppose a_i>b_j and i<j. Then b_i  b_j thus a_i  b_i  by , which contradicts the -tableau condition. This proves (1). For (2), suppose a_i  b_j and i≤ j. Then b_i ≤ b_j thus a_i  b_i by , which contradicts the -tableau condition. This proves (2). For (3), suppose i<j and a_i≥ b_j. Then b_i  b_j thus a_i  b_i by , which contradicts the -tableau condition. This proves (3).





 §.§ Ladders
 We define a special kind of a natural unit interval order called a ladder order.
 A partial order  is called a ladder order if it is isomorphic to _(m-1),m for some m ∈.



Figure <ref> shows the partial order _(9),10 which is by definition a ladder order, and the partition and the unit interval arrangement defining it. The term “ladder” is inspired from the shapes of its Hasse diagram and the corresponding unit interval arrangement.


 For a partial order  defined on X, we say that A is a ladder in  if |_A is a ladder order.

For example, if =_(m-1),m then ladders in  are exactly [a,b] for some a,b ∈ [1,m].
Let us describe some basic properties of ladders. Later we will frequently use these properties without reminder.
 Suppose that  is a natural unit interval order on [1,n] and assume that y_1, …, y_k ∈ [1,n] such that y_1<y_2<⋯<y_k and {y_1, …, y_k} is a ladder in . Then,


  * {y_i, …, y_j} is a ladder in  for any 1≤ i≤ j ≤ k.

  * y_i  y_i+1 for i ∈ [1,k-1].

  * y_i  y_j if j-i≥ 2.

  * If x y_1 and x  y_2, then {x, y_1, …, y_k} is a ladder in .

  * If z y_k and z  y_k-1, then {y_1, …, y_k, z} is a ladder in .

  * If y_i<x<y_i+1 for some i ∈ [1,k-1], then y_i  x and x  y_i+1.


 It follows almost directly from the definition of a ladder and .





 §.§ Climbing a ladder
 We define a special kind of partial orders called “ladder-climbing” orders.
 For a partial order  on [1,n], we say that someone is climbing a ladder in  or  is ladder-climbing if there exist x, y_1, …, y_k ∈ [1,n] such that


  * x ∉{y_1, y_2, …, y_k},

  * {y_1, y_2, …, y_k} is a ladder in , and

  * y_1  x  y_k.

In this case, we also say that x is climbing a ladder in  or x is climbing (the ladder) {y_1, …, y_k}  in . If there is no such x, then we say that no one is climbing a ladder in  or simply  is not ladder-climbing.


Indeed, there is a characterization of ladder-climbing partial orders in terms of the avoidance of certain suborders as the following proposition shows.
 Let  be a partial order on [1,n]. Then no one is climbing a ladder in  if and only if it avoids both _(3,1,1),5 and _(4,2,1,1),6. (See Figure <ref> for the Hasse diagrams of these two orders.)

 Direct calculation shows that 3 is climbing the ladder {1, 2, 4, 5} in _(3,1,1), 5 and 4 is climbing the ladder {1, 2, 4, 5, 6} in _(4,2,1,1),6. Thus if no one is climbing a ladder in  then it should avoid _(3,1,1),5 and _(4,2,1,1),6.

It remains to show that if  is ladder-climbing then there is a set X ∈ [1,n] such that |_X is isomorphic to either _(3,1,1),5 or _(4,2,1,1),6. Suppose that x is climbing the ladder {y_1, y_2, …, y_k} in  where y_1<y_2<⋯<y_k, in which case y_1  x  y_k. Then without loss of generality we may assume that y_2x and y_k-1x. Since y_1  y_2 and y_k-1 y_k, this implies that y_2  x and y_k-1 x by . Moreover, we have y_i _ x for i∈ [2,k-1]. Indeed, if y_i x (resp.  y_i x) then y_2  x (resp. y_k-1 x) by  applied to (y_2, y_i, x) (resp. (x, y_i, y_k-1)), which is a contradiction.

Since y_2  x and y_k-1 x we have k≥ 4. On the other hand, if k≥ 7 then y_2, y_4, y_6_ x and y_2  y_4  y_6 which is impossible by Lemma <ref>. Thus it follows that k ∈[4,6]. If k=4, then one can easily show that  restricted to {x, y_1, y_2, y_3, y_4} is isomorphic to _(3,1,1),5 where the isomorphism of posets is given by (x, y_1, y_2, y_3, y_4)↦ (3,1,2,4,5). If k=5, then  restricted to {x, y_1, y_2, y_3, y_4, y_5} is isomorphic to _(4,2,1,1),6 where the isomorphism is given by (x, y_1, y_2, y_3, y_4, y_5) ↦ (3,1,2,4,5,6). Finally, if k=6 then  restricted to {x, y_1, y_2, y_3, y_5} is isomorphic to _(3,1,1),5, where the isomorphism is given by (x, y_1, y_2, y_3, y_5) ↦ (4, 1, 2, 3, 6). It suffices for the proof.





There is another characterization of _(3,1,1),5-avoiding partial orders as follows.
  The following two conditions are equivalent.


  *  avoids _(3,1,1),5.

  * “A join of two ladders is again a ladder.” Suppose that  and ' are two ladders in  such that ∩' = {x}. If x is the maximum in  and the minimum in ' with respect to the usual order and ||, |'|≥ 3 then  ∪' is also a ladder in .


 Suppose that =_(3,1,1),5. Then {1,2,3} and {3, 4, 5} are ladders but {1, 2, 3, 4, 5} is not a ladder. Thus any order that does not avoid =_(3,1,1),5 cannot satisfy the second condition. Now suppose that  avoids _(3,1,1),5 and assume that a_1<⋯<a_k<x<b_1< ⋯<b_l such that {a_1, …, a_k, x} and {x, b_1, …, b_l} are ladders in . Then it suffices to show that {a_k-1, a_k, x, b_1, b_2} is again a ladder in . By assumption we have a_k-1 x  b_2 and a_k-1 a_k x  b_1  b_2. Also a_k-1 b_1 and a_k  b_2 by . Thus if a_k  b_1 then direct calculation shows that  restricted to {a_k-1, a_k, x, b_1, b_2} is isomorphic to _(3,1,1),5, which is a contradiction. Thus a_k  b_1 and the result follows.









§ -KNUTH EQUIVALENCE AND THE MAIN THEOREM
 
In this section we assume that a fixed natural unit interval order  on [1,n] is given and define -Knuth moves and equivalences. Also we state our main theorem in this paper.


 §.§ Definition of -Knuth equivalences
 First we define the notions of -Knuth moves and equivalences which generalize the ones originally introduced by Knuth.
 Let 1≤ a<b<c≤ n and a c. We say that two words w, w' are connected by a -Knuth move if they fall into one of the following situations, in which case we write w  w' (or w ↭ w' if there is no confusion).


  * If a b and b c, then [⋯ bca ⋯][⋯ cab ⋯].

  * If a b and b c, then [⋯ bca ⋯][⋯ bac ⋯] and [⋯ cba ⋯][⋯ cab ⋯].

  * If a b and b c, then [⋯ bca ⋯][⋯ cba ⋯] and [⋯ acb ⋯][⋯ cab ⋯].

  * If a b and b c, then [⋯ bca ⋯][⋯ bac ⋯] and [⋯ acb ⋯][⋯ cab ⋯].



[scale=0.5]
  (a) at (0,0) a;
  (b) at (2,1) b;
  (c) at (0,2) c;
  (d) at (1,-1) (1) |_{a,b,c}≃_(1),3;
  [black,<-] (a) – (c);
  [black,dashed,<-] (a) – (b);
  [black,dashed,<-] (b) – (c);
  [scale=0.5]
  (a) at (0,0) a;
  (b) at (2,1) b;
  (c) at (0,2) c;
  (d) at (1,-1) (2) |_{a,b,c}≃_(1,1),3;
  [black,<-] (a) – (c);
  [black,<-] (a) – (b);
  [black,dashed,<-] (b) – (c);
  [scale=0.5]
  (a) at (0,0) a;
  (b) at (2,1) b;
  (c) at (0,2) c;
  (d) at (1,-1) (3) |_{a,b,c}≃_(2),3;
  [black,<-] (a) – (c);
  [black,dashed,<-] (a) – (b);
  [black,<-] (b) – (c);
  [scale=0.5]
  (a) at (0,0) a;
  (b) at (2,1) b;
  (c) at (0,2) c;
  (d) at (1,-1) (4) |_{a,b,c}≃_(2,1),3;
  [black,<-] (a) – (c);
  [black,<-] (a) – (b);
  [black,<-] (b) – (c);



In each situation, there exists i ∈ [2,n-1] such that the set of positions of a, b, and c is {i-1, i, i+1}. In such a case, we say that i is the position of the -Knuth move and also that the -Knuth move occurs at position i.


The -Knuth equivalence relation on the set of words is the equivalence relation generated by -Knuth moves. If two words w, w' are equivalent under this relation, we say that w and w' are -Knuth equivalent and write w∼ w'. (If there is no confusion, we also say that w and w' are equivalent and write w∼ w'.)


Note that -Knuth move/equivalence revert to the usual Knuth move/equivalence when  is the usual order on [1,n].

[Figure <ref>] All the possible -Knuth moves for natural unit interval orders  on [1,3] are described in Figure <ref>. Here, the underlined numbers in each word indicate its -descents.






 §.§ Relation to -descents and D graphs

Here we relate -Knuth equivalences with study of dual equivalence graphs by Assaf. More precisely, we show that the graphs obtained from the -Knuth moves are D graphs in the sense of <cit.>. First let us discuss how -Knuth moves affect the -descents of words.
  Assume that w,w'∈_n are connected by a -Knuth move at position i. 


  * We have {_(w)∩{i-1, i}, _(w')∩{i-1, i}} = {{i-1}, {i}}.

  * If i>2, then {_(w)∩{i-2, i-1}, _(w')∩{i-2, i-1}} is equal to one of {∅, {i-1}},  {{i-2}, {i-1}}, or {{i-2}, {i-2,i-1}}.

  * If i<n-1, then {_(w)∩{i, i+1}, _(w')∩{i, i+1}} is equal to one of {∅, {i}},  {{i}, {i+1}}, or {{i+1}, {i,i+1}}.

  * If j∈ [1,n-1]-[i-2, i+1], then _(w)∩{j}=_(w')∩{j}.


 (1) is checked case-by-case. For (2), we only need to check that {_(w)∩{i-2, i-1}, _(w')∩{i-2, i-1}}≠{∅, {i-2, i-1}} thanks to (1). This is also checked case-by-case. (3) is proved similarly to (2). (4) is trivial from the definition of -Knuth moves.


We recall the notion of signed colored graphs following <cit.> and <cit.>.
 A signed colored graph of degree n is a collection (V, σ, {E_i}_1<i<n) where V is a set, σ is a function σ: V→ 2^[1,n-1], and each E_i is a set of unordered pairs of different elements in V. (Here 2^[1,n-1] denotes the power set of [1,n-1].) Each element in V is called a vertex, and each element in E_i is called an edge colored i.


In <cit.> and <cit.> the function σ assigns to each vertex v ∈ V a sequence of length n-1 consisting of + and -. Their definition is equivalent to ours if we define a new sigma function, say σ': V → 2^[1,n-1], such that σ'(v)  i (resp. σ'(v) i) if and only if the i-th component of σ(v) equals + (resp. -).


 Suppose that V ⊂_n is closed under -Knuth moves. Then we define the -Knuth equivalence graph Γ_V attached to V to be Γ_V=(V, _, {E_i}_1<i<n) where each E_i is the set of pairs in V connected by a -Knuth move at position i.



It is clear that -Knuth equivalence graph is a signed colored graph of degree n. Now we recall the notion of D graphs following <cit.>.
 A signed colored graph (V, σ, {E_i}_1<i<n) of degree n is called a D graph if the following axioms hold.


  * For w ∈ V and 1<i<m, |σ(w) ∩{i-1, i}|=1 if and only if there exists x∈ V such that {w, x}∈ E_i. Moreover, x is unique when it exists.

  * Whenever {w, x}∈ E_i, σ(w)∩{i}≠σ(x) ∩{i} and σ(w)∩{h} =σ(x) ∩{h} for h ∉[i-2, i+1].

  * For {w, x}∈ E_i, if σ(w) ∩{i-2}≠σ(x) ∩{i-2} then |σ(w) ∩{i-2,i-1}|=1. Also, if σ(w) ∩{i+1}≠σ(x) ∩{i+1} then |σ(w) ∩{i,i+1}|=1.

  Ax5. Whenever |i-j|≥ 3, {w,x}∈ E_i, and {x,y}∈ E_j, there exists v∈ V such that {w, v}∈ E_j and {v, y}∈ E_i.


We claim that the -Knuth equivalence graphs are indeed D graphs.
 A -Knuth equivalence graph is a D graph.

 We need to check that Ax1, Ax2, Ax3, and Ax5 hold for -Knuth equivalence graphs. For Ax1, it follows from the fact that the -Knuth move at position i in Definition <ref> occurs in all the possible cases of words satisfying |σ(w) ∩{i-1, i}|=1. Ax2 follows from (1) and (4) of Lemma <ref>. Ax3 follows from (2) and (3) of Lemma <ref>. Lastly, Ax5 clearly follows from the definition of -Knuth moves.


In <cit.> and <cit.>, they defined dual equivalence graphs which are a special kind of D graphs by imposing two additional axioms. This framework is used to study Schur positivity of certain quasi-symmetric functions. In particular, the “generating functions” attached to a dual equivalence graph is a single Schur function by <cit.>. However, our graphs are not dual equivalence graphs in general.

 Figure <ref> shows all the connected -Knuth equivalence graphs on _4 with =_(2,1),4, where underlined numbers denote -descents and numbers above edges indicate their colors. (Written above each connected component is the corresponding generating function which we will define in a moment.) There is one connected component with 5 vertices which satisfies neither Axiom 4 nor Axiom 6 of <cit.> for dual equivalence graphs. 






 §.§ Genuine -height and fake -inversion number

Here we prove that the -Knuth move preserves genuine -heights and fake -inversion numbers of permutations. For the former claim, we need to impose assumption that  is not ladder-climbing.

 Suppose that  avoids _(3,1,1),5 and _(4,2,1,1), 6. If w  w', then (w) = (w'). As a result, the genuine -height is constant on any connected -Knuth equivalence graph.

The proof of this proposition will be given in Section <ref>.
 If we allow that  is ladder-climbing, then the above proposition is no longer true. For example, when =_(3,1,1),5 we have 53241  53412 but _(53241)=|(5,3)|=2≠ 3=|(5,3,1)|=_(53412). Likewise, when =_(4,2,1,1),6 we have 563241  635241 but _(563241)=|(6,4,1)|=3≠ 2=|(6,3)|=_(635241). 





 If w  w', then |_(w)| = |_(w')|. As a result, the fake -inversion number is constant on any connected -Knuth equivalence graph.

 Suppose that the -Knuth move w  w' occurs at position i. If either x ∉{w_i-1, w_i, w_i+1} or y ∉{w_i-1, w_i, w_i+1} then it is clear that _(w) ∩{(x,y)} =_(w') ∩{(x,y)} since the relative position of x and y does not change. Thus for the verification of this lemma we may restrict our attention to words of length 3, e.g. Figure <ref>. Now the lemma follows from case-by-case observation.






 §.§ Generating functions and the main theorem

Let us define a generating function of a -Knuth equivalence graph. (cf. <cit.>)
 For a -Knuth equivalence graph Γ_V=(V, _, {E_i}), its generating function is defined to be γ_V∑_w ∈ V t^|_(w)|F__(w). 

If we consider a connected -Knuth equivalence graph, then we may factor out t^|_(w)| from the formula due to Lemma <ref>.





More precisely, if Γ_V is a connected graph then γ_V t^|_(V)|∑_w ∈ V F__(w) where |_(V)| is the fake -inversion number of any element in V. Now we state the main theorem of this paper. Its proof is given in Section <ref>. Note that this strengthens <cit.> for a natural unit interval order which avoids _(3,1,1),5 and _(4,2,1,1),6.
  Suppose that  is a natural unit interval order on [1,n] which avoids _(3,1,1),5 and _(4,2,1,1),6. Let Γ=(V, _, {E_i}) be a connected -Knuth equivalence graph and γ_V be its generating function. Let w_1, …, w_k be all the elements in V each of which is the reading word of the -tableau PT_1, …, PT_k, of shape λ_1, …, λ_k, respectively. Then we have γ_V = t^|_(V)|(s_λ_1+⋯ +s_λ_k), where |_(V)| is the fake -inversion number of any element in V. Furthermore, we have l(λ_1)=⋯ =l(λ_k) which is also equal to the genuine -height of any w ∈ V.

 
The claim of the Theorem <ref> is true for all unit interval orders  (except the last sentense).

See Section <ref> for some examples of -Knuth equivalence graphs and their generating functions.
The following corollary is a direct consequence, which generalizes both <cit.> and <cit.> for a natural unit interval order which avoids _(3,1,1),5 and _(4,2,1,1),6.
 Suppose that  is a natural unit interval order on [1,n] which avoids _(3,1,1),5 and _(4,2,1,1),6.
Then the generating function of any -Knuth equivalence graph is Schur positive, i.e. it is a symmetric function and its coefficients with respect to the expansion of Schur functions are polynomials in t with nonnegative integer coefficients.




§ COLUMN INSERTION ALGORITHM
 
In this section, we assume that a fixed natural unit interval order  is given and define a column insertion algorithm.



 §.§ Column insertion algorithm _Φ
 
For convenience, we add , - to the poset ([1,n], ) so that i (resp. - i) for any i∈[1,n]. We define 

    {(a_m, …, a_1) | m ∈, a_i ∈ [1,n] ∪{}, a_i≠ a_j  if  i≠ j  and  a_i, a_j ≠},
    
       {(c_l, …,  c_1) | l ∈, c_i ∈ [1,n], c_i c_j  if   i<j},
    
       {(α, c) ∈×| a_i ≠ c_j  for any  i, j}, and
    
       {(c, α) ∈×| a_i ≠ c_j  for any  i, j}.

One may regard  as a set of (input/output) words and  as a set of chains, i.e. one-column -tableaux. (Recall that we read columns from bottom to top.) 

We introduce the column insertion algorithm _Φ. This defines a function Φ: → and is described in terms of the pseudocode Algorithm <ref>. 




Let us investigate this algorithm in more detail. It takes the input (α, c) ∈ where α=(a_m, …, a_1) and c=(c_l, …, c_1). Initiate =(b_m, …, b_1) with (a_m, …, a_1) and =(d_l, …, d_1) with (c_l, …, c_1). (Here l=||, which may change as the algorithm is performed.) Also we set d_0  - to simplify our argument. Initialize p with 1. 



  §.§.§ 
If p>m=|α|, then we terminate the algorithm and return (d, β)=(, ).



  §.§.§ [(a)]
 Suppose that a_p=. Then we increase p by 1 and repeat the algorithm from the beginning.
 The reason why we call it [(a)] (instead of ) shall become apparent when we describe another algorithm Ψ_X in the proof of Proposition <ref>.


From now on we suppose a_p ≠ and choose r ∈ [0,l] such that d_r<a_p<d_r+1. (If d_l<a_p, then we set r=l.) First suppose that a_p and d_r are comparable, i.e. d_r  a_p.





  §.§.§ [(a)]
 We first consider the case when r= l, i.e. a_p is bigger than any element in  with respect to . (This includes the case when r=l=0, i.e.  is an empty chain.) In this case we “add a_p to the end of the chain ”, i.e. set d_l+1 a_p and replace  with (d_l+1=a_p, d_l, ⋯, d_1). (As a result, the length of  increases by 1.) After this, we increase p by 1 and repeat the algorithm from the beginning.




  §.§.§ [(b)]
 Now suppose that  r<l. (This include the case when -=d_0< a_p< d_1.) Then “a_p bumps d_r+1”; we set b_p d_r+1 and then replace d_r+1 in  with a_p. For example, if 1 3 and 1 2, then Φ((2), (3,1)) = ((2,1),(3)). (Whether 2 3 or not does not affect the result here.) After this, we increase p by 1 and repeat the algorithm from the beginning.


Now we suppose that a_p and d_r are not comparable (which forces that r>0). We set

    A={   (i,j) ∈^2 | a_p<a_p+1<⋯<a_p+j{d_r, …, d_r+i, a_p, …, a_p+j} is a ladder in }.

Note that (0,0) ∈ A as {d_r, a_p} is a ladder in  by assumption (since _(1),2=_∅,2). We set (h,q) to be the maximum of A with respect to lexicographic order. In other words, we choose (h,q) such that 


  * a_p<a_p+1<⋯<a_p+q with respect to the usual order,

  * {d_r, …, d_r+h, a_p, …, a_p+q} is a ladder in ,

  * h is the biggest among such possible (h,q)'s, and

  * q is the biggest among such possible (h,q)'s with h chosen above.

For later use, we define:
 We assume the situation above. Then the phrase “maximality in ” indicates the maximality of (h,q) in A.



  §.§.§ [(a)]
 First we suppose that a_p+q<d_r+h, i.e. max{d_r, …, d_r+h, a_p, …, a_p+q}=d_r+h. (e.g. Example <ref> and <ref>) In this case we do not alter the chain  and simply let a_p, …, a_p+q “pass through the chain”, i.e. set b_i a_i for i ∈ [p,p+q].
After this, we increase p by q+1 and repeat the algorithm from the beginning.
 Here, the maximality in  means that either p+q=m or a_p+q+1 does not satisfy both a_p+q+1 a_p+q and a_p+q+1 d_r+h.





  §.§.§ [(b)]
 The remaining case is when a_p+q>d_r+h, i.e.  max{d_r, …, d_r+h, a_p, …, a_p+q}=a_p+q. (e.g. Example <ref> and <ref>) We set p-1=u(r-1)< u(r)< u(r+1)< ⋯< u(r+h)=p+q such that d_i<a_u(i-1)+1<⋯<a_u(i) for i∈ [r, r+h]. 
Then we replace d_r, …, d_r+h on the chain in  with a_u(r), …, a_u(r+h), respectively. Furthermore, for j ∈ [p, p+q] we set

    b_j {   d_i    if  j=u(i-1)+1  for some  i ∈ [r,r+h],
    
       a_j-1    otherwise.
    .
 
After this, we increase p by q+1 and repeat the algorithm from the beginning.

 Here, the maximality in  means that
 

  * either p+q=m or a_p+q+1 does not satisfy both a_p+q+1 a_p+q and a_p+q+1 a_p+q (or a_p+q+1 d_r+h if a_p+q d_r+h), and

  * either r+h=l or d_r+h+1a_i for any i ∈ [p,p+q].

One may check that the second condition is equivalent to
 

  * either r+h=l or d_r+h+1 a_i for any i ∈ [p,p+q].


For later use, we define:

We say that a_p is in [(a)], 1(b), etc. if the step in the column insertion algorithm _Φ processing a_p corresponds to [(a)], 1(b), etc.

This finishes the description of the algorithm _Φ. See Section <ref> for some examples about this algorithm. Before we proceed, we need to check that:
 The algorithm _Φ is well-defined, i.e. Φ(α, c) ∈.

 First suppose that a_1, a_m ≠ and only one step of _Φ is performed when calculating Φ((a_m, …, a_1), (c_l, …, c_1))=((d_l', …, d_1), (b_m, …, b_1)). Then we need to show that b_i, d_j for i ∈[1,m], j∈[1,l'] are pairwise different (possibly except ) and d_1 d_2 ⋯ d_l'. But the first part is clear from the assumption that a_1, …, a_m, c_1, …, c_l are pairwise different. The second part is also easily checked case-by-case using . Now the statement in the general case follows from induction on the number of steps.





















































































































































































































































































































 §.§ Properties of _Φ

Here we discuss some properties of _Φ. Firstly, if Φ(α,c) = (d, β) then it is easy to observe the following. (We will use these facts without reminder later on.)


  * if a_i is in [(a)] or [(a)], we have b_i=,

  * if a_i is in [(b)], we have a_i<b_i≠,

  * if a_i is in [(a)], we have a_i=b_i, and

  * if a_i is in [(b)], we have a_i b_i.

The following lemma is less trivial.
 For α=(a_m, …, a_1) and c=(c_l, …, c_1), suppose that there exists i ∈ [1,l] such that c_i  a_j for all j∈ [1,m]. If Φ(α, c) = ((d_l', …, d_1), -), then we have  c_j=d_j for j ∈ [1,i].

 It is shown by case-by-case observation.


The proofs of the following two propositions are provided in Section <ref>.

 
Suppose that Φ(α, c) = (d, β) where α=(a_m, …, a_1), β=(b_m, …, b_1), and c=(c_l, …, c_1). Write α^f (resp. β^f) to be the word obtained by removing  from α (resp. β).


  *  α^f+c and d+β^f are -Knuth equivalent. In particular, α^f+c=d+β^f as sets.

  *  Suppose that α∈, m≥ l, and (α, c) satisfies the -tableau condition, i.e. a_i c_i for i ∈ [1,l]. Then d=α and β=(,…, ) +c.

  *  If a_i, a_i+1≠ and a_i  a_i+1, then either [b_i+1 = ] or [b_i, b_i+1≠ and b_i  b_i+1].

  *  If a_i, a_i+1≠ and a_i a_i+1, then either [b_i = , b_i+1≠] or [b_i, b_i+1≠ and b_i b_i+1].



  Suppose that (α=(a_m, …, a_1), c), (α'=(a'_m, …, a'_1), c')∈ satisfy Φ(α,c) = Φ(α',c') and a_i =⇔ a_i'=. Then we have (α,c) = (α',c').




 §.§ Another algorithm _Ψ

Here we introduce another column insertion algorithm _Ψ which resembles _Φ. This will not be used for the definition of the -Robinson-Schensted algorithm in the next section, but it will play an important role when we prove Proposition <ref>. Also see Section <ref> for some examples about this algorithm.







For a subset X ⊂_>0, the algorithm _Ψ defines a function Ψ_X: → and is described by the pseudocode Algorithm <ref>. Note that the only difference between _Φ and _Ψ is when a_p=, p ∈ X, and ≠∅, which is as follows.

[(b)] Suppose that a_p=, p ∈ X, and ≠∅. Then we “drag the first entry of  to ”, i.e. set b_p d_1 and replace  with (d_l, …, d_2). (As a result, the length of  decreases by 1.) After this, we increase p by 1 and repeat the algorithm from the beginning.

Indeed, if X=∅ then _Ψ and Ψ_X revert to _Φ and Φ, respectively.


 The algorithm Ψ_X is well-defined.

 It is proved in the same manner as Theorem <ref>.










§ -ROBINSON-SCHENSTED ALGORITHM
 
In this section, we assume that a fixed natural unit interval order  is given and define a -Robinson-Schensted algorithm.


 §.§ -Robinson-Schensted algorithm

We identify  with the subset of ^n such that (c^1, c^2, …, c^n)∈^n corresponds to the -tableau whose reading word is c^1+c^2+⋯+ c^n if such a -tableau exists.
We define the -Robinson-Schensted algorithm _ as in Algorithm <ref>.



Let us describe the algorithm in detail. This algorithm takes an input α=(a_m, …, a_1) ∈ and produces an output (PT, QT). Initialize p with 0 and (b_m, …, b_1) with (a_m, …, a_1).



  §.§.§ 
 If (b_m, …, b_1)=(, …, ) then terminate the algorithm and return (PT, QT) where PT=(PT_1, …, PT_p) and QT=(QT_1, …, QT_p).



  §.§.§ 
 Otherwise, we increase p by 1 and set (PT_p, (t_m, …, t_1)) to be Φ((b_m, …, b_1),∅). Also we set QT_p=(i(k), …, i(1)) where i(1)< ⋯< i(k) are chosen such that {i(1), …, i(k)} = {j ∈ [1.m] | t_j=, b_j≠}, i.e. they are indices where [(a)] of _Φ occured in the calculation of Φ((b_m, …, b_1),∅). After this, we set (b_m, …, b_1) to be (t_m, …, t_1) and repeat the algorithm from the beginning.

This finishes the description of the algorithm _. It is clear that each column of PT (resp. QT) is a chain with respect to  (resp. the usual order). However, it is not clear at this moment that PT (resp. QT) is a -tableau (standard Young tableau). Indeed, it is not always so; see Section <ref> for such examples. However, we will observe that this algorithm behaves well when the given partial order on [1,n] avoids _(3,1,1),5 and _(4,2,1,1),6.



 §.§ Properties of 

Let T_λ∈_λ be the standard Young tableau of shape λ where λ'=(l_1, l_2, …, l_p) such that the i-th column of T_λ consists of (∑_k=1^i-1l_k)+1, (∑_k=1^i-1l_k)+2, …, (∑_k=1^il_k). For example, we have T_(4,3,1) = 1468,257,3. The following theorem summarizes important properties of the algorithm _ which is proved in Section <ref>, together with the main theorem (Theorem <ref>) of this paper.
 
Suppose that  avoids _(3,1,1),5 and _(4,2,1,1),6, i.e.  is not ladder-climbing. Then the following are satisfied.


  *  For w∈_n, if (w)=(PT, QT) then PT is a -tableau and QT is a standard Young tableau.

  *  For w∈_n, if (w) = (PT, QT) then {n-x | x ∈_(w)} = (QT).

  *  For w∈_n, If (w)=(PT, QT) then w(PT).

  *  For w ∈_n, if (w)=(PT, QT) then the length of the first column of PT is equal to _(w). Furthermore, if w' ∈_n satisfies w∼_ w' and (w') = (PT', QT'), then the lengths of the first column of PT and PT' are the same.

  *  If w=(PT) for some PT ∈_λ then (w) = (PT, ω(T_λ)) where ω : _λ→_λ is Schützenberger's evacuation. 

  *  If α=(a_m, …, a_1) and α'=(a'_m, …, a_1') are two words of the same length then (α)=(α') ⇔α=α'.

  *   restricts to a bijection : _n _λ⊢ n_λ×_λ.







§ EXAMPLES

In this section we give various examples of the objects that we introduced so far.


 §.§ -Knuth equivalence graphs
 
Here we provide some examples of -Knuth equivalence graphs whose generating functions are not a single Schur function. In Figure <ref>–<ref>, underlined numbers in each word denote its descents and numbers above edges indicate their colors. Vertices with bold borders are reading words of some -tableaux and vertices of the same colors are the ones that give the same -tableau under . Also, two gray vertices in Figure <ref> are the ones that insert to 312,54, which is not a -tableau for =_(3,1,1),5.


























































































































 §.§ Some examples of _Φ and _Ψ

Here we provide some examples how the algorithms _Φ and _Ψ work.
[Figure <ref>]  Suppose that =_(5,3,2,1),6, α=(4,3,2), and c=(6,5,1). In this case only one step of _Φ is required to calculate Φ(α, c), i.e. [(a)]. Here, the set A in the description of  is equal to {(0,0),(0,1),(0,2),(1,2)}, and thus we have (h,q)=(1,2). It follows that Φ(α, c) = ((6,5,1), (4,3,2)).



[Figure <ref>]  Suppose that =_(6),7, α=(7,5,4,2), and c=(6,3,1). Similarly to above, in this case only one step of _Φ is required to calculate Φ(α, c), i.e. [(b)]. Here, the set A in the description of  is equal to A={(0,0),(1,0),(1,1),(1,2), (2,2), (2,3)}, and thus we have (h,q)=(2,3). It follows that Φ(α, c) = ((7,5,2), (6,4,3,1)).



[Figure <ref>]  Suppose that =_(2,1,1),5, α=(5,4,2) and c=(3,1). We need to process three steps of _Φ to calculate Φ(α,c) in this case. 


  * Since a_1=2  1=d_1, a_1 is in . Here A={(0,0), (1,0), (0,1), (0,2)}, and thus we have (h,q)=(1,0) that is the maximum of A with respect to the lexicographic order even if the choice of (0,2) produces a bigger ladder. We set b_1=2, p=2 and continue.

  * Since a_2=4  3=d_2, a_2 is in . Here A={(0,0)}, and thus (h,q)=(1,0). Note that {3, 4, 5} is not a ladder in  since 3 5. We set b_2=3, d_2=4, p=3 and continue.

  * Since a_3=5 4=d_2, a_3 is in . Here A={(0,0)}, and thus (h,q)=(1,0). We set b_3=4, d_3=5, and terminate the algorithm.

As a result, we have Φ((5,4,2), (3,1)) = ((5,1), (4,3,2)).




[Figure <ref>]  Suppose that =_(7, 6, 5, 4, 3, 2, 1),9, α=(9, 8, 7, 5, 6, 3, 2, 4, 1) and c=∅. We need to process five steps of _Φ to calculate Φ(α,c) in this case. 


  * Since the chain is empty, a_1 is in [(a)]. We set d_1=1, p=2 and continue.

  * Since a_2=4>d_1=1 and 4  1, a_2 is in [(a)]. We set d_2=4, p=3 and continue.

  * Since d_1=1<a_3=2<d_2=4 and 2  1, a_3 is in . The set A is equal to {(0,0), (0,1), (1,1)} thus (h,q)=(1,1), in which case it is in [(a)]. We set b_3=2, b_4=3, p=5 and continue.

  * Since a_4=6>d_2=4 and 6  4, a_4 is in [(a)]. We set d_3=6, p=6 and continue.

  * Since d_2=4<a_6=5<d_3=6 and 5  4, a_6 is in . The set A is equal to {(0,0), (1,0), (1,1), (1,2), (1,3)} thus (h,q)=(1,3) in which case it is in [(b)]. We set d_2=5, d_3=9, b_6=4, b_7=6, b_8=7, b_9=8 and terminate the algorithm.

As a result, we have Φ((9,8,7,5,6,3,2,4,1), ∅) = ((9,5,1), (8,7,6,4,,3,2,,)).



[Figure <ref>]  Suppose that =_(7, 6, 5, 4, 3, 2, 1),9, α=(,,8,7,,6,4,3,2), c=(9, 5, 1), and X={5, 8, 9}. We need to process five steps of _Ψ to calculate Ψ_X(α,c) in this case. 


  * Since d_1=1<a_1=2<d_2=5 and 2  1, a_1 is in . The set A is equal to {(0,0), (0,1), (0,2), (1,2), (1,3)} thus (h,q)=(1,3) in which case it is in [(b)]. We set d_1=4, d_2=6, b_1=1, b_2=2, b_3=3, b_4=5, p=5 and continue.

  * Since a_5=, 5∈ X,  and ≠∅, a_4 is in [(b)]. We set =(9,6), b_5=4, p=6 and continue.

  * Since d_1=6<a_6=7<d_2=9 and 7  6, a_6 is in . The set A is equal to {(0,0), (0,1), (1,1)} thus (h,q)=(1,1), in which case it is in [(a)]. We set b_6=7, b_7=8, p=8 and continue.

  * Since a_8=, 8∈ X,  and ≠∅, a_8 is in [(b)]. We set =(9), b_8=6 and continue.

  * Since a_9=, 9∈ X,  and ≠∅, a_9 is in [(b)]. We set =∅, b_9=9 and continue.

As a result, we have Ψ_{5, 8, 9}((,,8,7,,6,4,3,2), (9, 5, 1)) = (∅, (9,6,8,7,4,5,3,2,1)).



 Indeed, Example <ref> and Example <ref> are “mirror images” to each other. This is not a coincidence but explained in detail in Section <ref>.





 §.§ Some examples of _

Here we provide some examples of the algorithm _.

 Figure <ref> shows the steps of _ when =_(2,1),4 and w is an element of {3241, 3421, 4231, 4312, 4132}, the set of vertices of a connected -Knuth equivalence graph that is not a dual equivalence graph (cf. Figure <ref>). Here we have Φ(3241) = (132,4,134,2), Φ(3421) = (21,43,12,34), Φ(4231) = (21,43,13,24), Φ(4312) = (132,4,124,3), and Φ(4132) = (132,4,123,4). It is easy to observe in this case that (cf. Theorem <ref>)


  (A) the outputs are pairs (PT, QT) where PT ∈_λ, QT∈_λ for some λ⊢ 4,

  (B) if (w) = (PT, QT) then _(w) = {4-x| x ∈(QT)},

  (C) (21,43) = 4231 and (132,4) = 4132 are the vertices of the given connected -Knuth equivalence graph,

  (D) Φ(4231)=(21,43, ω(13,24))=(21,43, 13,24) and Φ(4132) = (132,4,ω(134,2))=(132,4,123,4) where ω is Schützenberger's evacuation, and

  (E), (F) Φ gives a bijection between the given set of vertices and {21,43}×_(2,2)⊔{132,4}×_(3,1).

Furthermore, its generating function is t^2(s_31+s_22) as expected by Theorem <ref>.







 Figure <ref> shows the steps of _ when =_(7,6,5,4,3,2,1),9 and w=(9,8,7,5,6,3,2,4,1). Here we have Φ(w) = (1432,5876,9, 1346,2789,5).  Note that {9-x | x∈_(w)} = {1,4,6}=(1346,2789,5).





 Figure <ref> shows the steps of _ when =_(9,8,6,6,4,3,2,2,1),10 and w=(8, 4, 6, 7, 10, 1, 2, 5, 3, 9). Here we have Φ(w) = (1239,46510,87, 1245,3789,610). Note that {10-x | x∈_(w)} = {2,5,9}=(1245,3789,610).











 §.§ Some pathologies for ladder-climbing partial orders
  Here we provide some examples when  does not produce a desired output when  is ladder-climbing.

smalltableaux
 Figure <ref> shows the steps of _ when =_(3,1,1),5 and w=(3,4,5,2,1). Here we see that Φ(w) = (312,54, 125,34). However, PT in this case is not a -tableau since 3 1.






 Figure <ref> shows the steps of _ when =_(4,2,1,1),6 and w=(4,3,6,5,2,1). Here we see that Φ(w) = (4132,65, 1256,34). However, PT in this case is not a -tableau since 4 1.






 Figure <ref> shows the steps of _ when =_(5,3,2,1,1),7 and w=(3,1,5,6,7,4,2). Here we see that Φ(w) = (1264,35,7, 1256,34,7). However, PT and QT in this case are not even tableaux.









§ PROOF OF PROPOSITION  <REF>, <REF>, AND <REF>
  



 §.§ Proof of Proposition <ref>

We start with the following lemma.
  Let  be a natural unit interval order on [1,n]. Suppose that we are given a, b ∈ [1,n] and w ∈_n that satisfy w^-1(a)<w^-1(b) and a b. Then the following are equivalent:


  * (a,b) ∉_(w).

  * there exists a subword ad_1⋯ d_kb of w such that a _ d_1 _⋯_ d_k _ b.

  * there exists a subword ad_1⋯ d_kb of w such that a  d_1 ⋯ d_k  b.

  * there exists a subword ad_1⋯ d_kb of w such that a  d_1 ⋯ d_k  b and {a, d_1, …, d_k, b} is a ladder in .



(1) ⇔ (2) by definition, and (4) ⇒ (3) ⇒ (2) is clear. It remains to show (2) ⇒ (4). To this end, suppose that ad_1⋯ d_kb is a subword of w such that a _ d_1 _⋯_ d_k _ b and we construct another subword satisfying the condition of (4).

For simplicity we set d_0=a and d_k+1=b. First, let d_i be the last element in the subword d_0d_1⋯ d_kd_k+1 such that d_0_ d_i. By removing d_1, d_2, …, d_i-1 if necessary, without loss of generality we may assume that it is d_1. Similarly we let d_j be the last element in the subword d_0d_1⋯ d_kd_k+1 such that d_1 _ d_j. By removing d_2, …, d_j-1 if necessary, without loss of generality we may assume that it is d_2. We iterate this process, and thus we may assume that d_i+1 is the last element in d_0d_1⋯ d_kd_k+1 such that d_i _ d_i+1 for i ∈ [0,k].

We claim that d_i  d_i+1 for any i ∈ [0,k]. For the sake of contradiction suppose otherwise, i.e. d_i  d_i+1 and let i ∈ [0,k] be the smallest element such that d_i  d_i+1. If i >0, then d_i-1 d_i by assumption and thus d_i-1_ d_i+1 by , which contradicts the fact that d_i is the last element satisfying d_i-1_ d_i. If i=0, i.e. a  d_1, then we claim that a  d_j for any j ≥ 2, which in particular contradicts the fact that a  b=d_k+1. Thus suppose otherwise. Then there exists j such that a  d_j, and we choose such j to be the minimum one. Then we have a<d_j-1, d_j-1_ d_j, and a  d_j, which contradicts . (Note that this argument is valid even when j=2.)

Now for any i ∈ [1,k], we have d_i-1 d_i  d_i+1, and thus d_i-1 d_i+1 since again d_i is the last element satisfying d_i-1_ d_i. But this means that {d_0,d_1, …, d_k, d_k+1} is a ladder in , which is what we want to prove.




















Let us start proving Proposition <ref>. Let w = ⋯ xyz ⋯ and w'=⋯ x'y'z' ⋯ such that the -Knuth move connecting w and w' shuffles {x, y, z}={x',y',z'}. 

Suppose that (p_1, …, p_s, r_1, …, r_u, q_1, …, q_t) is the longest subword of genuine -inversions in w such that ∩{x, y, z} = {r_1, …, r_u}. In particular we have _(w) = s+t+u. Note that s, t ≥ 0 and u∈ [0,2]. (u cannot be 3 since otherwise x y z in which case there is no -Knuth move shuffling x,y,z.) 

We may assume s, t ≥ 2. Indeed, we add n+1, n+2 and 0, -1 to the poset ([1,n], ) so that n+2  n+1  i  0  -1 for any i ∈ [1,n]. Then we replace w and w' with (n+2, n+1)+w+(0, -1) and (n+2, n+1)+w'+(0, -1), respectively. After this procedure,  still remains to avoid _(3,1,1),5 and _(4,2,1,1), 6. Also, any longest subword of genuine -inversions in w and w' contains n+2, n+1, 0, and -1, which in particular increases s and t by 2, respectively. (Here, we have p_1=n+2, p_2=n+1, q_t-1=0, and q_t=-1.)

We will construct the subword ' of genuine -inversions of length s+t+u on w', which contains p_1, …, p_s-1, q_2, …, q_t. It means in particular that _(w') ≥ s+t+u, which proves the claim by symmetry. Note that we possibly change only p_s, r_1, …, r_u, q_1 part from  to obtain '. Therefore, the entries before p_s-1 and after q_2 in w and w' do not affect this process. By removing such entries if necessary, it suffices to assume that s=t=2, i.e. we have =(p_1, p_2, r_1, …, r_u, q_1, q_2). 

Let a, b, c ∈ [1,n] be such that a<b<c and {a, b, c}={x,y,z}={x',y',z'}. From now on we argue case-by-case based on |_{a, b, c} and u∈ [0,2].



  §.§.§ |_{a, b, c}≃_∅,3
 There is no -Knuth move in this case, so there is nothing to prove.



  §.§.§ |_{a,b,c}≃_(1),3

We have a b  c and a  c. There is only one -Knuth move in this case: [⋯ bca ⋯]  [⋯ cab ⋯].

• u=0 case. In this case we have =p_1p_2q_1q_2 and in particular (p_2,q_1) ∈_(w). If (p_2, q_1) ∈_(w') then we are done since we may set '=. From now on we assume (p_2, q_1) ∉_(w').

First consider the case when w=[⋯ bca ⋯] and w'=[⋯ cab ⋯]. By Lemma <ref>, there exists a subword p_2d_1⋯ d_kq_1 (k≥ 1) in w' where p_2  d_1⋯ d_k q_1 and  is a ladder in . As (p_2,q_1) ∈_(w), it means that the order of some elements in  should be switched under the -Knuth move so that it no longer prohibits (p_2, q_1) from being a genuine -inversion of w. Then the only possibility is that =p_2d_1⋯ d_v-1 cb d_v+2⋯ d_kq_1, i.e. d_v=c and d_v+1=b for some v ∈ [1,k-1]. 

We claim that we may choose ' p_1p_2aq_2. To this end we need to check that (p_2,a), (a, q_2) ∈_(w'). First if (p_2,a) ∉_(w') then as p_2>c a there exists a subword p_2e_1⋯ e_la of w' such that p_2 _ e_1 _⋯_ e_l _ a. Since c  a, e_l appears before c in w' which means that p_2e_1⋯ e_la is also a subword of w. However, this contradicts (p_2, q_1) ∈_(w) as a _ b _ d_v+2_⋯_ d_k_ q_1. 

This time suppose that (a,q_2) ∉_(w'). Since b>q_1  q_2 and b  a, by  we should have a>q_2. First suppose that a  q_2. If v<k-1 then b  q_1  q_2 and b a q_2, which contradicts Lemma <ref>. Thus v=k-1, i.e. =⋯ cbq_1. However, direct calculation shows that  restricted to {c, b, q_1, a, q_2} is isomorphic to _(3,1,1),5, which is again a contradiction.

Thus we have a  q_2, and by Lemma <ref> there exists a subword ae_1⋯ e_lq_2 of w' (l≥ 1) such that a  e_1 ⋯ e_l  q_2 and {a, e_1, …, e_l, q_2} is a ladder in . By Lemma <ref> it follows that {c,b,a, e_1, …, e_l, q_2} is also a ladder in . By assumption we have c  q_1  q_2, and also q_1 ∉{c,b,a, e_1, …, e_l, q_2}; it is clear that q_1≠ c,b,a, q_2, and if q_1=e_i for some i then it means that (q_1, q_2) ∉(w). In other words, q_1 is climbing the ladder {c,b,a, e_1, …, e_l, q_2}, which contradicts the assumption on .

It remains to consider the case when w=[⋯ cab ⋯] and w'=[⋯ bca ⋯]. By arguing similarly, we should be able to find a subword =p_2d_1⋯ d_v-1bad_v+2⋯ d_kq_1 of w' with the same properties as above. Then we may choose '=p_1cq_1q_2, which can also be shown analogously. We omit the details.


• u=1 case. We have =p_1p_2r_1q_1q_2 where r_1 ∈{a,b,c}. First consider the case when w=[⋯ bca ⋯] and w'=[⋯ cab ⋯]. Using Lemma <ref>, one can easily show that if r_1=a then we may set '= and we are done. 

Now suppose that r_1=b. 
We claim that we may choose '=p_1p_2aq_1q_2. To this end we need to verify that (p_2,a), (a, q_1) ∈_(w'). First if (p_2, a) ∉_(w') then as p_2 b > a there exists a subword p_2e_1⋯ e_la of w' such that p_2  e_1⋯ e_l  a. Since b a, either e_l=b or e_l _ b by , which means that  (p_2, b) ∉_(w). This is a contradiction and thus we have (p_2, a) ∈_(w'). On the other hand, since b q_1 and b a we have a>q_1 by . Now if (a, q_1) ∉_(w'), i.e. there exists a subword ae_1⋯ e_lq_1 (l≥ 0) of w' such that a e_1 ⋯ e_l  q_1 (note that e_1 cannot be b), then since b  a it follows that (b, q_1) ∉_(w). This is a contradiction, and thus we have (a, q_1) ∈_(w') as desired.

If r_1=c, then by the same argument one can easily show that we may choose '=p_1p_2bq_1q_2. We omit the details.







It remains to consider the case when w=[⋯ cab ⋯] and w'=[⋯ bca ⋯]. Similarly to above, we may set '=p_1p_2cq_1 q_2 if r_1∈{b,c} and '=p_1q_2bq_1q_2 if r_1=a. Again we omit the details.

• u=2 case. We have = p_1p_2caq_1q_2. Then using Lemma <ref>, one can easily show that '= satisfies the desired properties.



  §.§.§ |_{a,b,c}≃_(1,1),3
 
We have a  b  c and a  c. Here we have two kinds of -Knuth moves: [⋯ bca ⋯][⋯ bac ⋯] and [⋯ cba ⋯][⋯ cab ⋯].


• u=0 case. In this case we have =p_1p_2q_1q_2 and in particular (p_2,q_1) ∈_(w). Since the relative position of b and c does not change by the -Knuth moves in this case, one can easily show that (p_2, q_1) ∈_(w') by using Lemma <ref>. Then we are done since we may set '=. 

• u=1 case. We have =p_1p_2r_1q_1q_2 where r_1 ∈{a,b,c}. Again, since the relative position of b and c does not change by the -Knuth moves in this case, one can easily show that we may set '= by using Lemma <ref>.

• u=2 case. We have = p_1p_2r_1r_2q_1q_2 where either (r_1, r_2) = (b,a) or (r_1, r_2) = (c,a). Since the relative position of b and c does not change by the -Knuth moves in this case, we only need to consider the situations when the relative position of r_1 and r_2 changes under the moves. We have two cases to consider.

The first case is when =p_1p_2baq_1q_2, w=[⋯ cba ⋯], and w'=[⋯ cab ⋯]. We claim that we may choose '=p_1p_2 caq_1q_2. To this end we need to check (p_2,c) ∈_(w'). (It is trivial that (c,a) ∈_(w') in this case.) Since p_2  b and c  b, we have p_2>c by . Thus if (p_2,c) ∉_(w') then there exists a subword p_2e_1⋯ e_lc (l≥ 0) of w' such that p_2  e_1 ⋯ e_l  c. However, since c  b, it implies (p_2,b) ∉_(w), which is a contradiction.

The remaining case is when =p_1p_2caq_1q_2, w=[⋯ bca ⋯], and w'=[⋯ bac ⋯]. Here one can show that we may choose '=p_1p_2baq_1q_2 similarly to above. We omit the details.



  §.§.§ |_{a,b,c}≃_(2),3
 This case is completely analogous to the above case when |_{a,b,c}≃_(1,1),3 if one “reverses” the words therein. We again omit the details.



  §.§.§ |_{a,b,c}≃_(2,1),3
 We have a b c. Here we have two kinds of -Knuth moves: [⋯ bca ⋯][⋯ bac ⋯] and [⋯ acb ⋯][⋯ cab ⋯].


• u=0 case. In this case we have =p_1p_2q_1q_2. It is easy to show that (p_2, q_1) ∈_(w) implies (p_2, q_1) ∈_(w'), and thus we may set '=. 

• u=1 case. We have =p_1p_2r_1q_1q_2 where r_1 ∈{a,b,c}. Again, one can easily show that we may set '=.

• u=2 case. We have = p_1p_2r_1r_2q_1q_2 where (r_1, r_2) ∈{(b,a), (c,a), (c,b)}. Here we only need to consider the situations when the relative position of r_1 and r_2 changes under the -Knuth moves. We have two cases to consider.

The first case is when = p_1p_2caq_1q_2, w=[⋯ bca ⋯], and w'=[⋯ bac ⋯]. Here we may choose '=p_1p_2baq_1q_2. Trivially (b,a) ∈_(w'), so it suffices to check that  (p_2,b) ∈_(w'). If we suppose otherwise then since p_2  c  b there exists a subword p_2e_1⋯ e_lb (l>0) in w' such that p_2 e_1 ⋯ e_l  b and {p_2, e_1, …, e_l, b} is a ladder in . However, c ∉{p_2, e_1, …, e_l, b} and p_2  c  b which means that c is climbing the aforementioned ladder, which is a contradiction. Thus we have (p_2,b) ∈_(w').

The remaining case is when  = p_1p_2caq_1q_2, w=[⋯ cab ⋯], and w'=[⋯ acb ⋯]. Here we may choose '=p_1p_2cbq_1q_2 similarly to above. We omit the details.

We exhausted all the cases and thus conclude the statement.



 §.§ Proof of Proposition <ref><ref>
 
Here, we write (⋯abc⋯)  (⋯ a'b'c' ⋯) for {a', b' , c'}={a,b,c} to indicate the location of a -Knuth move (that is the underlined part). We start with the following lemma. After this, we use wavy underlines, e.g. ⋯x_1⋯ x_k⋯⋯ y_1⋯ y_k ⋯ for {x_1, …, x_k}={y_1, …, y_k} to indicate the part where Lemma <ref> is applied.
 Suppose that a fixed natural unit interval order  is given. 

 

  * If b_1 b_2⋯ b_k and a<b_1 then ab_k⋯ b_1   b_k ⋯ b_2ab_1.

  * If b_1 b_2⋯ b_k and a>b_k then b_k⋯ b_1a   b_kab_k-1⋯ b_1.

  * If b_1 b_2 ⋯ b_k, x y, and y<b_1 then yxb_k⋯ b_1 yb_k⋯ b_1x.

  * If b_1 b_2 ⋯ b_k, x y, and x>b_k then b_k⋯ b_1yx yb_k⋯ b_1x.


 For (1), we have 
ab_kb_k-1⋯ b_1  b_kab_k-1b_k-2⋯ b_1 ⋯ b_k⋯ b_3ab_2b_1 b_k⋯ b_3b_2ab_1. (2) is proved similarly. For (3), we have yxb_k⋯ b_1   yb_kxb_k-1⋯ b_1 ⋯ yb_k ⋯b_2xb_1 yb_k ⋯ b_2b_1x. (4) is proved similarly.


We prove (A) by showing that each step in the column insertion algorithm respects the -Knuth equivalence. It is sufficient to consider when the input is given by (α=(a_m, …, a_1), c=(c_l, …, c_1)) such that c_1 c_2 ⋯ c_l, α=α^f, and only one step of _Φ is required to obtain the output. We argue case-by-case.

[(a)]. There is nothing to prove since α+c=d and β=().

[(b)]. The length of α equals 1, i.e. α=(a) for some a. First suppose that  c_i<a<c_i+1 and c_i  a for some i ∈ [1,l-1]. We have

    ac_l⋯ c_i+2 c_i+1c_i ⋯ c_1  c_l⋯ c_i+2ac_i+1c_ic_i-1⋯ c_1
    
        c_l⋯ c_i+2ac_ic_i+1c_i-1⋯ c_1 c_l⋯ c_i+2ac_i⋯ c_1c_i+1.

which proves the claim.
It remains to show that ac_l⋯ c_1  c_l⋯ c_2ac_1 if c_1  c_2 ⋯ c_l and a<c_1, but it follows directly from Lemma <ref>.

[(a)].
It suffices to prove the following lemma.
  Suppose that c_1 ⋯ c_l, c_i<a_1<a_2<⋯<a_m<c_i+1 for some i ∈ [1,l-1], and  {c_i, a_1, …, a_m, c_i+1} is a ladder in . Then a_m⋯ a_1 c_l⋯ c_1  c_l⋯ c_1 a_m ⋯ a_1.

 Since we have

    a_m⋯ a_1c_lc_l-1c_l-2⋯ c_1  c_la_m⋯ a_1c_l-1c_l-2c_l-3⋯ c_1⋯
        c_l⋯ c_i+3a_m⋯ a_1c_i+2c_i+1c_i⋯ c_1  c_l⋯ c_i+2a_m⋯ a_1c_i+1c_i ⋯ c_1      and
       c_l⋯ c_i+1c_ia_m⋯ a_1c_i-1c_i-2⋯ c_1  c_l⋯ c_ic_i-1a_m⋯ a_1c_i-2c_i-3⋯ c_1 ⋯
        c_l⋯ c_3c_2a_m⋯ a_1c_1 c_l⋯ c_3c_2c_1a_m⋯ a_1,

it is enough to consider the case when i=1 and l=2. However, in this case we have

    a_m⋯ a_2a_1c_2c_1  a_m⋯ a_3a_2c_2a_1c_1 ⋯a_mc_2a_m-1 a_m-2⋯ a_1 c_1
    
        c_2a_m-1a_ma_m-2a_m-3⋯ a_1 c_1 
    ⋯  c_2a_ma_m-1⋯ a_4 a_2a_3a_1 x   c_2a_ma_m-1⋯ a_3a_1a_2 c_1
         c_2a_ma_m-1⋯a_3a_2 c_1a_1⋯c_2a_mc_1a_m-1⋯ a_1   c_2c_1a_m⋯ a_1

as desired.


[(b)]. Suppose that there exist s,t and 0=u(0)<u(1)<⋯< u(s)=m such that c_t+i<a_u(i-1)+1<⋯< a_u(i) for i ∈ [1,s]. Also we assume that {c_t+1, …, c_t+s, a_1, …, a_m} is a ladder in . Note that if t+s<l then we may assume that c_t+s+1 a_i for any i ∈ [1,m] by maximality in .



We argue by induction on s≥ 1. Assume that s=1, i.e. c_t+1<a_1<⋯<a_m and c_t+2 a_i for any i ∈ [1,m] if t+1<l. First if m=1, then we have

    a_1 c_l ⋯ c_t+2c_t+1⋯ c_1     c_l ⋯ c_t+3a_1c_t+2c_t+1c_t ⋯ c_1 
    
        c_l ⋯ c_t+2a_1c_t+1c_tc_t-1⋯ c_1 
    
        c_l ⋯ c_t+2a_1c_tc_t+1c_t-1c_t-2⋯ c_1 ⋯
        c_l ⋯ c_t+2a_1c_t⋯c_2 c_t+1 c_1
        c_l ⋯ c_t+2a_1c_t⋯ c_2 c_1 c_t+1

which proves the claim. In general, we have

    a_m ⋯ a_1 c_l ⋯ c_1     a_m ⋯ a_2 c_l ⋯ c_t+2a_1c_t⋯  c_1 c_t+1
        a_m ⋯ a_3 c_l ⋯ c_t+2a_2c_t⋯  c_1 a_1c_t+1⋯
        c_l ⋯ c_t+2a_mc_t⋯  c_1 a_m-1⋯ a_1c_t+1

by iterating the above process m times.

Now suppose that the induction step is valid up to s-1. Then we have

    a_u(s)⋯ a_1c_l⋯ c_1 
    
        a_u(s)⋯ a_u(1)+1c_l⋯ c_1 a_u(1)⋯ a_1
    
        c_l ⋯ c_t+s+1a_u(s)a_u(s-1)⋯ a_u(2)c_t+1⋯ c_1 + a_u(s)-1⋯ a_u(s-1)+1c_t+s
            + a_u(s-1)-1⋯ a_u(s-2)+1 c_t+s-1+⋯+ a_u(2)-1⋯ a_u(1)+1c_t+2a_u(1)⋯ a_1
    
    
        a_u(s)-1⋯ a_u(s-1)+1c_t+s + a_u(s-1)-1⋯ a_u(s-2)+1 c_t+s-1+⋯
            + a_u(2)-1⋯ a_u(1)+1c_t+2a_u(1)⋯ a_1 + c_l ⋯ c_t+s+1a_u(s)a_u(s-1)⋯ a_u(2)c_t+1⋯ c_1
    
    
        a_u(s)-1⋯ a_u(s-1)+1c_t+s + a_u(s-1)-1⋯ a_u(s-2)+1 c_t+s-1+⋯+ a_u(2)-1⋯ a_u(1)+1c_t+2
            + c_l ⋯ c_t+s+1a_u(s)a_u(s-1)⋯ a_u(2)a_u(1)c_t ⋯ c_1 + a_u(1)⋯ a_1c_t+1
    
         c_l ⋯ c_t+s+1a_u(s)a_u(s-1)⋯ a_u(2)a_u(1)c_t ⋯ c_1+ a_u(s)-1⋯ a_u(s-1)+1c_t+s
            + a_u(s-1)-1⋯ a_u(s-2)+1 c_t+s-1+⋯+ a_u(2)-1⋯ a_u(1)+1c_t+2 + a_u(1)⋯ a_1c_t+1

which completes the induction step. (Here, the second ∼_ is from induction assumption, the fourth one is from s=1 case, and the others are from Lemma <ref>.)



 §.§ Proof of Proposition <ref><ref>

 We argue by induction on l=|c|. First suppose that l=1. If a_1 is in , then it should be in [(b)] by assumption and the result is trivial. If a_1 is in , then the only possible case is when a_1 is in [(b)] and either a_1 is not processed in the same step as a_2 or α=(a_1). Again the result is trivial in this case.

From now on suppose that l≥ 2 and the result holds up to l-1. Note that a_1 <c_2 since otherwise a_1  c_1 by . If a_1<c_1, then a_1 is in [(b)] and a_1 bumps c_1. Then a_1  a_j for any j ∈ [2,m] and a_i  c_j for j ∈ [2,l], and thus we may apply induction assumption on (a_m,…, a_2) and (c_l,…, c_2) to prove the claim. Thus it suffices to assume that c_1<a_1<c_2. Since a_1 c_1, it implies that a_1  c_1, and thus a_1 is in . Suppose that a_1 is in [(b)] and a_1, …, a_k are processed in the same step but a_k+1 is not. As a_1 ⋯ a_k, it means that a_1, …, a_k bump c_1, …, c_k, respectively, and we may apply induction hypothesis to (a_m, …, a_k+1) and (c_l, …, c_k+1) similarly to above.

It remains to assume that a_1 is in [(a)]. Since a_1  a_2, this only happens when a_1  c_2. However, as a_1  a_2 and a_2 c_2, this forces that a_1<c_2<a_2 and a_2  c_2 by . In other words, {c_1, a_1, c_2, a_2} is a ladder in . Thus by the assumption that a_1 is in [(a)] we have a_2  c_3. We may iterate this argument and observe that {c_1, a_1, c_2, a_2, …, c_l, a_l} is a ladder. However, in this case a_1 is in [(b)], which is a contradiction. Thus a_1 cannot be in [(a)] and the claim is proved.



 §.§ Proof of Proposition <ref><ref>
 
We assume that the input is given by (α=(a_m, …, a_1), c=(c_l, …, c_1)) and the output is given by (-, β) where β=(b_m, …, b_1). Furthermore, we suppose that a_i is processed in the first step of the algorithm. For example, if a_i is in [(a)] or [(b)] then it means that a_j= for j<i. 


In order to prove <ref>, we need to show that b_i ≠ and b_i  b_i+1 under the assumption that a_i, a_i+1≠, a_i  a_i+1, and b_i+1≠. 
First we consider the case when a_i and a_i+1 are processed in the same step. If this step is in [(a)], then a_i=b_i and a_i+1=b_i+1 thus the result is obvious. On the other hand, if this step is in [(b)] then one may easily observe that b_i<a_i<b_i+1<a_i+1 and {b_i, a_i, b_i+1,a_i+1} is a ladder in . In particular we have b_i  b_i+1 as well.

Therefore, it suffices to assume that a_i and a_i+1 are processed in different steps. We let =(d_l', …, d_1) be the chain obtained after the first step (which processes a_i) is performed. (See Figure <ref>.) For example, if a_i is in [(a)] then l'=l+1, d_l'=a_i, and d_j=c_j for j ∈ [1,l].






First, we note that b_i ≠; otherwise, a_i is in [(a)] which means that a_i becomes the largest element in the chain . Since  a_i  a_i+1, it means that a_i+1 is also in [(a)], which contradicts the assumption that b_i+1≠. In particular, it follows that l=l', i.e. the length of c and  should be equal.

It remains to show that b_i  b_i+1. First assume that a_i is in [(b)], i.e. there exists j ∈ [0,l-1] such that c_j<a_i<c_j+1 and c_j a_i. (Here we put c_0=- as before.) In this case b_i = c_j+1, d_j+1=a_i, and d_k=c_k for k ≠ j+1. Now, if a_i+1 is in


  * [(a)]: this is impossible as we assumed that b_i+1≠.

  * [(b)]: a_i+1 should bump d_k=c_k for some k ≥ j+2 since d_j+1=a_i  a_i+1. As a result, b_i=c_j+1 c_k =b_i+1.

  * [(a)]: since a_i  a_i+1, this is only possible when there exists d_k=c_k for some k≥ j+2 such that c_k  a_i+1. As c_j+1 c_k, we have c_j+1 a_i+1 by  applied to (c_j+1, c_k, a_i+1). Therefore we have b_i = c_j+1  a_i+1 = b_i+1.

  * [(b)]: it is shown in the same way as [(a)].


Now we assume that a_i is in [(a)], i.e. a_i=b_i and d=. Then for any x≥ a_i+1 we have a_i=b_i  x by  applied to (a_i, a_i+1, x), and thus the only nontrivial case occurs when a_i+1 is in [(b)]. However, this is only possible when there exists j ∈ [1,l] such that a_i c_j  a_i+1, in which case a_i and a_i+1 should be processed in the same step because of the maximality in . This violates the aforementioned assumption.

Lastly we assume that a_i is in [(b)], i.e. a_i  b_i. Again, by  the only nontrivial case occurs when a_i+1 is in [(b)] and this is only possible when there exists j ∈ [1,l] such that a_i c_j=d_j a_i+1. In this case we have b_i+1=c_j and thus b_i  c_j=b_i+1 by  applied to (b_i, a_i, c_j).

We exhaust all the possibilities and thus completed the proof of <ref>.




 §.§ Proof of Proposition <ref><ref>

We keep the setup in the proof of<ref> above.
First we consider the case when a_i and a_i+1 are processed in the same step. If this step is in [(a)], then a_i=b_i and a_i+1=b_i+1 thus the result is obvious. On the other hand, if this step is in [(b)] then one may easily observe that b_i<a_i=b_i+1<a_i+1 and {b_i, a_i=b_i+1,a_i+1} is a ladder in . In particular we have b_i  b_i+1 as well. Therefore, it suffices to assume that a_i and a_i+1 are processed in different steps.

We suppose that b_i+1=, i.e. a_i+1 is in [(a)]. Since a_i a_i+1, it follows that d_l'≠ a_i, i.e. l=l' and d_l=c_l (and also l≠ 0). However, it is only possible when a_i<c_l and c_l  a_i+1, which implies a_i  a_i+1 by  applied to (a_i, c_l, a_i+1). This violates our assumption, and thus b_i+1≠ as expected.

It remains to show that b_i b_i+1 if b_i≠, i.e. the length of c is equal to . We first assume that a_i is in [(b)], i.e. there exists j∈ [0,l-1] such that c_j<a_i<c_j+1 and c_j  a_i. (Here we put c_0=- as before.) In this case we have b_i =c_j+1>a_i, d_j+1=a_i, and d_k=c_k for any k ≠ j+1. As b_i a_i+1 by  applied to (a_i, b_i=c_j+1, a_i+1), it follows that b_i x for any x ≤ a_i+1 again by  applied to (b_i, x, a_i+1). Therefore the only nontrivial case occurs when a_i+1 is in [(b)] as well. This is only possible when either [there exists k∈[0,j-1] such that c_k<a_i+1<c_k+1 and c_k  a_i+1] or [c_j<a_i+1<d_j+1=a_i and c_j  a_i+1]. Thus b_i+1 is equal to either c_k+1 for k<j or a_i. In either case, we have b_i=c_j+1b_i+1.

Let us assume that a_i is in [(a)], i.e. c=. As above, the only nontrivial case occurs when a_i+1 is in [(b)], i.e. there exists j ∈ [0,l-1] such that c_j<a_i+1<c_j+1 and c_j  a_i+1, in which case b_i+1=c_j+1. Now if a_i = b_i  b_i+1=c_j+1, then as a_i is in [(a)] there exists k <j+1 such that a_i c_k. But this is contradiction since c_j  a_i+1 implies c_k  a_i+1, which means a_i  a_i+1 by  applied to (a_i, c_k, a_i+1).

Lastly, we assume that a_i is in [(b)] so that a_i  b_i. As a_i and a_i+1 are not processed in the same step, a_i should be in . If a_i+1 is in


  * [(a)]: this is impossible as we assumed that b_i+1=.

  * [(b)]:  since a_i a_i+1, a_i+1 either bumps a_i or some element above a_i in the chain , i.e. b_i+1=a_i or b_i+1 a_i. In either case, we should have b_i b_i+1 since otherwise a_i  b_i.

  * [(a)]: suppose that b_i b_i+1=a_i+1. As b_i  a_i, we have a_i<a_i+1 by  applied to (b_i, a_i, a_i+1), and thus  {b_i, a_i, a_i+1} is a ladder in . However, this violates the maximality of  as a_i and a_i+1 are not processed in the same step. Thus we should have b_ib_i+1=a_i+1

  * [(b)]: 

b_i+1 is some element in the chain d' satisfying a_i+1 b_i+1. If b_i  b_i+1, then we should have b_i<a_i<b_i+1<a_i+1 by  applied to (b_i, a_i, b_i+1) and also b_i  a_i+1  by  applied to (b_i, b_i+1, a_i+1).


However, in such a case {b_i, a_i, a_i+1} is a ladder in , which violates the maximality in . Thus we have b_i b_i+1


We exhaust all the possibilities and thus completed the proof of <ref>.



 §.§ Proof of Proposition <ref>
  






























































































Hereafter we write = and a n+1-a for a ∈ [1,n]. (n is assumed to be fixed.) We define a new order  on [1,n] such that a b if and only if ab. Then one can easily check that =_λ,m if and only if =_λ', m. Also, from now on we write ^, ^, Φ^, Ψ_X^, etc. to clarify which partial order is used in their definitions. We define 

    ∙:    →: α=(a_m, …, a_1) ↦α=(a_1, …, a_m)
    
    ∙:    ^→^: c=(c_l, …, c_1) ↦c=(c_1, …, c_l)

and ∙: ^→^ similarly. Also we set 

    ω:^→^: (c, α) ↦ (α, c),

and ω:^→^ similarly. (Here we abuse notations and denote both functions by ω.) Note that these functions are well-defined bijections.

Suppose that Φ^(α,c) = (d, β) for some (α,c) ∈^ and (d,β) ∈^ where α=(a_m, …, a_1) and β=(b_m, …, b_1). We set X={m+1-i | i∈ [1,m], a_i≠, b_i=}. (This set records in which step [(a)] occured when calculating Φ^(α, c).) 
We claim the following.
 Keep the assumptions above. Then we have (α,c) = (ω∘Ψ^_X ∘ω∘Φ^)(α, c)=(ω∘Ψ^_X ∘ω)(d, β), i.e. (c, α) = Ψ^_X(β, d).

 Since the set X depends on (α, c), the lemma above does not show that ω∘Ψ^_X ∘ω∘Φ^ is the identity. However, it shows that one can recover (α, c) from (d,β) and X, which essentially proves Proposition <ref>.

 We may assume that m ≥ 1 and a_m≠. Suppose that it only needs one step. If it is in


  * [(a)]: in this case it is clear that α=(a_1), β=(), d=(a_1)+c, and X={1}. Thus Ψ_X^(β ,d) = Ψ_{1}^(() ,c+(a_1))=(c, (a_1))=(c, α) as desired. (This corresponds to [(b)] of _Ψ.)

  * [(b)]: we have α=(a_1) and X=∅. There exists r ∈ [0,l-1] such that c_r < a_1<c_r+1 and c_r  a_1. (If a_1 <c_1 then we set r=0.) Then we have β=(c_r+1) and d=(c_l, …, c_r+2, a_1, c_r, …, c_1). Since c_r+2<c_r+1<a_1 and c_r+2c_r+1, we have
Ψ_X^(β ,d)
= Φ^((c_r+1) ,(c_1, …, c_r, a_1, c_r+2, …, c_l))
=((c_1, …, c_r, c_r+1, c_r+2, …, c_l), (a_1))
=(c, α) as desired. (This corresponds to [(b)] of _Ψ, and it is still valid when r+2=l+1.)

  * [(a)]: we have X=∅, α=β, c=d, and a_1<a_2<⋯<a_m. There exists r,h such that {c_r, …, c_r+h}∪α is a ladder in  and c_r<a_i<c_r+h for any i. Then it is easy to see that  a_m<⋯<a_2<a_1, {c_r, …, c_r+h}∪α is a ladder in , and c_r+h<a_i<c_r for any i. Thus
Ψ_X^(β ,d)
= Φ^(α ,c)
=(c, α) as desired. (This corresponds to [(a)] of _Ψ.)

  * [(b)]: we have X=∅. As in the description of _Φ, we choose r, h and 0=u(r-1)< u(r)< u(r+1)< ⋯< u(r+h)=m such that c_i<a_u(i-1)+1<⋯<a_u(i) for i∈ [r, r+h] and {c_r, …, c_r+h, a_1, …, a_m} is a ladder in . 
Then it follows that d=(c_l, …, c_r+h+1, a_u(r+h), …, a_u(r), c_r-1, …, c_1) and 

    b_j ={   c_i    if  j=u(i-1)+1  for some  i ∈ [r,r+h],
    
       a_j-1    otherwise.
    .
 
However, it implies that b_1>b_2>⋯>b_m, {a_u(r), …, a_u(r+h), b_1, …, b_m} is a ladder in , and b_u(i-1)+1=c_i>a_u(i-1)+1>⋯>a_u(i) for i∈ [r, r+h]. Also note that c_r-1 x for any x ∈{a_u(r), …, a_u(r+h), b_1, …, b_m} when r>1. Thus

    Ψ_X^(β ,d)   = Φ^((b_1, …, b_m) ,(c_1, …, c_r-1, a_u(r),…, a_u(r+h), c_r+h+1…, c_l))
    
       =((c_1, …, c_r-1, c_r,…, c_r+h, c_r+h+1, …, c_l), (a_1, …, a_m))=(c, α)

as desired. (This corresponds to [(b)] of _Ψ.)


To prove the general case we argue by induction on the number of steps of _Φ for the calculation of Φ^(α,c). Let m∈[0,m-1] be the smallest element such that a_m+1, …, a_m are processed in the same step. Set α=(a_m, …, a_1), α=(a_m, …, a_m+1), β=(b_m, …, b_1) and β=(b_m, …, b_m+1), so that α=α+α and β=β+β. Then there exists d∈^ such that Φ^(α, c)=(d, β) and Φ^(α, d) = (d, β) because of the choice of m.  Thus by induction assumption we have (c, α) = Ψ^_X(β, d) and (d, α)=Ψ^_X(β, d) where X ={i+m-m| i ∈ X∩ [m-m+1, m]} and X=X∩[1,m-m].

Therefore, in order to prove the lemma, it suffices to show that the first step of the calculation of Ψ^_X(β, d) processes b_m+1, …, b_m but not b_m. (See Figure <ref>.) If a_m is in  of _Φ then b_m is in  or  of _Ψ as shown above, in which case the statement is trivial. Thus we assume that a_m is in  of _Φ. Then we have |d|=|d| and X=∅. Thus in particular Ψ^_X(β, d)=Φ^(β, d). We set d=(d_q, …, d_1) and d=(d_q, …, d_1).






[(a)]. Suppose that a_m is in [(a)] of _Φ. Then d=d, β=α and there exist r, h such that {d_r, …, d_r+h, a_m+1, …, a_m} is a ladder in  and d_r≤ x≤ d_r+h for any x∈.

Here we need to check that {b_m}∪{x| x ∈} is not a ladder in , i.e. either m=0 or b_m does not satisfy both b_m b_m+1 and b_m d_r. For the sake of contradiction we suppose otherwise. By Proposition <ref><ref>, it also means that a_m a_m+1. Also a_m cannot be in [(a)] of _Φ.

Suppose that a_m is in [(b)] of _Φ. Then b_m is bumped out from the chain , and thus d_rb_m unless a_m bumps the r-th element of  and a_m=d_r. But this is absurd since it means that a_m<b_m but b_m d_r=a_m.



Now we assume that a_m is in [(a)] of _Φ and '{d_r', …, d_r'+h', a_m', …, a_m} is the corresponding ladder in  where d_r'<⋯<d_r'+j and d_r'<a_m' < ⋯ < a_m<d_r'+h'. Then b_m=a_m, and thus d_r b_m=a_m which is only possible when r'+h'=r, i.e. ∪' is again a ladder in . (Note that a_m=b_m a_m+1.) However, it contradicts the minimality of m.

Assume that a_m is in [(b)] of _Φ. Then a_m=d_i for some i, and as a_m a_m+1 and a_m+1 d_r we should have i<r and a_m=d_i d_r. On the other hand, we always have a_m b_m, and thus d_r b_m by . However, it contradicts the assumption that d_r b_m.


[(b)]. Suppose that a_m is in [(b)] of _Φ and let 
{d_r, …, d_r+h, a_m+1, …, a_m} be the corresponding ladder so that d_r≤ x ≤ a_m for any x∈. Then direct calculation as above shows that ={d_r,…, d_r+h,   b_m+1, …, b_m}. Note that ∪{d_r-1} cannot be a ladder, and thus in order for b_m to be processed with b_m+1, …, b_m we should have that {x| x∈}∪{b_m} is a ladder in , i.e. b_m+1 b_m and x  b_m for any x∈-{b_m+1} by maximality in . By Proposition <ref><ref>, it also means that a_m a_m+1.

Assume that a_m is in [(b)] of _Φ. Then a_m=d_i for some i. Since a_m a_m+1 and d_r a_m+1, we should have r=i and a_m=d_r. But it contradicts that b_m>a_m as b_m b_m+1=d_r.

Assume that a_m is in [(a)] of _Φ. Then b_m=a_m a_m+1≠ b_m+1 which contradicts that x  b_m for any x∈-{b_m+1}.

Assume that a_m is in [(b)] of _Φ and ' is the corresponding ladder where a_m>b_m>x for any x ∈'-{a_m, b_m}. Then a_m=d_i for some i. Since a_m a_m+1 and d_r a_m+1, it follows that r=i. Together with the fact that x  b_m for any x∈-{b_m+1}, it follows that ∪' is again a ladder. However, it contradicts the minimality of m.

We exhaust all the cases and finish the proof.


We are ready to prove Proposition <ref>.
 Recall that we have (α=(a_m, …, a_1), c), (α'=(a'_m, …, a'_1), c')∈ such that a_i =⇔ a_i'= and Φ(α,c) = Φ(α',c'). Let (d, β) ∈ be such a result. Let X={m+1-i| i ∈ [1,m], a_i≠, b_i=}={m+1-i | i ∈ [1,m], a_i'≠, b_i=}. Then by Lemma <ref> we have ω(Ψ^_X(β, d))=(α,c) = (α',c') as desired.






§ PROOF OF THEOREM <REF> AND <REF>
 


 §.§ Preliminary lemmas

Before the proof we first state the following series of lemmas which will be frequently used later on.

Suppose that {a_1, …, a_k} is a ladder in  where k ≥ 2 and a_1< ⋯ < a_k.


  * If b a_k, then either {a_1, …, a_k-1,a_k, b} or {a_1, …, a_k-2, a_k-1, b} is a ladder in .

  * If b a_1, then either {b, a_1, a_2, …, a_k} or {b, a_2, a_3, …, a_k} is a ladder in .


 For (1), first note that  we have b  a_k-2 which follows from  as a_k-2 a_k. Now if b  a_k-1, then  {a_1, …, a_k-1,a_k, b} is a ladder in . Otherwise, we have b  a_k-1 and thus {a_1, …, a_k-2, a_k-1, b} is a ladder in . (2) is proved similarly.


 
Suppose that {a_1, …, a_k} is a ladder in  where a_1< ⋯ < a_k. If x ∉{a_1, …, a_k}, a_1 x, and no one is climbing a ladder in , then a_i x and a_i+1 < x for i ≤ k-3.

 Since no one is climbing a ladder in , we have a_kx. Since a_k-2 a_k, this means that a_k-2 < x by . Now suppose that there exists i ≤ k-3 such that a_i x (and thus k≥ 5). By , it is equivalent to assuming that a_k-3 x. Since a_k-3 a_k-1, this means that x<a_k-1 by . Thus we have x  a_k-1, a_k and x  a_k-2, a_k-3. Since a_k-4 a_k-2, we also have x  a_k-4 by . Now one may check that  restricted to {a_k-4, a_k-3, a_k-2, x, a_k} is isomorphic to _(3,1,1),5, which is a contradiction. It remains to check that a_i<x for i ≤ k-2, and thus suppose otherwise (and thus k≥ 4). It implies that a_i-1 a_i by  since a_i-1 x by above (or by assumption if i=2), which is a contradiction.



  Suppose that {b_1,…, b_k, a_1, a_2, a_3} is a ladder in  where b_1<⋯<b_k<a_1<a_2<a_3, x ∉{b_1,…, b_k, a_1, a_2, a_3}, b_1  x, and no one is climbing a ladder in . Then the relation between {a_1, a_2} and x falls into one of the following. (Also see Figure <ref>.)


  * a_1 x and a_2 x

  * a_1 x and a_2 x

  * a_1 x and a_2 x

  * a_1 x and a_2 x


 By Lemma <ref> we may assume that k=1. Then one may check case-by-case using  and a_3 x since otherwise x is climbing {b_1,…, b_k, a_1, a_2, a_3}.






 
Suppose that {a_1, …, a_k} is a ladder in  where a_1< ⋯ < a_k and k≥ 4, x ∉{a_1, …, a_k}, and no one is climbing a ladder in .


If a_2 x, then it falls into one of the following cases. (Also see Figure <ref>)


  * a_1  x, a_3 x

  * k=4, a_1 x, a_3  x, a_4 x

  * k=4, a_1 x, a_3  x, a_4  x









 Using Lemma <ref>, , and the assumption that x is not climbing {a_1, …, a_k} in , one may deduce that the only possibilities are the above three cases and possibly [k=5, a_1 x, a_3  x, a_4  x, a_5  x] (see the last diagram in Figure <ref>). However, the latter is impossible since in this case a_3 is climbing the ladder {a_1, a_2, x, a_5}.











 §.§ Proof of Theorem <ref><ref>

We are ready to prove Theorem <ref><ref>.
Since each column of PT (resp. QT) is a chain with respect to  (resp. the usual order), we may restrict our attention to comparing elements in two adjacent columns of PT and QT, respectively. To this end, we set α, β∈ to be α=(a_m, a_m-1, …, a_1), β=(b_m, …, b_1) and set PT=(PT_1, PT_2) where PT_1, PT_2 ∈ are defined to be PT_1=(d_p, …, d_1) and PT_2=(e_q, …, e_1). We assume that Φ(α, ∅) = (PT_1, β), Φ(β, ∅) = (PT_2, γ) for some γ∈. We define QT=(QT_1, QT_2) to be as in the algorithm of . 


nosmalltableaux




We argue by induction on m=|α|. There is nothing to prove when its length is 0, and thus suppose that m≥ 1 and the statement is true up to m-1. We set m<m (specified later), and define α=(a_m, …, a_1), β=(b_m, …, b_2, b_1), PT=(PT_1, PT_2) where PT_1=(d_p, …, d_2, d_1), PT_2=(e_q, …, e_2, e_1), QT=(QT_1, QT_2), and γ∈ analogously. (See Figure <ref>.) 

It suffices to assume that a_m≠. For a_m in [(a)], we set m=m-1. Then we have p=p+1, q=q, PT_1=(a_m)+PT_1, QT_1=(m)+QT_1, PT_2=PT_2, and QT_2=QT_2. In this case there is nothing to prove. From now on, we divide all the remaining possibilities into the following cases. (Note that we have p=p and QT_1=QT_1 in these cases.)





  * a_m is in [(b)] (see Figure <ref>): we set m m-1. There exists ϱ∈ [1,p] such that d_ϱ-1 < a_m<d_ϱ and d_ϱ-1 a_m. (Here we set d_0=-.) Here it is easy to observe that Φ((a_m), PT_1)=(PT_1, (b_m)). Also we have d_ϱ=a_m<d_ϱ, d_k=d_k if k≠ϱ, β=(b_m-1, …, b_2, b_1), and b_m=d_ϱ.






  * a_m is in [(a)] (see Figure <ref>): we set m∈ [0,m-1] to be the smallest integer such that a_m+1, …, a_m are processed in the same step and a_i  a_i+1 if i∈ [m+1,m-1]. Then,


  * Φ((a_m, …, a_m+1), PT_1)=(PT_1, (b_m, …, b_m+1)),

  * there exists ϱ∈ [1, p-1] such that d_ϱ< a_m+1<⋯< a_m<d_ϱ+1, and

  * _ad{d_ϱ, a_m+1,⋯, a_m,d_ϱ+1} is a ladder in .

Then we have PT_1=PT_1, β=(b_m, …, b_2, b_1),  and b_i=a_i for i ∈ [m+1, m].





  * a_m is in [(b)] (see Figure <ref>): we set m∈ [0,m-1] to be the smallest integer such that a_m+1, …, a_m are processed in the same step and a_i  a_i+1 if i∈ [m+1,m-1]. Then,


  * Φ((a_m, …, a_m+1), PT_1)=(PT_1, (b_m, …, b_m+1)),

  * there exists ϱ∈ [m-m,p] such that d_σ+1< a_m+1<d_σ+2<a_m+2<⋯< d_ϱ<a_m where σϱ-m+m,

  * either ϱ=q or d_ϱ+1 a_m (by maximality in ), and

  * _ad{d_σ+1, a_m+1,d_σ+2,a_m+2,…, d_ϱ,a_m} is a ladder in .

Then we have d_i=d_i for i ∈ [1,σ]∪[ϱ+1, p] and d_i=a_i+m-ϱ for i ∈ [σ+1, ϱ], β=(b_m, …, b_2, b_1), and b_i=d_i+ϱ-m for i ∈ [m+1, m].









The condition Φ((a_m, …, a_m+1), PT_1)=(PT_1, (b_m, …, b_m+1)) implies that in each case QT_2 is obtained from QT_2 by adding some entries in [m+1,m] in order, which in turn means that QT satisfies the standard Young tableau condition if and only if p≥ q. Thus in each case it suffices to prove that p≥ q and d_i e_i for i∈ [1,q]. Now we also divide possibilities into following cases. (Here we use Lemma <ref> in each case. Note that we always have b_m+1<⋯< b_m.)




  * b_m+1 is in [(a)]: we have e_q b_i for i ∈ [m+1, m]. Thus e_i = e_i for i ∈ [1, q]

  * b_m+1 is in [(b)]: there exists r∈[1,q] such that e_r-1<b_m+1<e_r and  e_r-1 b_m+1. (Here we set e_0=-.) Then we have e_i=e_i for i ∈ [1, r-1].





  * b_m+1 is in : let m' ∈ [1,m+1] be the smallest integer such that b_m', …, b_m+1 are processed in the same step (thus in particular b_m'<⋯<b_m+1), and we set PT_2=(e_q, …, e_2, e_1) ∈ to be “PT_2 right before the step processing b_m', …, b_m”, i.e. such that Φ((b_m, …, b_m'), PT_2) = (PT_2, -) and also Φ((b_m, …, b_m'), PT_2) = (PT_2, -). (As  does not increase the length of the chain, PT_2 is of length q. See Figure <ref>.)







Also, we set r,s≥ 1 and 0≤ m'-1=u(r)<⋯<u(r+s)=m+1 to be such that e_r+j<b_u(r+j-1)+1<…< b_u(r+j) for j ∈ [1,s] and

    _be{e_r+1, …, e_r+s, b_m',b_m'+1, …, b_m+1}

is a ladder in . Note that we always have e_i=e_i=e_i for i ∈ [1, r] by Lemma <ref> because e_r b_j for j ∈ [m', m] by assumption. Also one may easily check that e_i=e_i for i ≥ r+s+1. Here we list all the possibilities. (Also see Figure <ref>.) 






  * [(a)], u(r+s-1)=m. (See Figure <ref>.) This case includes s=1 and u(r)+1=u(r+1)=m+1. This means that b_m', …, b_m were originally in (a) as well. We have r+s+1≤ q≤ q, e_i=e_i for all i and also e_i=e_i for i ∈ [r+1, r+s-1] by Lemma <ref> because e_r+s-1 b_j for j ∈ [m+1, m]. 





  * [(a)], u(r+s-1)< m. (See Figure <ref>.) This means that b_m', …, b_m were originally in (b). We have r+s+1≤ q≤ q, e_r+i=b_u(r+i) for i ∈ [1, s-1], e_r+s=b_m,  and e_i=e_i for i ∈ [r+1, r+s] by Lemma <ref> because (a) does not alter the given chain and e_r+s b_j for j ∈ [m+1, m] by assumption.





  * [(b)], u(r+s-1)< m. (See Figure <ref>.)  This means that b_m', …, b_m were originally in (b) as well. We have e_i=e_i for i ∈ [r+1,r+s-1] and e_r+s=b_m by Lemma <ref> since e_r+s-1 b_j for j ∈ [m+1, m] by assumption.





  * [(b)], u(r+s-1) = m. (See Figure <ref>.) This case includes s=1 and u(r)+1=u(r+1)=m+1. This means that b_m', …, b_m were originally in (a). We have e_i=e_i for any i and e_r+i=b_u(r+i) for i ∈ [1, s-1] by Lemma <ref> because b_u(r+s-1)=b_m b_j for j ∈ [m+1, m]. Also, it is easy to observe that e_r+i <e_r+i for i ∈ [1,s-1].






From now on we verify the conditions p≥ q and d_i e_i for i∈ [1,q] in each case. Note that p=p≥ q and d_ie_i for any i by induction assumption, and thus p≥ q if q=q and d_i e_i if d_i=d_i, e_i=e_i.




  §.§.§  a_m is in 
 We have m=m-1. Here it suffices to check d_k e_k only for k satisfying k≤ q and either k> q or e_k < e_k, which follows from , induction assumption, and the fact that d_k ≤ d_k for k ∈ [1,p].

I.i. b_m is in [(a)]: we have q=q+1 and PT_2=(b_m)+PT_2. First in this case p ≥ϱ≥ q since e_q-1=e_q b_m=d_ϱ. Now it suffices to check d_q e_q. Now if ϱ>q, then e_q=d_ϱd_q =d_q. If ϱ=q, then e_q=d_ϱa_m=d_ϱ.

I.ii.  b_m is in [(b)]: we have q=q, and e_i≠ e_i only when i=r in which case e_r=b_m=d_ϱ. Thus it suffices to check d_r e_r. Note that r≤ϱ since d_ϱ =b_m e_r-1. If r<ϱ then d_r=d_rd_ϱ=e_r. If r=ϱ then d_ϱ=a_m d_ϱ=e_r thus the condition still holds. 

I.iii.  b_m is in [(a)], u(r+s-1)=m-1: we have PT_2=PT_2, and thus there is nothing to check.

I.iv.  b_m is in [(a)], u(r+s-1)< m-1: in this case we have q=q,  e_r+s = b_m-1, e_r+j = b_u(r+j) for j ∈ [1,s-1], and e_k=e_k if k∉[r+1, r+s]. Thus it suffices to check d_k e_k for k∈ [r+1, r+s]. Note that r+s≤ϱ since e_r+s=b_m-1<b_m=d_ϱ.
First suppose that k∈ [r+1,r+s], k< ϱ, and d_k  e_k. Then as d_k =d_k d_ϱ=b_m it implies that d_k is climbing _be in , which is a contradiction. 
Now suppose k∈ [r+1,r+s], k≥ϱ and d_k e_k (which forces that k=ϱ=r+s). Note that _be∪{e_r+s+1} is a ladder in  since b_m is in [(a)] and _be∪{e_r+s+1, d_ϱ+1} is also a ladder as d_ϱ+1=d_ϱ+1 d_ϱ=b_m and d_ϱ+1=d_ϱ+1e_r+s+1=e_r+s+1. Since d_ϱ d_ϱ+1, we see that d_ϱ is climbing the ladder _be∪{e_r+s+1, d_ϱ+1} which is a contradiction. (See Figure <ref>.)



I.v.  b_m is in [(b)], u(r+s-1)< m-1: we have  q=q, e_r+s=b_m>b_m-1=e_r+s and e_k=e_k for k ≠ r+s, and thus there is nothing to check.

I.vi.  b_m is in [(b)], u(r+s-1) = m-1: we have q=q, e_r+i<b_u(r+i)=e_r+i for i ∈ [1,s] and e_k=e_k for k ∉[r+1,r+s], and thus there is nothing to check.






  §.§.§  a_m is in 

Recall that b_i=d_i+ϱ-m for i ∈ [m+1, m]. Since d_i=d_i for all i, similarly to above it suffices to check d_k e_k only for k satisfying k≤ q and either k> q or e_k < e_k. 

II.i. b_m+1 is in [(a)]: direct calculation shows that q=q+1 and PT_2=(a_m)+PT_2. First we have p≥ϱ+1≥ q+1=q since d_ϱ+1>a_m+1=b_m+1 e_q. It remains to check d_q e_q. If ϱ+1=q, then d_ϱ+1 a_m=e_q, and thus the result holds. Otherwise, i.e. if ϱ+1>q, then d_q≤ d_ϱ<a_m=e_q, and thus again the result holds.



II.ii. b_m+1 is in [(b)]:  Note that ϱ+1 ≥ r since d_ϱ+1>a_m+1=b_m+1 e_r-1. First assume that r=q or e_r+1 b_m= a_m. (This includes the case m=m+1.) Then we have q=q, e_r=a_m, and e_k =e_k for k ≠ r, and thus it suffices to show that d_r e_r = a_m. However, if d_r  a_m then d_ϱ+1≥ d_r  a_m thus d_ϱ+1 a_m, which contradicts the assumption.

From now on we suppose that e_r+1a_m (so that m≥ m+2). In this case a_m>e_r by  since e_r+1a_m and e_r+1 e_r. First we assume m=m+2. Then we have a_m e_r+1; otherwise we should have a_m>e_r+1, but it is impossible by  since e_r+1 e_r >a_m-1 but a_m  a_m-1. Now direct calculation shows that q=q, e_r=a_m-1, and e_k=e_k for k≠ r, and thus it suffices to show that d_r e_r=a_m-1. If ϱ+1>r, then we have d_r ≤ d_ϱ<a_m-1=e_r, and thus we are done. Now we claim that ϱ+1≠r; first note that d_ϱ > e_r-1 since a_m-1 e_r-1=e_r-1 and a_m-1 d_ϱ. Together with d_ϱ =d_ϱe_ϱ=e_r-1, this means that d_ϱ e_r-1. Also e_r+1 a_m-1 since e_r+1=e_r+1 e_r >a_m-1. But this means that {e_r-1, d_ϱ, a_m-1, a_m, e_r+1} is a ladder in  which e_r is climbing (e_r+1 e_r e_r-1), which is a contradiction. (See Figure <ref>.)




It remains to assume that m≥ m+3. We claim that e_ra_m+1. Otherwise, a_m-1 <e_r by Lemma <ref> which in turn implies that a_m-1 e_r+1 and a_m  e_r+1 by assumption. However, it means that {a_m+1, …, a_m, e_r+1} is a ladder that e_r is climbing, which is a contradiction. Since e_r  > a_m+1 by assumption, it follows that e_r a_m+1.  Now we apply Lemma <ref> to _ad (of length m-m+2≥ 5) and e_r and conclude that d_ϱ e_r and a_m+2 e_r.

Note that e_r+1 a_m+1 by  as e_r e_r+1 and e_r>a_m+1. Thus by Lemma <ref> we have e_r a_j for j∈[m+1,m-2] and we may apply Lemma <ref> to {a_m-1, a_m} and e_r+1. As a_m e_r+1 by assumption, case (<ref>.4) is excluded. In other cases, direct calculations shows that e_r=a_m+1, e_k=e_k if k ∉{r, r+1}, and


  * (<ref>.1): either e_r+1=e_r+1 or e_r+1=a_m>e_r+1.

  * (<ref>.2): e_r+1=a_m.

  * (<ref>.3): e_r+1=e_r+1.

(See Figure <ref>.) In any case we have q=q. Thus it suffices to check that d_r e_r, and d_r+1e_r+1 in case (<ref>.2).
Note that here we have ϱ+1>r since d_ϱ+1 a_m-1≥ a_m+2>e_r. If d_r  e_r = a_m+1, then since d_r  d_ϱ+1 it means that d_r is climbing _ad, which is a contradiction. Also in case (<ref>.2) we have d_r+1e_r+1=a_m by  since d_r+1≤ d_ϱ+1 and d_ϱ+1 a_m. 




II.iii. b_m+1 is in [(a)], u(r+s-1)=m: when m=m+1, then PT_2=PT_2, and thus there is nothing to check. Thus suppose that m≥ m+2. Note that e_r+s a_m+1=b_m+1 since b_m+1 is in [(a)] and u(r+s-1)+1=m, and ϱ≥ r+s since d_ϱ+1 a_m+1>e_r+s. First assume that e_r+s a_m+2. Then _ad∪{e_r+s}-{d_ϱ} is a ladder and e_r+s e_r+s+1, and thus by Lemma <ref> we have e_r+s a_j for j∈[m+1,m-2] and we may apply Lemma <ref> to {a_m-1, a_m} and e_r+s+1. (<ref>.4) is impossible since b_m+1 is in [(a)], i.e. there exists j ∈ [m+1, m] such that a_j=b_j e_r+s+1. In other cases, direct calculation shows that e_k=e_k if k ≠ r+s+1 and


  * (<ref>.1): either e_r+s+1=e_r+s+1 or e_r+s+1=a_m>e_r+s+1.

  * (<ref>.2): e_r+s+1=a_m.

  * (<ref>.3): e_r+s+1=e_r+s+1.

(See Figure <ref>.) In any case we have q=q. Thus we only need to check that d_r+s+1e_r+s+1=a_m in case (<ref>.2). But this holds by  since d_r+s+1≤ d_ϱ+1 and d_ϱ+1 a_m=e_r+s+1. 



It remains to assume that e_r+s a_m+2. Since e_r+s e_r+s+1, this means that a_m+2<e_r+s+1 by . 
On the other hand,  in this case b_m+1 is in [(a)] only if a_m+1 e_r+s+1. Thus we may apply Lemma <ref> to _ad and e_r+s+1. Here (<ref>.3) is the only one satisfying a_m+2<e_r+s+1, in which case m=m+2 and PT_2=PT_2. (See Figure <ref>.) Thus there is nothing to prove.



II.iv. b_m+1 is in [(a)], u(r+s-1) < m:  first assume that m=m+1. Then q=q, e_r+s = b_m-1, e_r+j = b_u(r+j) for j ∈ [1,s-1], and e_j=e_j if j ∉[r+1, r+s]. Thus it suffices to check d_k e_k for k∈ [r+1, r+s]. Since d_ϱ+1=d_ϱ+1> a_m=b_m>b_m-1=e_r+s, we have r+s≤ϱ+1. Also since d_ϱ+1 a_m=b_m, by Lemma <ref> either _be∪{d_ϱ+1} or _be∪{d_ϱ+1}-{b_m} is a ladder. Now if d_k  e_k for some k ∈ [r+1,r+s], k<ϱ+1 then as d_k  d_ϱ+1 it implies that d_k is climbing a ladder, which is impossible. It remains to check the case when k=r+s=ϱ+1. We claim that this is impossible. First, ϱ+2 = r+s+1 ≥ q ≥ p, and thus d_ϱ+2 is well-defined. Furthermore, d_ϱ+2 = d_ϱ+2e_r+s+1=e_r+s+1, and thus d_ϱ+1<e_r+s+1 by  since d_ϱ+2 d_ϱ+1. On the other hand, if d_ϱ+2<e_r+s+1 then a_m <d_ϱ+1 d_ϱ+2<e_r+s+1 which implies b_m = a_m  e_r+s+1, but it contradicts the assumption that b_m is in [(a)]. Therefore, we have d_ϱ+1<e_r+s+1<d_ϱ+2 and also d_ϱ+2 e_r+s+1. Now one may check that  restricted to {d_ϱ, a_m, d_ϱ+1,e_r+s+1, d_ϱ+2} is isomorphic to _(3,1,1),5, which is a contradiction. (See Figure <ref>.)





Now assume that m≥ m+2. First d_ϱ+1=d_ϱ+1 a_m+1>b_m=e_r+s, and thus ϱ≥ r+s. As _be is a ladder of size ≥ 3 by assumption, _be∪(_ad-{d_ϱ}) is also a ladder by Lemma <ref>. Now by Lemma <ref> we have e_r+s+1 x for any x∈_be∪(_ad-{d_ϱ})-{a_m-1, a_m, d_ϱ+1}, and we may apply <ref> to {a_m-1, a_m} and e_r+s+1. Keep in mind that b_m+1 is in [(a)] which implies that (<ref>.4) is impossible. Direct calculation shows that e_r+j = b_u(r+j) for j ∈ [1,s-1], e_r+s = b_m,  e_k=e_k if k∉[r+1, r+s+1} and


  * (<ref>.1): either e_r+s+1=e_r+s+1 or e_r+s+1=a_m>e_r+s+1.

  * (<ref>.2): e_r+s+1=a_m.

  * (<ref>.3): e_r+s+1=e_r+s+1.

(See Figure <ref>.) In any case we have q=q. 
Thus it suffices to show that d_k e_k if k ∈ [r+1,r+s] and d_r+s+1e_r+s+1 in case (<ref>.2). The former is clear. Indeed, if k ∈ [r+1,r+s] then k<ϱ+1, and thus d_k  d_ϱ+1. Therefore, if d_k  e_k then d_k is climbing _be∪ (_ad-{d_ϱ}) which is a contradiction. Now if we are in case (<ref>.2) then d_ϱ+1≥ d_r+s+1 and d_ϱ+1 a_m = e_r+s+1, and thus d_r+s+1e_r+s+1.




II.v. b_m+1 is in [(b)], u(r+s-1)< m: note that _be a_m+1, b_m, e_r+s, and thus _be is of length ≥ 3. If m>m+1 then _be∪ (_ad-{d_ϱ}) is a ladder by Lemma <ref>, and thus so is _be∪ (_ad-{d_ϱ,d_ϱ+1}). If m=m+1 then _be∪ (_ad-{d_ϱ,d_ϱ+1})=_be is clearly a ladder. Then direct calculation shows that q=q, e_r+s=b_m>b_m-1=e_r+s, and e_i = e_i otherwise, and thus there is nothing to check here.

II.vi. b_m+1 is in [(b)], u(r+s-1)= m: first assume that _be∪(_ad-{d_ϱ, d_ϱ+1}) =_be⊔{a_m+2, …, a_m} is a ladder. Then direct calculation shows that e_r+i=b_u(r+i)>e_r+i for i ∈ [1,s-1], e_r+s = b_m > e_r+s, and e_i=e_i if i ∉[r+1, r+s], and thus there is nothing to check. Thus suppose otherwise, i.e. _be∪{a_m+2, …, a_m} is not a ladder and in particular m≥ m+2. Since {a_m+1, …, a_m, d_ϱ+1} is a ladder of length ≥ 3, by Lemma <ref> the length of _be should be at most 2, i.e. _be = {e_r+1, a_m+1} and also e_r+1 a_m+2. Also we have either q=r+1 or e_r+2 a_m+1=b_m+1 since b_m+1 is in [(b)]. If q>r+1 then we may apply Lemma <ref> to {a_m-1, a_m} and e_r+2. Again since b_m+1 is in [(b)], the only possible cases is (<ref>.4), i.e. a_m  e_r+2. Now direct calculation shows that q=q, e_r+1=a_m>e_r+1 and e_i=e_i otherwise. Thus there is nothing to check. (See Figure <ref>.)








  §.§.§  a_m is in 

Recall that b_i=a_i for i ∈ [m+1, m]. Here, we have d_i=d_i if i∈[1,σ]∪[ϱ+1,p]. Thus here we only need to check that p≥ q when q≠ q and d_k e_k if k≤ q and either k> q, e_k < e_k, or k ∈ [σ+1, ϱ]. 



III.i. b_m+1 is in [(a)]: direct calculation shows that q=q+m-m and PT_2=(d_ϱ, …, d_σ+1)+PT_2. Note that σ≥ q since d_σ+1=b_m+1 e_q, and thus in particular q≤σ+m-m=ϱ≤ p. It remains to check d_k e_k for k∈ [q+1,q]. However, since e_q+i=b_m+i=d_σ+i a_m+i= d_σ+i and d_σ+i≥ d_q+i for i ∈ [1, q-q], we have d_q+ie_q+i by  as desired.


III.ii. b_m+1 is in [(b)]: we claim that


  * q=max{q, r+m-m-1},

  * e_r+i=b_m+i+1=d_σ+i+1 for i ∈ [0, m-m-1] and e_k=e_k otherwise, and

  * b_m+i+1 are in (either (a) or (b)) if i<m-m-1.

(See Figure <ref>.) Note that the first part follows from the other parts. To this end, we use induction on i. If i=0 then it is obvious by assumption. Now assume that the result is true up to i-1. First suppose that i<m-m-1. If b_m+i+1 >e_r+i, then we have b_m  b_m+i+1 >e_r+i e_r+i-1=b_m+i which means that e_r+i is climbing _ad, a contradiction. Thus b_m+i+1 <e_r+i, and direct calculation shows that b_m+i+1 is in  and e_r+i=b_m+i+1.


Finally, we assume i=m-m-1>0. If q<r+m-m-1 or b_m<e_r+m-m-1 then b_m is in  and the result is obvious, and thus suppose otherwise. If e_r+m-m-1 b_m, then b_m  e_r+m-m-1 b_m-1, a_m-1 b_m, and a_m-1 b_m-1, which contradicts Lemma <ref>(1). Thus we have e_r+m-m-1 b_m. If q<r+m-m or b_m  e_r+m-m, then b_m is in [(b)] and e_r+m-m-1=b_m, and thus we are done. It remains to consider the case when q≥ r+m-m and e_r+m-m b_m, so that b_m is in [(a)]. But then a_m-1 e_r+m-m by Lemma <ref>(1) applied to b_m-1, e_r+m-m-1, e_r+m-m, and a_m-1. This means that {b_m-1, a_m-1, b_m, e_r+m-m} is a ladder in  which e_r+m-m-1 is climbing, which is a contradiction. (See Figure <ref>.)








Note that σ+1 ≥ r as d_σ+1=b_m+1 e_r-1. Thus r+m-m-1≤σ+m-m=ϱ≤ p, which means that q≤ p. It remains to check that d_k e_k for k ∈ [σ+1, ϱ] ∪ [r, r+m-m-1], k≤ q. If k ∈ [σ+1, ϱ] then we have d_k=a_k+m-ϱ b_k+m-ϱ=e_r+k+m-ϱ-m-1=e_r+k-σ-1 and e_r+k-σ-1≤ e_k, which means that d_k e_k by . Similarly, if k ∈ [r, r+m-m-1] then d_k+σ+1-r e_k and d_k+σ+1-r≥ d_k, and thus d_k e_k by .


III.iii. b_m+1 is in [(a)], u(r+s-1)=m: note that σ+1 ≥ r+s since d_σ+1=b_m+1 >e_r+s. First we assume that m=m+1, in which case PT_2=PT_2. Here it suffices to check that d_k e_k for k =σ+1=ϱ, k≤ q.
It is obvious when σ+1=ϱ>r+s by  since d_ϱ=a_m b_m and b_m<e_r+s+1≤ e_ϱ. Now we assume that k=ϱ=r+s. Then ϱ+1≤ p since ϱ+1=r+s+1≤ q ≤ p, and d_ϱ+1 > e_r+s+ 1 by  since d_ϱ+1=d_ϱ+1 d_ϱ=b_m and b_m e_r+s+1. As d_ϱ=d_ϱ+1e_r+s+1=e_r+s+1 by assumption, it means that d_ϱ+1 e_r+s+1, i.e. {e_r+s, b_m, e_r+s+1, d_ϱ+1} is a ladder. Now if d_ϱ e_r+s then d_ϱ is climbing {e_r+s, b_m, e_r+s+1, d_ϱ+1}, which is a contradiction. (See Figure <ref>.)




Now we show that the case m>m+1 is impossible. For the sake of contradiction we assume this condition.

Here b_m+1 is in [(a)] only if e_r+s+1 b_m+1, which in turn implies that e_r+s+1 <b_m+2 by . Since b_m+1 e_r+s, either _ad∪{e_r+s} or _ad∪{e_r+s}- {b_m+1} is a ladder by Lemma <ref>. If m>m+2 or _ad∪{e_r+s} is a ladder then b_m+1 e_r+s+1 by Lemma <ref> since e_r+s e_r+s+1, but this is a contradiction. Thus m=m+2 and _ad∪{e_r+s}- {b_m-1} is a ladder, i.e. e_r+s a_m-1. Now we apply Lemma <ref> to {a_m-1, b_m} and e_r+s+1; the only possible case is (<ref>.1) since e_r+s+1 <b_m. However, in this case b_m-1 is in [(b)] (together with b_m), which is a contradiction. (See Figure <ref>.)





III.iv. b_m+1 is in [(a)], u(r+s-1)< m:  first we assume that m=m+1, in which case q=q, e_r+i=b_u(r+i) for i ∈ [1,s-1], e_r+s=b_m-1, and e_i=e_i otherwise. Thus here it suffices to check that d_k e_k for k∈{ϱ}∪ [r+1, r+s], k ≤ q. Note that ϱ≤  r+s since d_ϱ=b_m > b_m-1=e_r+s. For k <ϱ,  first note that either _be∪{d_ϱ} or _be∪{d_ϱ}-{b_m} is a ladder by Lemma <ref> since b_m  a_m=d_ϱ. Thus if d_k  e_k then d_k is climbing a ladder as d_k  d_ϱ, which is a contradiction. It remains to consider the case k=ϱ. If ϱ<r+s, then it follows from  since d_ϱ =a_m  b_m and b_m <e_r+s+1=e_r+s+1≤ e_ϱ. If k=ϱ=r+s, then first ϱ+1=r+s+1 ≤ q≤ p, and d_ϱ+1 =d_ϱ+1 d_ϱ=b_m. Since d_ϱ+1e_r+s+1 and e_r+s+1 b_m, by  it follows that d_ϱ+1 e_r+s+1, i.e. _be∪{e_r+s+1, d_ϱ+1} is a ladder in . Now if d_ϱ e_r+s then as d_ϱ d_ϱ+1 it implies that d_ϱ is climbing a ladder, which is contradiction. (See Figure <ref>.)









Now assume that m>m+1, and we prove that this is impossible. Indeed,  b_m+1 e_r+s+1 =e_r+s+1 since b_m+1 b_m+2 and b_m+1 is in [(a)]. However, since _be∪_ad is a ladder by Lemma <ref> and e_r+s=e_r+s e_r+s+1=e_r+s+1, we should have b_m+1 e_r+s+1 by Lemma <ref>. This is a contradiction. (See Figure <ref>.)







III.v. b_m+1 is in [(b)], u(r+s-1)< m: first we assume that m=m+1, in which case q=q, e_r+s=b_m>b_m-1=e_r+s, and e_i=e_i otherwise. Thus here it suffices to check that d_k e_k for k=ϱ, k ≤ q. Note that ϱ≥ r+s since d_ϱ=b_m > b_m-1=e_r+s, which implies e_ϱ≥ e_r+s. As d_ϱ=a_m  b_m=e_r+s, the result follow from .




Now we assume that m> m+1. Then _be∪_ad is a ladder by Lemma <ref>, and thus if q≤ r+s+1 then b_m+1 e_r+s+1=e_r+s+1 by Lemma <ref> as e_r+s+1=e_r+s+1 e_r+s. Now almost the same argument as in  applies here and one can show that q=max{q, r+s+m-m-1}, e_r+s+i=b_m+i+1=d_σ+i+1 for i ∈ [0,m-m-1], and e_i = e_i otherwise. First, we have σ+1≥ r+s since d_σ+1=b_m+1>b_m=e_r+s. Thus r+s+m-m-1≤σ+m-m=ϱ≤ p, which means that q≤ p. It remains to verify that d_k e_k for k ∈ [σ+1, ϱ] ∪ [r+s, r+s+m-m-1], k ≤ q. If k ∈ [σ+1, ϱ] then we have d_k=a_k+m-ϱ b_k+m-ϱ=e_r+s+k+m-ϱ-m-1=e_r+s+k-σ-1 and e_r+s+k-σ-1≤ e_k, which means that d_k e_k by . Similarly, if k ∈ [r+s, r+s+m-m-1] then d_k+σ+1-r-s e_k and d_k+σ+1-r-s≥ d_k, and thus d_k e_k by .






III.vi. b_m+1 is in [(b)], u(r+s-1)= m: note that σ+1 ≥ r+s as d_σ+1=b_m+1>e_r+s. First suppose that r+s+1≤ q and e_r+s+1 b_m+1. Since b_m+1 is in [(b)], this forces that m >m+1 and e_r+s+1 b_m+2. On the other hand, by Lemma <ref> either _ad∪{e_r+s} or _ad∪{e_r+s}-{b_m+1} is a ladder, 
thus we may apply Lemma <ref> to {a_m-1, b_m} and e_r+s+1. The only possible case is when m=m+2 and we are in (<ref>.1), i.e. a_m-1 e_r+s+1 and e_r+s+1 b_m.

Now direct calculation shows that q=q, e_r+i=b_u(r+i)>e_r+i for i ∈ [1,s-1], e_r+s=b_m-1>e_r+s, e_r+s+1=b_m >e_r+s+1, and e_i=e_i otherwise, and thus it suffices to check d_k e_k for k={σ+1=ϱ-1,ϱ}, k ≤ q. We have d_ϱ-1e_ϱ-1 by  since d_ϱ-1=a_m-1 b_m-1=e_r+s and e_ϱ-1≥ e_r+s and similarly d_ϱe_ϱ  since d_ϱ=a_m b_m=e_r+s+1 and e_ϱ≥ e_r+s+1. (See Figure <ref>.)



This time suppose that either r+s+1>q or e_r+s+1 b_m+1. Then almost the same argument as in  applies here and one can show that q=max{q, r+s+m-m-1}, e_r+i=b_u(r+i)>e_r+i for i ∈ [1,s-1], e_r+s=b_m+1>e_r+s, e_r+s+i=b_m+i+1=d_σ+i+1 for i ∈ [1,m-m-1], and e_i = e_i otherwise. First, we have σ+1≥ r+s since d_σ+1=b_m+1>b_m=e_r+s. Thus r+s+m-m-1≤σ+m-m=ϱ≤ p, which means that q≤ p.







 It remains to verify that d_k e_k for k ∈ [σ+1, ϱ] ∪ [r+s+1, r+s+m-m-1], k ≤ q. If k ∈ [σ+1, ϱ] then we have d_k=a_k+m-ϱ b_k+m-ϱ=e_r+s+k+m-ϱ-m-1=e_r+s+k-σ-1 and e_r+s+k-σ-1≤ e_k, which means that d_k e_k by . Similarly, if k ∈ [r+s+1, r+s+m-m-1] then d_k+σ+1-r-s e_k and d_k+σ+1-r-s≥ d_k, and thus d_k e_k by .





We exhausted all the possibilities and thus proved Theorem <ref><ref>.




 §.§ Proof of Theorem <ref><ref>

Let us write w=(a_n, …, a_1). Then n-i ∈_(w) if and only if a_i  a_i+1. We first show that a_i  a_i+1 if and only if i ∈(QT). The result is trivial if i and i+1 are in the same column of QT, and thus suppose otherwise. Then by Proposition <ref>, i+1 is in the former column than that of i. Since QT is a standard Young tableau by part <ref>, it follows that i is in the upper row than i+1, and thus i∈(QT). Now suppose that a_i a_i+1. By Proposition <ref>, i should be in the former column than that of i+1. In this case it is easy to see that i+1 cannot be in the lower row than that of i because of the standard Young tableau condition, and thus i∉(QT).



 §.§ Proof of Theorem <ref><ref>

For w∈_n, let (w)=(PT=(PT_1, …, PT_p), QT) and choose w=w_0, w_1, …, w_p =(, …, ) ∈ such that Φ(w_i, ∅) = (PT_i+1, w_i+1) for i ∈ [0,p-1]. Then by Proposition <ref><ref>,  we have (recall that α^f is the word obtained from α by removing )

    w PT_1+w_1^f PT_1+PT_2+w_2^f⋯ PT_1+PT_2+⋯ PT_p=(PT)

as desired.



 §.§ Proof of Theorem <ref><ref>

By Theorem <ref><ref> if (w) = (PT, QT) then w ∼_(PT). Thus by Proposition <ref> we have _(w) = _((PT)). Furthermore, if w ∼_ w' and (w') = (PT', QT') then by the same reason _((PT)) ∼__(w) ∼__(w') ∼__((PT')). 

Thus it suffices to show that _((T)) equals the length of the first column of T for any T ∈. Let us denote by l the length of the first column of T. Since the first column of T is a subword of genuine -inversions in (T), it follows that _((T))≥ l. Now for the sake of contradiction suppose _((T))> l. Then by pigeonhole principle there exists a, b ∈ [1,n] such that (a,b) ∈_((T)), the column containing a is on the left of that of b, and b is not in the upper row than a.

Let c be the element located in the intersection of the row of a and the column of b. We claim that (a,c) ∈_((T)). Indeed, if b=c then we are done, and thus suppose otherwise. As b and c are in the same column we have b c. Since a b by assumption, if (a,c)∉_((T)) then by Lemma <ref> there exists a subword ae_1⋯ e_k c in (T) such that a  e_1 ⋯ e_k  c and {a, e_1, …, e_k, c} is a ladder in (T). Note that b cannot be any of e_i since any element between b and c in (T) is bigger than c with respect to . However, this means that b is climbing the ladder {a, e_1, …, e_k, c} which contradicts the assumption.

Now let d_1, d_2, …, d_s be the elements between a and c in the row of T containing a and c. We also set d_0=a and d_s+1=c for simplicity. (Note that d_0d_1⋯ d_s d_s+1 is a subword of (T).) Then by the condition of -tableaux, we have  d_i d_i+1 for i ∈ [0,s]. (In particular, we have s≥ 1.) We claim that there exists e_1∈{d_1, …, d_s} such that d_0 _ e_1. Suppose otherwise, then as d_0  d_s+1 and d_0 d_1, there exists j ∈ [1,k] such that d_0  d_j and d_0  d_j+1. However, this is impossible since  d_j d_j+1.

Since d_0 _ e_1 and d_0  d_s+1, we have e_1 >d_s+1 by . If e_1  d_s+1 then it contradicts that (a,c) = (d_0,d_s+1) ∈_((T)), and thus we should have e_1  d_s+1. Now we can iterate this process forever and find e_1, e_2, …∈{d_1, …, d_s} such that e_1 _ e_2 _⋯. This is clearly a contradiction, and thus we conclude that _((T))= l which is what we want to prove.




 §.§ Proof of Theorem <ref><ref>

Let (w)=(PT', QT'). We first show that PT'=PT. Let PT=(PT_1, …, PT_k, PT_k+1, …, PT_p) where the length of PT_i equals 1 if and only if i>k. Then direct calculation shows that Φ(PT_k+PT_k+1+⋯+PT_p, ∅) = ((PT_k), (,…,)+PT_k+1+⋯+PT_p+()). Now if we assume PT_i=(…, a) and PT_i+1 = (b, …, c) for i ∈ [1,k-1], then we have a<b since otherwise a c by  which contradicts the assumption that PT is a -tableau. (Here it is crucially used that the length of PT_i+1 is ≥ 2.) In other words, if x and y are processed in the same step then x, y should be in the same column of PT. Thus by Proposition <ref><ref>, we have Φ(w, ∅) = (PT_1, (,⋯,)+PT_2+(, ⋯, )+PT_3+⋯+(, ⋯, )+PT_k+1+⋯+PT_p+()), i.e. the first column of PT' is equal to that of PT. Now we iterate this argument to conclude that PT=PT' as desired.

It remains to show that QT'=ω(T_λ). By part <ref> of the theorem, if we set l_1, …, l_p to be the column lengths of λ then we have (QT') = {n-x | x∈ [1,n-1], x≠∑_i=1^k l_i  k ∈ [1, p]}. By the property of evacuation, it follows that (ω(QT'))= [1,n-1]-{∑_i=1^k l_i | k ∈ [1, p]}. Now the result follows from the fact that T_λ is the only standard Young tableau of shape λ that satisfies this property.



 §.§ Proof of Theorem <ref><ref>
 Suppose that (α) = (α')=(PT, QT) where PT=(PT_1, …, PT_p) ∈_λ and QT=(QT_1, …, QT_p) ∈_λ.  Also, let α=α_0, α_1, …, α_p=(, …, ) and α'=α_0', α_1', …, α_p'=(, …, ) be the elements in  such that Φ(α_i, ∅) = (PT_i+1, α_i+1) and Φ(α_i', ∅) = (PT_i+1, α_i+1') for i ∈ [0,p-1]. Clearly α_p=α'_p, and thus it suffices to show that α_i+1=α'_i+1⇒α_i=α'_i for i ∈ [0,p-1]. However it follows from Lemma <ref> since (∅, α_i)= Ψ^_X_i+1(α_i+1, PT_i+1) and (∅, α_i')= Ψ^_X_i+1(α_i+1', PT_i+1) where X_i+1 = {|α|+1-j| j ∈ QT_i+1}.




 §.§ Proof of Theorem <ref><ref>
 By part <ref> of the theorem, it suffices to show that : _n →_λ⊢ n_λ×_λ is surjective. 
We have (here ω is Schützenberger's evacuation)

    ∑_λ⊢ n∑_PT∈_λ∑_QT∈_λ F_(ω(QT))
       =∑_λ⊢ n∑_PT∈_λ∑_QT∈_λ F_(QT)   (∵ω_λ)
    
       =∑_λ⊢ n |_λ| · s_λ   (∵<cit.>)
    
       =∑_w ∈_n F__(w)   (∵<cit.>)
    
       =∑_(PT, QT) ∈ F_(ω(QT))   (∵part <ref> and injectivity of )
    
       =∑_λ⊢ n∑_PT ∈_λ∑_(PT, QT) ∈ F_(ω(QT)).

This equality holds only when  is surjective, from which the result follows.

 It is possible to prove surjectivity of  without relying on Gasharov's result. Indeed, instead one may argue similarly to the proof of Proposition <ref> and use properties of -tableaux for  which avoids _(3,1,1),5 and _(4,2,1,1),6. Or conversely, from the theorem above we obtain the following bi-product.

 Suppose that  avoids _(3,1,1),5 and _(4,2,1,1),6. Let PT=(PT_1, …,PT_l) ∈_λ and QT=(QT_1, …, QT_l)∈_λ for some λ⊢ n. Define α_0, α_1, …, α_l∈, c_0,c_1, …, c_l∈ successively so that α_l=(,…,), |α_l|=n, and Ψ_X_i^(α_i, PT_i) = (c_i-1, α_i-1) for i ∈ [1,l] where X_i={n+1-x| x∈QT_i}. Then we have c_0=c_1=⋯=c_l=∅, (α_0) = (PT, QT), and α_0∈_n.

 By Theorem <ref><ref>, there exists w∈_n such that (w) = (PT, QT). It means that there exists w=w_0, w_1, …, w_l=(,…, ) such that Φ(w_i-1, ∅)=(PT_i, w_i) and QT_i={j ∈ [1,n] | (w_i-1)_j≠, (w_i)_j=} for i ∈ [1,l] where (w_i-1)_j and (w_i)_j are the j-th coordinates of w_i-1 and w_i, respectively. Now the result follows from successively applying Lemma <ref>.





 §.§ Proof of Theorem <ref>

Suppose that Γ=(V, _, {E_i}) is a connected -Knuth equivalence graph. We claim that PT∈{PT_1, …, PT_k} if (w)=(PT, QT) for some w∈ V. Indeed, we have (PT)  w w_i (PT_i) for any i ∈ [1,k] by Theorem <ref><ref>. By assumption, it means that (PT) ∈{(PT_1), …, (PT_k)}. Since a -tableau is completely determined by its reading word, it means that PT ∈{PT_1, …, PT_k} as desired.

It is clear that _n is a disjoint union of connected -Knuth equivalence graphs. Since  is a bijection between _n and _λ⊢ n_λ×_λ, it follows that (V) = _i=1^k{PT_i}×_λ_i. Thus we have (here |_(V)| is a fake -inversion number of any w∈ V and ω is Schützenberger's evacuation)

    γ_V   =t^|_(V)|∑_w ∈ V F__(w)
       =t^|_(V)|∑_(PT, QT) ∈(V) F_(ω(QT))    (∵Theorem <ref><ref> and injectivity of )
    
       =t^|_(V)|∑_i=1^k∑_T ∈_λ_i F_(ω(T))    (∵(V) = _i=1^k{PT_i}×_λ_i)
    
       =t^|_(V)|∑_i=1^k∑_T ∈_λ_i F_(T)   (∵ω_λ_i)
    
       =t^|_(V)|∑_i=1^ks_λ_i   (∵<cit.>)

as desired.

Finally, the last sentense of the theorem follows directly from Theorem <ref><ref>.







amsalpha


