Mathematics Colloquia and Seminars

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.