Here is the main problem we are trying to solve today.
Given a word let us consider disjoint subwords of which are weakly increasing. For example if , then we can pick two or three disjoint subwords as follows:
For each , we wish to compute , the maximum length sums of disjoint weakly increasing subwords. In our example, However, since we can add the second ‘5’ to the circles, thus using up 8 numbers in the word. It turns out we do have although this is not obvious at the moment.
There is at least one case where computing is trivial.
Proposition 1. If for some SSYT of shape , then for each we have:
Indeed if has rows , then and the words are disjoint weakly increasing words of the required length sum. Hence
Conversely, if are disjoint weakly increasing subwords of , the numbers in each are from different columns of . So in each column of at most entries are used among the and the length sum of is at most ♦
The good news is, every case can be reduced to the SSYT case. Indeed, given any word we can write for some skew SSYT Now we perform sliding operations to turn into an SSYT By the next result, for all k, so we can revert to the above special case.
Proposition 2. If are Knuth-equivalent words, then
We may assume is obtained from by rule R1 or R2. Let us consider each case.
R1: in we have a consecutive triplet with ; we swap and to get In most instances, disjoint weakly increasing subwords of will remain so in and vice versa. The only problem is when a subword of contains , say If no subword contains we can replace with and the resulting word is still weakly increasing. If not, we swap the heads:
which are still weakly increasing.
R2: similarly, in we have a consecutive triplet with ; swap and to get The critical case is now as follows:
This completes the proof. ♦
Thus we have:
Algorithm. To compute , write for a skew SSYT , perform the sliding algorithm to turn into an SSYT of shape Now we have:
E.g. in our initial example of (1, 1, 5, 4, 2, 5, 4, 6, 7), first write it as a word of some skew SSYT, then perform sliding to turn it into an SSYT.
It follows that , and .
Question to Ponder
Besides computing , what is an efficient way to compute explicit disjoint subwords with the desired length sum?
Uniqueness of SSYT for Word
We need the following lemma for our theorem later.
Lemma. If and (resp. ) is obtained from (resp. ) by removing the largest element, then The same holds for the smallest element.
Here, if the maximal element of occurs more than once, the rightmost occurrence is taken to be the largest. Similarly, the leftmost occurrence of the minimal element is the smallest.
We may assume is obtained from by R1 or R2, i.e. by replacing a consecutive triplet:
If none of is maximal, we are done. Otherwise, in both cases, is maximal; after removing it, we get in and
In the case the smallest element is removed, in the first case we remove and obtain in both and In the second case, we remove and obtain in both and ♦
Now we have enough tools to prove the following result we claimed earlier.
Theorem. For any word there is a unique SSYT such that
We call this the rectification of the word For a skew SSYT the rectification of is also called the rectification of
Existence of was proven earlier; we now prove uniqueness, i.e. for any SSYT
By proposition 2, the shape of satisfies
so and have the same shape. Now we proceed by induction on ; when we clearly have
Suppose and is the largest element in and if this occurs more than once, we take the rightmost occurrence. Note that must lie in a corner square of and Removing it thus gives us SSYT and By the above lemma, we have
Since has one less square than , by induction hypothesis And since and have the same shape, we have ♦
There is a bijection:
The bijection is preserved when we drop the maximum or minimum element in either case. Clearly concatenation preserves Knuth-equivalence:
since any sequence of R1’s and R2’s performed on can be done on Thus this gives an associative product operation on the set of SSYT: given let be the rectification of This motivates the product operation we defined earlier.