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)

Advertisements

About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in algebraic combinatorics, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s