## Greene’s theorem, Knuth moves, and Jeu de Taquin

Lemma 6 ${I_k(\omega), D_k(\omega)}$ do not change under Knuth moves.

Proof:

1. ${I_k}$ and ${D_k}$ are related by ${I_k(\omega) = D_k(\omega')}$, where if ${\omega = \omega_1 \ldots \omega_n}$, then ${\omega' = \omega_n \ldots \omega_1}$. This follows fromm the definition of ${I_k,D_k}$.Therefore ${\omega \overset{K}{\sim} \nu}$ if and only if ${\omega' \overset{K}{\sim} \nu'}$.
2. Fix ${k}$, suppose the lemma is false. Say ${I_k(\omega) = m}$. After a Knuth move ${acb \rightarrow cab}$ of ${\omega}$, we arrive at ${\omega'}$, and have ${I_k(\omega') < m}$ without loss of generality.

Claim: For any ${\sigma_1,\ldots, \sigma_k}$ increasing subsequences in ${\omega}$, ${\sum |\sigma_k| = m}$, the fact ${I_k(\omega') < I_k(\omega)}$ implies that ${a,c \in \sigma_i}$, and ${b \in \sigma_j}$ for some ${i \neq j}$. Now after the Knuth move switching ${a}$ and ${c}$, we can still fit all three symbols into the union of two increasing subsequences by combining the part before ${acb}$ in ${\sigma_i}$ with the part after ${acb}$ in ${\sigma_j}$ and vice versa, i.e. a cross breeding of the two subsequences. (See Fomin’s appendix of Stanley volume 2 for more detail) $\Box$

Given ${T}$ a standard Young tableau, e.g.

$\displaystyle T = \begin{array}{cccc} 1& 3 & 5 & 6\\ 2 &4 && \\ 7&8&& \end{array}, \ \ \ \ \ (17)$

the reading of ${T}$ is given by ${\text{Read}(T) = 78241356}$.

Lemma 7 Any ${\omega}$ is Knuth equivalent to the reading word of ${P(\omega)}$ the insertion tableau.

Proof: It is enough to show that if ${P}$ is some partial Young tableau and ${k \notin P}$, then

$\displaystyle (\text{Read}(P),k) \overset{K}{\sim} \text{Read}(P) \leftarrow k \ \ \ \ \ (18)$

For this it is enough to consider the insertion operation for one row. For example, if ${P=1356}$, ${k=2}$,

$\displaystyle \text{Read}(P) ,k = 13562 \ \ \ \ \ (19)$

and ${\text{Read}(P) \leftarrow k = 31256}$. $\Box$

From the fact that Knuth moves don’t change ${I_k}$‘s, we arrive at

Corollary 8 ${\text{Read}(P(\omega))}$ and ${\omega}$ have the same ${I_k,D_k}$ for all ${k}$.

Lemma 9 Let ${\omega = \text{Read}(T)}$, then ${P(\omega) = T}$.

Proof: For a permutation sequence arising from the reading of a standard Young tableau, the insertion procedure of RSK algorithm applied to it simply places the rows (which are increasing subsequences) on top of each other, because they displace the previous top rows in a systematic left to right way. Thus the proof is by inspection. $\Box$

Proof: (of Greene’s theorem; for statement see the end of previous lecture) We may assume by the above corollary and lemma that ${\omega = \text{Read}(T)}$, for some ${T}$.

• the rows of ${T}$ give increasing subsequences of ${\omega}$, so ${I_k(\omega) \ge \lambda_1 + \ldots + \lambda_k}$.
• the columns of T gives decreasing subsequences, ${D_k(\omega) \ge \lambda'_1 + \ldots + \lambda'_k}$.
• Consider a box on the rim of ${T}$. For example

$\displaystyle T = \begin{array}{cccc} 1 & 3 & 4 & 8 \\ 2 & 6 & 7 & \\ 5 & 9 & & \end{array} \ \ \ \ \ (20)$

the boxes on the rim are ${\{5, 9 , 6 , 7 , 4 , 8 \}}$. Say the box we chose is in position ${(k,l)}$ e.g. ${(2,2) = 6}$ in the numerical example above. Then

$\displaystyle \lambda_1 + \ldots + \lambda_k + \lambda'_1 + \ldots + \lambda'_l = n + kl \ \ \ \ \ (21)$

Hence ${I_k(\omega) + D_k(\omega) \ge n + kl}$.

• an increasing subsequence ${\sigma}$ and a decreasing subsequence ${\tau}$ can intersect in at most one place. Thus ${I_k(\omega) + D_k(\omega) \le n + kl}$. For example, the case ${k=l=1}$ is intuitively clear. thus ${I_k(\omega) + D_k(\omega) = n + kl}$ for all ${(k,l)}$ on the rim. Therefore

$\displaystyle I_k(\omega) = \lambda_1 + \ldots + \lambda_k, D_k(\omega) = \lambda'_1 + \ldots + \lambda'_l \ \ \ \ \ (22)$

since for every ${k}$, there is some ${l}$ such that ${(k,l)}$ is on the rim, this proves the theorem.

$\Box$

Corollary 10 (Easy) ${\text{Sh}(P(\omega))}$ is consant on Knuth classes.

Theorem 11 ${P(\nu) = P(\omega)}$ if and only if ${\nu \overset{K}{\leftrightarrow} \omega}$.

Proof: Fix k, let ${\omega_k}$ be the subpermutation of ${\omega}$ using ${1,2,\ldots, k}$. For example, if ${\omega = 1724365}$, then ${\omega_3 = 123}$, ${\omega_4 = 1243}$. Let ${P(\omega)}$ be insertion tableau for ${\omega}$, ${P_k}$ insertion tableau for ${\omega_k}$. Because ${k+1, \ldots, n}$ don’t affect ${1,\ldots, k}$, ${P_k}$ is just subtableau with ${1,\ldots, k}$. Take ${\omega = 592671348 = P (\begin{array}{cccc} 1 & 3 & 4 & 8\\ 2 & 6 & 7 & \\ 5 & 9 & & \end{array})}$.
Crucial observation: any Knuth move either doesn’t change ${\omega_k}$ or is a Knuth move on ${\omega_k}$. Since a tableau ${T}$ is uniquely determined by a sequence of shapes

$\displaystyle \begin{array}{c} 1 \\ \end{array} \Rightarrow \begin{array}{c} 1 \\ 2 \end{array} \Rightarrow \begin{array}{cc} 1 & 3 \\ 2 & \end{array} \Rightarrow \begin{array}{ccc} 1 & 3 & 4 \\ 2 && \end{array} \ldots \ \ \ \ \ (23)$

and all shapes are unchanged by Knuth moves, we have ${\emptyset \le \text{Sh}(P_{(1)}) \le \ldots \le \text{Sh}(P_{(n)})}$. $\Box$

Jeu de Taquin, evacuation:
Motivation: consider ${\omega = \omega_1 \omega_2 \ldots \omega_n \leftrightarrow (P(\omega), Q(\omega))}$. What about ${\omega' = (\omega_n, \ldots, \omega_1)}$?

Theorem 12 ${\omega' \leftrightarrow (P(\omega)^T, \text{EV}(Q)^T)}$. Here ${\text{EV}(Q)}$ is an involution, ${Q \rightarrow \text{EV}(Q)}$ has the same shape obviously.

Example:

$\displaystyle \begin{array}{c}1 \\ \end{array} \Rightarrow \begin{array}{cc}1 & 4\\ & \end{array}\Rightarrow \begin{array}{cc}1 &2\\4 \end{array}\Rightarrow \begin{array}{ccc}1 & 2 & 5\\ 4 &&\end{array}\Rightarrow \begin{array}{ccc}1 & 2 & 3\\ 4 & 5 &\end{array} = P(\omega) \\ \begin{array}{c}1 \\ \end{array} \Rightarrow \begin{array}{cc}1 & 2\\ & \end{array}\Rightarrow \begin{array}{cc}1 &2\\3 \end{array}\Rightarrow \begin{array}{ccc}1 & 2 & 4\\ 3 &&\end{array}\Rightarrow \begin{array}{ccc}1 & 2 & 4\\ 3 & 5 &\end{array} = Q(\omega) \ \ \ \ \ (24)$

Here comes Jeu de Taquin on ${Q}$. Removing top left corner and slide the small one in

$\displaystyle \begin{array}{ccc} 1 & 2 & 4 \\ 3 & 5 & \end{array} \Rightarrow \begin{array}{cc} 2 & 4 \\ 3 & 5 \end{array} \Rightarrow \begin{array}{cc} 3 & 4 \\ 5 & \end{array} \Rightarrow \begin{array}{c} 4 \\ 5 \end{array} \Rightarrow \begin{array}{c} 5 \\ \end{array} \Rightarrow \emptyset \ \ \ \ \ (25)$

Play the sequence backward and label the ${j}$th newly added position by ${j}$ (i.e., a bookkeeping tableau), we get the standard Young tableau ${\text{EV}(Q)}$:

$\displaystyle \begin{array}{ccc} 1 & 3 & 5\\ 2 & 4 & \end{array} = \text{EV}(\begin{array}{ccc} 1 & 2 & 4 \\ 3 & 5 & \end{array}) \ \ \ \ \ (26)$

As a corollary, if ${\omega \leftrightarrow (P(\omega),Q(\omega))}$, and ${\bar{\omega} := (n+1 - \omega_n, n+1 - \omega_{n-1}, \ldots, n+1 - \omega_1)}$, then

$\displaystyle \bar{\omega} \Leftrightarrow (\text{EV}(P), \text{EV}(Q)). \ \ \ \ \ (27)$