Combinatorics Seminar

When: Sunday, November 21, 10am
Where: Schreiber 309
Speaker: Nathan Linial, Hebrew University
Title: On the Lipschitz constant of the RSK correspondence


The RSK correspondence (after Robinson, Schensted and Knuth who made some of the fundamental discoveries in this area) is a wonderful mathematical object. To every permutation \pi on [n], it associates an ordered pair (P,Q) of Standard Young Tableaux on [n] with the same shape. This mapping is a bijection and it has numerous surprising properties. Among the different places at which this correspondence appears are: Various problems in combinatorics and specifically in the study of monotone subsequences of random permutations. It plays a key role in the representation theory of the symmetric group and other parts of algebra. Various asymptotic properties of this correspondence were studied as well. However, most of the work in this area is combinatorial and algebraic. Here we investigate the following natural analytic/geometric aspect of the RSK correspondence: If we start from a permutation \pi and modify it slightly, to what extent will the shape of the corresponding tableaux change? Here "a slight change" means pre-multiplying the permutation 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.

No prior knowledge of the subject is assumed and everything will be defined from scratch.

This is joint work with Nayantara Bhatnagar.