Combinatorics Seminar
When: Sunday, November 21, 10am
Where: Schreiber 309
Speaker: Nathan Linial, Hebrew University
Title: On the Lipschitz constant of the RSK correspondence
Abstract:
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.