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$?
Best Answer
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".