Return to Colloquia & Seminar listing
The Lipschitz constant of the RSK correspondence
Algebra & Discrete Mathematics| Speaker: | Nayantara Bhatnagar, UC Berkeley |
| Location: | 2212 MSB |
| Start time: | Thu, Apr 21 2011, 4:10PM |
The Robinson-Schented-Knuth (RSK) correspondence in its most basic form is a bijection between the set of permutations S_n on n elements and ordered pairs of Young tableaux of size n with the same shape. This surprising bijection is intimately related to the representation theory of the symmetric group and the theory of symmetric functions. The bijection is defined through an algorithm which was studied by Schensted in his study of the longest increasing subsequence in a permutation.
A natural question is to characterize the permutations with a given shape under RSK and this is a well studied problem. In our work we ask an approximate version of such questions, namely to what extend the shape of the tableau changes when a permutation is modified slightly by pre-multiplication by t adjacent transpositions. For t=1 we give a tight answer and for larger t we give upper and lower bounds which are fairly close.
This is joint work with Nati Linial.