Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $S_n$ be the symmetric group on $n$ elements. The Robinson-Schensted-Knuth (RSK) correspondence sends a permutation $\pi\in S_n$ to a pair of Standard Young Tableaux $(P,Q)$ with equal shapes $\mbox{sh}(P)=\mbox{sh}(Q)=\lambda$, where $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_r)$ and $\lambda_1\geq\lambda_2\geq\cdots\geq \lambda_r$. A well known fact is that if $\pi$ is an involution ($\pi^2=1$) then $P=Q$. A nice way to think about involutions is by their cycle types: they must have only fixed points or 2-cycles. I have a few questions on what is known in this area.

1) Suppose we fix a shape $\lambda$. Is anything known about the class of involutions whose RSK correspondence gives tableaux of shape $\lambda$? Is there anything particularly special about them? For general permutations $\pi$, this question is essentially intractable but, my hope is for involutions there is something extra special that can be said.

The only things that I can think of are stuff like Greene's theorem on how the lengths of each row/column relate to the longest increasing/decreasing subsequences of the permutation. As well, the number of odd-length columns equals the number of fixed points. This unfortunately doesn't say much about the involutions involved.

2) Are there any other (not necessarily directly related to RSK) known bijections between involutions and Standard Young Tableaux? In particular, are these other bijections more amenable to answering questions similar to (1) about which subset of involutions maps to a specific shape $\lambda$?

share|improve this question
    
In point 1, do you mean the Greene invariant - the way of computing the shape corresponding to $\pi$ from $\pi$? That includes the fact that the length of the first row is the length of the longest increasing subsequence as a special case, so I presume that's what you're thinking of. But yes, that tells you pretty much nothing about the tableau itself. Have you thought at all about the notions of plactic and coplactic equivalence (or Knuth equivalence)? They describe ways of altering $\pi$ to find other permutations that correspond to the same shape as $\pi$. –  coolpapa May 26 at 1:19

1 Answer 1

For question 2, there was a paper published in 2013, Standard Young tableaux and colored Motzkin paths. http://www.sciencedirect.com/science/article/pii/S009731651300099X. They used "colored Motzkin paths" to characterize standard Young tableaux, and I think "colored Motzkin paths" is something like non-crossing partition. Roughly, the level step is a fixed-point in the involution and the pairs of up and down steps are the cycle in the involution. The most important things in this paper is that they found the relation between "bounded height SYT" and some restrictions of "colored Motzkin path".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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