Robinson-Schensted shapes arising from cycle decompositions

Abstract

In the symmetric group $S_n$, each element $\ddot{I}ƒ$ has an associated cycle type $\hat{I}\pm$, a partition of $n$ that identifies the conjugacy class of $\ddot{I}ƒ$. The Robinson-Schensted (RS) correspondence links each $\ddot{I}ƒ$ to another partition $\hat{I}»$ of $n$, representing the shape of the pair of Young tableaux produced by applying the RS row-insertion algorithm to $\ddot{I}ƒ$. Surprisingly, the relationship between these two partitions, namely the cycle type $\hat{I}\pm$ and the RS shape $\hat{I}»$, has only recently become a subject of study. In this work, we explicitly describe the set of RS shapes $\hat{I}»$ that can arise from elements of each cycle type $\hat{I}\pm$ in cases where $\hat{I}\pm$ consists of two cycles. To do this, we introduce the notion of an $\hat{I}\pm$-coloring, where one colors the entries in a certain tableau of shape $\hat{I}»$, in such a way as to construct a permutation $\ddot{I}ƒ$ with cycle type $\hat{I}\pm$ and RS shape $\hat{I}»$.

28 pages