On the Lipschitz Constant of the RSK Correspondence

Abstract

We view the RSK correspondence as associating to each permutation $\ddot{I}€\in S_n$ a Young diagram $\hat{I}»=\hat{I}»(\ddot{I}€)$, i.e. a partition of $n$. Suppose now that $\ddot{I}€$ is left-multiplied by $t$ transpositions, what is the largest number of cells in $\hat{I}»$ that can change as a result? It is natural refer to this question as the search for the Lipschitz constant of the RSK correspondence. We show upper bounds on this Lipschitz constant as a function of $t$. For $t=1$, we give a construction of permutations that achieve this bound exactly. For larger $t$ we construct permutations which come close to matching the upper bound that we prove.

Updated presentation based on comments made by reviewers. Accepted for publication to JCTA