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$?

  • $\begingroup$ 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$. $\endgroup$
    – coolpapa
    May 26, 2014 at 1:19
  • $\begingroup$ For any partition $\lambda$ we get h($\lambda$) tableaux. Combining (by RSK) pairs of identical tableaux, we get h($\lambda$) involutions. Why are all these involutions of the same cycle type? $\endgroup$
    – Wouter M.
    Dec 9, 2014 at 22:47
  • $\begingroup$ ... and since we know that the count k of odd parts in $\lambda'$ equals the count of fixed points in the involution, what can that involution be except some 2's followed by k 1's with total equal to weight $\lambda$ ? $\endgroup$
    – Wouter M.
    Jan 10, 2015 at 17:23

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".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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