7
$\begingroup$

It is well known via the RSK-correspondence that the length of the longest decreasing subsequence in a permutation $\pi \in S_n$ is the length of the longest column of the insertion tableau of $\pi$. ( The insertion tableau and the recording tableau produced by this algorithm have the same shape)

link text

My question is what else can be gleaned from the RSK correspondence in terms of ,say,

a) the length of the next longest decreasing subsequence in $\pi$ ?

b) the number of longest decreasing subsequences in $\pi$, given the fact that there is exactly one column of maximum length ?

c) can we say more about the above two questions if we knew that $\pi$ was an involution? (If $\pi$ happens to be an involution, then insertion tableau and recording tableau produced are equal)

$\endgroup$
3
  • $\begingroup$ You probably know this, but I figure it's worth reminding people that π is an involution if and only if P and Q (the tableaux under RSK) are equal. $\endgroup$ Nov 10, 2010 at 14:13
  • $\begingroup$ Agreed. I edited accordingly. $\endgroup$ Nov 11, 2010 at 2:32
  • $\begingroup$ @Vasu-vineet, while you do have a link to a page explaining the Robinson-Schensten-(Knuth) RSK correspondence, you never specifically state the full name of the algorithm. Others reading this page would be a bit mystified and may not bother clicking through to read the details of concept which establishes a bijective correspondence between elements of the symmetric group $S_n$ and pairs of standard Young tableaux of the same shape. Also, your wikipedia link has malformed characters in it and doesn't work. Try en.wikipedia.org/wiki/Robinson-Schensted_algorithm $\endgroup$ Nov 11, 2010 at 2:56

1 Answer 1

6
$\begingroup$

For a version of a), see C. Greene, An extension of Schensted's theorem, Advances in Mathematics, 1974. Note: the result is beautiful, but the statement is a bit delicate.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.